|
5th Annual Linux Showcase & Conference — Abstract
Pp. 173-182 of the Proceedings
A Directory Index for Ext2
Daniel Phillips
Abstract
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.
