 | This articlerelies excessively onreferences toprimary sources. Please improve this article by addingsecondary or tertiary sources. Find sources: "HTree" – news ·newspapers ·books ·scholar ·JSTOR(September 2013) (Learn how and when to remove this message) |
AnHTree is a specializedtree data structure for directory indexing, similar to aB-tree. They are constant depth of either one or two levels, have a high fanout factor, use ahash of thefilename, and do not requirebalancing.[1] The HTree algorithm is distinguished from standard B-tree methods by its treatment ofhash collisions, which may overflow across multiple leaf and index blocks. HTreeindexes are used in theext3 andext4Linuxfilesystems, and were incorporated into theLinux kernel around 2.5.40.[2] HTree indexing improved the scalability ofLinux ext2 based filesystems from a practical limit of a few thousand files, into the range of tens of millions of files per directory.
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 andAndrew Morton in 2002 during the 2.5kernel series addedjournal based crash consistency. With minor improvements, HTree continues to be used in ext4 in the Linux 3.x.x kernel series.
PHTree (Physically stable HTree) is a derivation intended as a successor.[3][unreliable source?] It fixes all the known issues with HTree except for write multiplication.[citation needed] It is used in theTux3 filesystem.[4]