HTree

HTree はLinuxのファイルシステムで使われている、B木に似た木構造を用いたディレクトリインデックスである。HTreeの深さは1種か2種の値で一定であり、ファン・アウト数が大きいのが特徴である。ファイル名のハッシュを用いる構造であり、平衡を取る必要はない。単に、標準的なB木のアルゴリズムを応用すると、ハッシュの衝突が生じた場合に、複数の葉ノードとインデックスブロックがオーバーフローを生じるため、HTreeではその対処を行っている。HTreeを用いたインデックスは、Linuxのファイルシステムであるext3やext4で用いられ、Linuxカーネル 2.5.40 に組み込まれている。HTreeのインデックスはLinux ext2 ベースのファイルシステムが数千ファイルで実質的に制限されていた問題を、ディレクトリごとに数千万ファイルを扱える程に改善した。
歴史.
HTreeによるインデックスのデータ構造とアルゴリズムは2000年に Daniel Phillips によって開発され、2001年2月に ext2 ファイルシステム用に実装された。2002年には、Christopher LiとAndrew Mortonがジャーナリングファイルシステムをベースとした衝突一貫性を、2.5系のカーネルのext3ファイルシステムへのポートに追加した。 さらに軽微な改良が加えられ、HTreeはLinux 3.x.xカーネルシリーズのext4で引き続き使用されている。
PHTree.
PHTree (Physically stable HTree) は、HTreeの後継として開発された。Write multiplication以外のHTreeの既知の問題をすべて修正したHTreeである。PHTreeはTux3ファイルシステムで使用されている。