B-treeとファイルシステムインデックス構造

なぜ二分木でなくB-treeなのか

メモリ内の探索なら二分探索木（BST）で十分ですが、ファイルシステムのインデックスは ディスク上 に置かれます。ここで支配的なコストはCPU比較ではなく ブロックI/Oの回数 です。HDDのシーク、SSDでも1ブロック読み出しのレイテンシは、メモリアクセスより桁違いに大きい。木の高さがそのままI/O回数になるため、いかに木を浅くするかが設計の中心になります。

二分木は要素数 n に対し高さが log2(n)、つまり分岐数が2しかありません。これに対し B-tree は1ノードに多数のキーと子ポインタを詰め、分岐数（fanout）を数百に上げます。分岐数を b とすると高さは log_b(n) に縮み、I/O回数が劇的に減ります。

二分木 (fanout 2)         B+Tree (fanout 500)
  高さ ≈ log2(n)            高さ ≈ log500(n)
  n=10^9 → 約30段           n=10^9 → 約4段
  → 30回のブロック読み       → 4回のブロック読み

要点は、ノードのサイズを ディスクブロック（典型的に4KiB）にぴったり合わせる ことです。どうせ1ブロックを読むなら、その1ブロックに入るだけのキーを詰めて一度に多くの分岐を得る方が得です。これがB-tree系がストレージ向け索引の標準である理由です。

ext4のHTree：ハッシュ化したディレクトリ索引

ext4 以前の伝統的なUNIXディレクトリは、エントリ（ファイル名とinode番号の対）を 線形リスト で持ちました。open("dir/file") のたびに先頭から名前を1つずつ比較するため、エントリ数 n に対し探索は O(n)。数万ファイルを置くと1回の検索が重くなります。

ext4 は HTree（Hashed Tree） でこれを解決します。ファイル名そのものをキーにすると長さがばらつき木が偏るため、名前を ハッシュ値 に変換し、その固定長ハッシュをキーにした浅い木で索引します。

ディレクトリブロック構造（HTree）
  ルートブロック : [ハッシュ範囲 → 子ブロック] のインデックス
        │
        ▼   名前 "report.txt" を hash() でハッシュ化
  リーフブロック : 実際の dirent（名前 + inode番号）が線形に並ぶ

検索はファイル名をハッシュし、ルートでそのハッシュが属する範囲の子をたどり、葉ブロック内だけを線形走査します。HTreeは互換性のため 木の深さを1〜2段に固定 しており、最初のブロックは旧来の線形ディレクトリと同じ形式（先頭エントリがインデックスへのフラグを兼ねる）を装うため、HTree非対応の古いツールからも壊れずに見えます。

XFSのB+Tree：空き領域・inode・ディレクトリを索引

XFS はほぼすべての管理構造を B+Tree で持つ徹底ぶりが特徴です。ボリュームは Allocation Group（AG） に分割され、各AGが独立したB+Tree群を持ちます。

空き領域を 開始ブロック順とサイズ順の2本 で持つのが巧妙です。ファイル削除でできた空きを隣接する空きと結合するには開始位置順が、「k ブロック以上の連続空きを探す」最適合わせには大きさ順が効きます。同じ集合を異なるキーで二重に索引することで、両方の操作を O(log n) にしています。

XFS のディレクトリはサイズに応じて形態が 段階的に昇格 します。小さければinode内インライン、中規模は単一ブロックの線形、大きくなると名前ハッシュをキーにしたB+Tree索引付きの形式へ移行します。データ量に対して常に適切なコストを保つ設計です。

BtrfsのB-tree：すべてをひとつの木で表す

Btrfs はさらに抽象化を進め、ファイルシステム全体を コピーオンライト型のB-tree 群で表現します。ファイルツリー、エクステントツリー、チェックサムツリーなど役割別の木があり、それらを上位のルートツリーが束ねます。詳細は CoW型ファイルシステム を参照してください。

