Hツリー
HTreeはディレクトリのインデックス作成に特化したツリーデータ構造で、Bツリーに似ています。1レベルまたは2レベルの一定の深さで、ファンアウト係数が高く、ファイル名のハッシュを使用し、バランス調整は不要です。[ 1 ] HTreeアルゴリズムは、複数のリーフおよびインデックスブロックにまたがってオーバーフローする可能性のあるハッシュ衝突の処理方法によって、標準的なBツリー方式と区別されます。HTreeインデックスはext3およびext4 Linuxファイルシステムで使用されており、2.5.40頃にLinuxカーネルに組み込まれました。 [ 2 ] HTreeインデックスにより、 Linux ext2ベースのファイルシステムのスケーラビリティが、実際的な制限である数千ファイルから、ディレクトリあたり数千万ファイルの範囲まで向上しました。
歴史
HTreeインデックスデータ構造とアルゴリズムは、2000年にDaniel Phillipsによって開発され、2001年2月にext2ファイルシステム向けに実装されました。2002年にChristopher LiとAndrew Mortonによって2.5カーネルシリーズでext3ファイルシステムへの移植が行われ、ジャーナルベースのクラッシュ整合性が追加されました。HTreeは、若干の改良を経て、Linux 3.xxカーネルシリーズのext4でも引き続き使用されています。
使用
- ext2 HTreeインデックスは元々ext2用に開発されましたが、パッチは公式ブランチには反映されませんでした。ext2ファイルシステムの作成時にdir_index機能を有効にすることはできますが、ext2コードはこれを反映しません。
- ext3 HTree インデックスは、dir_index 機能が有効になっている場合に ext3 で使用できます。
- ext4では、 HTreeインデックスがデフォルトで有効になっています。この機能はLinuxカーネル2.6.23で実装されています。HTreeインデックスは、ファイルがinodeに格納される4つのエクステントよりも多くのエクステントを必要とする場合に、ファイルエクステントにも使用されます。ext4のlarge_dir機能はLinuxカーネル4.13で実装されています。
PHツリー
PHTree（物理的に安定したHTree）は、後継として開発された派生版です。[ 3 ]書き込み乗算を除くHTreeの既知の問題をすべて修正しています。Tux3ファイルシステムで使用されています。[ 4 ]
参考文献
- ^ Mingming Cao. 「ディレクトリのインデックス作成」（PDF） . Linux 2.6 の機能.
- ^ [email protected]. 「ext3 インデックスディレクトリ (htree) のサポートを追加する」。
- ^ 「PHTreeのデザインリフレッシュ」 2013年1月4日。
- ^ 「Tux3 バージョン管理ファイルシステム」 。 2015年1月13日時点のオリジナルよりアーカイブ。2014年12月28日閲覧。
外部リンク
