ext3のパーティションフォーマットでB木が使われているそうなのですが、階層構造を表した時親に値が複数存在するB木だとどこか変だと思うのですが本当にB木が使われているのですか
自分のイメージでは木構造でフォルダを表しファイルをB木で表すことやDBMSの索引や検索機能では有効に働くと思いますが実際はどのようになっているのですか
-
「ファイルシステムのデータ構造について」では漠然としていると感じたため、本文を参考にタイトルを変更しました。– unaristCommented 2015年8月11日 0:28
-
「どこか変だと思う」と思っていらっしゃる内容をもう少し掘り下げて書いてみてくださいますか?– take88Commented 2015年8月11日 3:12
-
@take88 親に値が複数存在する事です私のフォルダには一番上まで上がれば一つの点にたどり着きますそこに複数のフォルダも置けますいくら増やしたとしてもB木のような挙動を見せません– todoCommented 2015年8月11日 6:05
コメントを追加
|
1 件の回答
うまく説明できる自身がないので回答になっているか不安ですが・・・。
フォルダとファイルの構造が 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.