Htree
From Wikipedia, the free encyclopedia
Not to be confused with H tree.
An HTree is a specialized tree data structure for directory indexing, similar to a B-tree. They are constant depth of either one or two levels, have a high fanout factor, use a hash of the filename, and do not require balancing.[1] Htree indexes are used in the ext3 and ext4 Linux filesystems, and were incorporated into the Linux kernel around 2.5.40.[2]
Contents |
[edit] ext2
Main article: ext2
Htree indexes were originally implemented for ext2 but the patch never made it to the official branch. The dir_index feature can be enabled when creating an ext2 filesystem, but the ext2 code won't act on it.
[edit] ext3
Main article: ext3
Htree indexes are available in ext3 when the dir_index feature is enabled.
[edit] ext4
Main article: ext4
Htree indexes are turned on by default in ext4. This feature is implemented in Linux kernel 2.6.23.
[edit] See also
[edit] References
- ^ Mingming Cao. "Directory indexing". Features found in Linux 2.6. http://ext2.sourceforge.net/2005-ols/paper-html/node3.html.
- ^ tytso@mit.edu. "Add ext3 indexed directory (htree) support". http://lwn.net/Articles/11481/.
[edit] External links
|
||||||||||||||||||||||||||
 |
This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |
