回答編集履歴

  Unix/Linux系の全てのファイルシステムを知っているわけではないですが、一般にディレクトリーの構造は、可変長のディレクトリーエントリー（可変長のファイル名と管理情報）が並んだ形式になっていて、データベースのような索引は無いので、ファイルを探すには先頭から見つかるまでディレクトリーファイルを読む必要があります。例えば、手元の`/usr/bin`は36KBなので、`/usr/bin/ls`の管理情報を知るために、平均すると18KBのファイルを読むことになります。

 

  質問の例だと、ファイル名が40バイトくらい(ちゃんと数えてませんが)のようなので、管理情報込みで1つのディレクトリーエントリーが60バイトだと仮定します。で、ファイルが1万6000個あったとすると、1つのディレクトリーに入れた場合、ディレクトリーサイズは、960,000 で、ファイルオープンや削除などをするために1ファイルの管理情報を得るために、平均480,000バイト読むことになります。

 

  あと、ディレクトリーエントリーは可変長なので、ファイル名の長さが異なるファイルを追加・削除を繰り返すと、空き領域の断片化が発生して、ディレクトリーサイズが肥大します。手元の`/tmp`はファイル数18個なのにサイズが112KBとかなり肥大化してます。作り直せば4KBで収まるはず。

  なので、キャッシュファイルの格納など、大量のファイルの追加削除が発生する場合は、ファイル名の長さを一定にすることが多いようです。ファイル名の長さが一定なら、全てのディレクトリーエントリーのサイズが同一で、削除したファイルの場所をそのまま再利用できるので、肥大化しません。肥大化すると読む量が増えるので、これも高速化のコツですね。