14265


ext3のパーティションフォーマットでB木が使われているそうなのですが、階層構造を表した時親に値が複数存在するB木だとどこか変だと思うのですが本当にB木が使われているのですか  
自分のイメージでは木構造でフォルダを表しファイルをB木で表すことやDBMSの索引や検索機能では有効に働くと思いますが実際はどのようになっているのですか


CC BY-SA 3.0
2015-08-10T23:58:40.230
14251
2015-08-11T06:48:38.833
2015-08-11T00:21:50.757
8000
10455
question
データ構造 filesystems
ext3ファイルシステムでB木がどのように使われているのか


うまく説明できる自身がないので回答になっているか不安ですが・・・。

フォルダとファイルの構造が B-Tree なのではなく、ディレクトリ内のファイルのブロックを探索するときに B-Tree (HTree) 探索を行います。

ext3はdir_indexを有効にするとディレクトリ内のファイル探索にhashed b-tree (HTreeとも言います)
を使いますので、無効な場合の線形探索に比べると、ファイルが多くなるほど探索結果がでるまでの時間が短くなります。

tune2fs のManページでは次のように説明されています。

[code]

       dir_index
                          Use hashed b-trees to  speed  up  lookups  in  large directories.
    
[/code]


CC BY-SA 3.0
2015-08-11T06:48:38.833
14265
2015-08-11T06:48:38.833
5008
14251
answer