ext3ファイルシステムでB木がどのように使われているのか

投稿者: Anonymous

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.
回答者: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *