Content deleted Content added
removed Category:Trees (data structures) using HotCat |
move PHTree - this needs better sourcing, and one for the (probably) self-claim |
||
Line 2:
{{primary sources|date=September 2013}}
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 table|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 distinguished from standard B-tree methods by its treatment of [[hash collision]]s, which may overflow across multiple leaf and index blocks. HTree [[index (database)|index]]es are used in the [[ext3]] and [[ext4]] [[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.
PHTree is a derivation intended as a successor.<ref>http://phunq.net/pipermail/tux3/2013-January/000026.html</ref> It fixes all the known issues with HTree except for write multiplication.▼
==History==
The HTree index data structure and algorithm were developed by Daniel Phillips in 2000 and implemented for the ext2 filesystem in February 2001. A port to the ext3 filesystem by Christopher Li and [[Andrew Morton (computer programmer)|Andrew Morton]] in 2002 during the 2.5 [[kernel (computing)|kernel]] series added [[journaling file system|journal]] based crash consistency. With minor improvements, HTree continues to be used in ext4 in the Linux 3.x.x kernel series.
==Use==
Line 13 ⟶ 11:
* [[ext4]] HTree indexes are turned on by default in ext4. This feature is implemented in Linux kernel 2.6.23. HTree indexes is also used for file [[Extent (file systems)|extents]] when a file needs more than the 4 extents stored in the [[inode]].
==
▲PHTree (Physically stable HTree) is a derivation intended as a successor.<ref>http://phunq.net/pipermail/tux3/2013-January/000026.html{{rs|date=December 2014}}</ref> It fixes all the known issues with HTree except for write multiplication.
==References==
| |||