HTree

HTree はLinuxのファイルシステムで使われている、B木に似た木構造を用いたディレクトリインデックスである。HTreeの深さは1種か2種の値で一定であり、ファン・アウト数が大きいのが特徴である。ファイル名のハッシュを用いる構造であり、平衡を取る必要はない^[1]。単に、標準的なB木のアルゴリズムを応用すると、ハッシュの衝突が生じた場合に、複数の葉ノードとインデックスブロックがオーバーフローを生じるため、HTreeではその対処を行っている。HTreeを用いたインデックスは、Linuxのファイルシステムであるext3やext4で用いられ、Linuxカーネル 2.5.40 に組み込まれている^[2]。HTreeのインデックスはLinux ext2 ベースのファイルシステムが数千ファイルで実質的に制限されていた問題を、ディレクトリごとに数千万ファイルを扱える程に改善した。

歴史

HTreeによるインデックスのデータ構造とアルゴリズムは2000年に Daniel Phillips によって開発され、2001年2月に ext2 ファイルシステム用に実装された。2002年には、Christopher LiとAndrew Mortonがジャーナリングファイルシステムをベースとした衝突一貫性を、2.5系のカーネルのext3ファイルシステムへのポートに追加した。さらに軽微な改良が加えられ、HTreeはLinux 3.x.xカーネルシリーズのext4で引き続き使用されている。

使用例

ext2 HTreeインデックスはもともと ext2 用に開発されたが、結局パッチは公式ブランチには作られなかった。dir_index機能は、ext2ファイルシステムを作成するときに有効にできる一方で、ext2コードはext2ファイルシステムでは動作しません。
ext3 HTreeインデックスは、dir_index機能が有効な場合にext3で利用可能である。
ext4 HTreeインデックスはext4ではデフォルトで有効になっている。この機能は、Linuxカーネル2.6.23で実装された。HTreeインデックスは、ファイルがInodeに格納されている5つ以上のエクステントを必要とする場合、ファイルエクステントにも使用されます。

PHTree

PHTree (Physically stable HTree) は、HTreeの後継として開発された^[3]。Write multiplication以外のHTreeの既知の問題をすべて修正したHTreeである。PHTreeはTux3ファイルシステムで使用されている^[4]。

出典

^ Mingming Cao. “Directory indexing”. Features found in Linux 2.6. 2018年2月4日閲覧。
^ tytso@mit.edu. “Add ext3 indexed directory (htree) support”. 2018年2月4日閲覧。
^ http://phunq.net/pipermail/tux3/2013-January/000026.html^{[信頼性要検証]}
^ “Archived copy”. 2015年1月13日時点のオリジナルよりアーカイブ。2014年12月28日閲覧。

外部リンク

Ext2 のディレクトリインデックス (HTreeのデータ構造の説明) at Archive.is (archived 2013-04-15)
HTree
HPDD Wiki - 並列ディレクトリの高度な設計

[1] Mingming Cao. “Directory indexing”. Features found in Linux 2.6. 2018年2月4日閲覧。

[2] tytso@mit.edu. “Add ext3 indexed directory (htree) support”. 2018年2月4日閲覧。

[3] ttp://phunq.net/pipermail/tux3/2013-January/000026.html^{[信頼性要検証]}

[4] “Archived copy”. 2015年1月13日時点のオリジナルよりアーカイブ。2014年12月28日閲覧。

[1]

[2]

[3]

[4]