HTree: Difference between revisions

An '''HTree''' is a specialized [[Tree (data structure)|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 [[balanced tree|balancing]].<ref>{{cite web|url=http://ext2.sourceforge.net/2005-ols/paper-html/node3.html|title=Directory indexing|author=Mingming Cao|work=Features found in Linux 2.6}}</ref> The HTree algorithm is distinquished from standard BTree methods by its treatment of hash collisions, which may overflow across multiple leaf and index blocks. Htree [[index (database)|index]]es are used in the [[ext3Ext3]] and [[ext4Ext4]] [[Linux]] [[filesystem]]s, and were incorporated into the [[Linux kernel]] around 2.5.40.<ref>{{cite web|url=http://lwn.net/Articles/11481/|title=Add ext3 indexed directory (htree) support|author=tytso@mit.edu}}</ref> HTree indexing improved the scalability of Linux Ext2 based filesystems from a practical limit of a few thousand files, into the range of tens of millions of files per directory.

*[[ext2]] Htree indexes were originally implementeddeveloped 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.