Encontrei a resposta compartilhando esta pergunta no Google Plus. A resposta de Axel Engeland :
That really depends on the file system used. Directories are supposed to store inode tables. If inode tables grow too large, another one is created and the tables are linked. So even if you removed all the files, there may still be a big amout of interlinked inode tables. if you rmdir and mkdir the directory again, performance should be better.
As you may have deleted all files but the last, the inode tables are still in place. ls -ld foo should show you the size of directory meta information. Consider:
# mkdir some_dir # ls -ld some_dir drwxr-xr-x 2 root root 4096 Oct 14 21:16 some_dir
So, the directory has 4096 bytes for meta data. ok. Let's make some files.
# pushd some_dir ; for i in {1..1000} ; do mktemp test.XXXXXXXXXXXXXX ; done ; popd
We just created 1000 files in some_dir.
# ls -ld some_dir drwxr-xr-x 2 root root 49152 Oct 14 21:16 some_dir
Oh wow, the directory now needs 49k für meta data. Let's remove the files.
# find some_dir/ -type f -delete # ls -ld some_dir drwxr-xr-x 2 root root 49152 Oct 14 21:19 some_dir
The files are gone. But still 48k meta data. A find will still have to go through all the meta data in the directory to... well... find something.