A Directory Index for EXT2

In recent years, filesystem designers have tended to favor the use of BTrees and variants thereof to eliminate directory performance bottlenecks. The idea of adding BTree directory indexing to Linux's Ext2 filesystem has been much discussed but never implemented, more probably due to an aversion to complexity than any laziness on the part of developers. Recently, I conceived and implemented a new kind of indexing technique using hashed keys held in a uniform-depth tree. I gave this structure the name "HTree". Compared to a BTree, the HTree has a considerable simpler implementation but offers similar performance. Furthermore, it turned out to be possible to achieve not only backward compatibility with existing Ext2 filesystems, but forward compatibility with earlier versions of Linux as well.