A Directory Index for Ext2

The native filesystem of Linux, Ext2, inherits its basic structure from Unix systems that were in widespread use at the time Linus Torvalds founded the Linux project more than ten years ago. Although Ext2 has been improved and extended in many ways over the years, it still shares an undesireable characteristic with those early Unix filesystems: each directory operation (create, open or delete) requires a linear search of an entire directory file. This results in a quadratically increasing cost of operating on all the files of a directory, as the number of files in the directory increases. The HTree directory indexing extension was designed and implemented by the author to address this issue, and has been shown in practice to perform very well. In addition, the HTree indexing method is backward and forward-compatible with existing Ext2 volumes and has a simple, compact implementation. The HTree index is persistent, meaning that not only mass directory operations but single, isolated operations are accelerated. These desirable properties suggest the the HTree index extension is likely to become part of the Ext2 code base during the Linux 2.5 development cycle.

...

Download PDF.