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.”