Я нашел ответ, поделившись этим вопросом в Google Plus. Ответ Акселя Энгеланда:
Это действительно зависит от используемой файловой системы. Каталоги должны хранить таблицы inode. Если таблицы inode становятся слишком большими, создается еще одна таблица, и таблицы связываются. Таким образом, даже если вы удалили все файлы, все равно может быть много связанных таблиц inode. если вы снова запустите каталоги rmdir и mkdir, производительность должна быть выше.
Поскольку вы, возможно, удалили все файлы, кроме последнего, таблицы inode все еще остаются на месте. ls -ld foo должен показать вам размер метаинформации каталога. Рассматривать:
# mkdir some_dir
# ls -ld some_dir
drwxr-xr-x 2 root root 4096 Oct 14 21:16 some_dir
Итак, в каталоге 4096 байт для метаданных. Хорошо. Давайте сделаем несколько файлов.
# pushd some_dir ; for i in {1..1000} ; do mktemp test.XXXXXXXXXXXXXX ; done ; popd
Мы только что создали 1000 файлов в some_dir.
# ls -ld some_dir
drwxr-xr-x 2 root root 49152 Oct 14 21:16 some_dir
Ух ты, каталогу сейчас нужны 49 тысяч метаданных. Давайте удалим файлы.
# find some_dir/ -type f -delete
# ls -ld some_dir
drwxr-xr-x 2 root root 49152 Oct 14 21:19 some_dir
Файлы исчезли. Но все равно 48к метаданных. Поиск все равно должен пройти через все метаданные в каталоге, чтобы ... ну ... найти что-то.