Directories in ext2 and ext3 used to be simple linked lists. These had scalability problems. When you put a lot of files in a directory programs like ‘ls’ took non-linear (O^2) amounts of time to complete. To resolve this the ext3 folks added a new directory indexing feature, which replaces the linked lists with an “HTree.” I’d never heard of an HTree before, either, and Daniel Phillips, the inventor, explains in a paper presented at USENIX ALS 2001:
…I went on to discard the BTree approach, and invented a new type of indexing structure whose characteristics lie somewhere between those of a tree and a hash table. Since I was unable to find anything similar mentioned in the literature I took the liberty of giving this structure the name HTree, a hash-keyed uniform-depth index tree.
Many recent Linux distributions set dir_index automatically on filesystems you create with the installer. However, mke2fs does not set this automatically, so you should take care to set it yourself on new volumes you create from the command line:
mke2fs -j -O dir_index /dev/Volume00/yourlv
You can check to see if your volume has dir_index enabled with:
tune2fs -l /dev/Volume00/yourlv
It will be under “Filesystem features.”
Awesome tip on how to know if an existing ext3 FS already has htree/dir_index enabled. Novell Groupwise on SLES does not like htree and we were having trouble determining if it was on. It appears that SLES disables it/doesn’t enable it by default. Thanks.
Enabling dir_index makes readdir() not return entries in (almost) creation time order like usual, so stat()ing files in readdir() order, like many programs do, makes more I/O. (See Ted Tso libspd_readdir as a “workaround” http://www.mail-archive.com/[email protected]/msg11860.html)
Also, when the number of entries in a directory drops, the directory size does not decrease. That would be almost ok if the time for listing directory content dropped, but that’s not the case, it stays high.
Yuck.