質問: ext3のパーティションフォーマットでB木が使われているそうなのですが、階層構造を表した時親に値が複数存在するB木だとどこか変だと思うのですが本当にB木が使われているのですか 自分のイメージでは木構造でフォルダを表しファイルをB木で表すことやDBMSの索引や検索機能では有効に働くと思いますが実際はどのようになっているのですか
回答: うまく説明できる自身がないので回答になっているか不安ですが・・・。 フォルダとファイルの構造が B-Tree なのではなく、ディレクトリ内のファイルのブロックを探索するときに B-Tree (HTree) 探索を行います。 ext3はdir_indexを有効にするとディレクトリ内のファイル探索にhashed b-tree (HTreeとも言います) を使いますので、無効な場合の線形探索に比べると、ファイルが多くなるほど探索結果がでるまでの時間が短くなります。 tune2fs のManページでは次のように説明されています。 ``` dir_index Use hashed b-trees to speed up lookups in large directories. ```