Check out the new USENIX Web site.

Home About USENIX Events Membership Publications Students
5th Annual Linux Showcase & Conference — Abstract

Pp. 173-182 of the Proceedings

A Directory Index for Ext2

Daniel Phillips


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.
?Need help? Use our Contacts page.

Last changed: 22 Aug. 2003 ch
Technical Program
ALS 2001 Home