Btrfsの妙は キーの汎用設計 にあります。木のキーは (objectid, type, offset) の3要素タプルで、これ1つでファイルのメタデータ、ディレクトリエントリ、エクステント情報を統一的に表します。

Btrfsのキー = (objectid, type, offset)
  例: inode item        → (inode番号, INODE_ITEM, 0)
      ディレクトリエントリ → (親inode, DIR_ITEM, 名前のハッシュ)
      ファイルのエクステント → (inode番号, EXTENT_DATA, ファイル内オフセット)

このキーは ソート順 に並ぶため、あるinodeに属する全項目（メタデータ→ディレクトリ→データ）がB-tree上で物理的に近接します。1回の範囲走査でファイルの関連情報をまとめて取得できます。ディレクトリは、名前ハッシュをキーにした DIR_ITEM（名前→inodeの一致検索用）と、連番をキーにした DIR_INDEX（readdir の順次列挙用）の2種類の項目で索引され、用途に応じて木を走査します。ext4のHTreeが「ディレクトリ専用の索引」だったのに対し、Btrfsは「索引の仕組みそのものを全構造で共有」しています。

エクステントの索引：範囲をどう木に載せるか

ファイルの中身は エクステント（連続ブロックを「論理オフセット＋長さ＋物理位置」で表す範囲）で管理されます。1ファイルが多数のエクステントに断片化したとき、論理オフセットから物理位置を引く写像を高速化するのも、やはり木です。

ext4 は inode 内に エクステントツリー を埋め込みます。inodeには4エントリ分の領域があり、断片化が少なければ木を作らずここに収まります。足りなくなると、葉に実エクステント、内部ノードにインデックスを置くB+Tree状の木へ拡張されます。

エクステントツリーのキー = ファイル内の論理ブロック番号
  内部ノード: [logical 0 →子A] [logical 10000 →子B] ...
                       │
                       ▼  探したい論理ブロックが属する範囲へ降りる
  葉ノード:   [logical 0,  len 1000, phys 50000]
             [logical 1000,len 500,  phys 80000]

キーが 論理オフセット順にソート されているため、mmap やシーケンシャル読みで「論理ブロック x はどこか」を O(log n) で引け、さらに葉が連続するので前方読みのプリフェッチも効きます。XFSも同様にエクステントマップをB+Treeで持ち、断片化したファイルでも写像コストを対数に抑えます。エクステント方式の基礎は ジャーナリングファイルシステム でも触れています。

ディスク向けノードサイズ設計

最後に、なぜノードを特定サイズに揃えるのかを定量的に押さえます。1ノードに入るキー数は次で決まります。

fanout ≈ ノードサイズ / (キー長 + ポインタ長)
  例: 4KiB ノード, キー16B + ポインタ8B = 24B
      → 約 170 分岐
  高さ h で表せる葉数 ≈ fanout^h
      170^3 ≈ 490万,  170^4 ≈ 8.4億

分岐数を上げれば木は浅くなりますが、ノードを大きくしすぎると1回のI/Oで読む無駄が増え、ノード内の二分探索コストや、更新時に書き戻すブロックも大きくなります。そこで ノードサイズ＝ファイルシステムブロックサイズ（または整数倍） に合わせ、I/O単位とノードを一致させるのが定石です。

まとめ

• ファイルシステムの索引は I/O回数＝木の高さ を最小化するため、分岐数の高いB-tree／B+Treeを使い探索を O(log n) に抑える。
• ext4 は HTree（名前ハッシュをキーにした浅い木）でディレクトリを索引し、XFS/Btrfs は キー順ソートのB+Tree／B-tree で空き領域・inode・ディレクトリ・エクステントを統一的に索引する。
• エクステント は論理オフセットをキーにした木で物理位置へ写像し、断片化しても対数コストを保つ。
• ノードを ブロックサイズに揃えて 分岐数を最大化し、分割・結合の不変条件で木の高さと充填率を保証するのが、ディスク向けノード設計の核心。
• 関連構造は CoW型ファイルシステム と ジャーナリングファイルシステム、基礎は ファイルシステム も参照。