About: HTree

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