B-Tree
B 木は自己平衡な多分岐探索木であり、各ノードが複数のキーと子へのポインタを保持し、ほぼ O(1) のファンアウトで O(log N) の検索を保証する。
目的
データベースインデックスの中核データ構造を理解し、その読み取り・書き込み性能とページ充填率を分析する。
メカニズム
次数 m の B 木は各ノードが最大 m 個、最小 ceil(m/2) 個の子を持つ。挿入時の分割と削除時の統合で平衡を保ち、すべての葉は同じ深さになる。ノードサイズはデータベースのページ I/O（例: 16KB）に合わせ、大きなファンアウトにより木の高さが低く保たれる（3〜4 層で TB 級を索引できる）。
ユースケース
- インデックスのデータ構造
- データベースの内部構造
- ストレージの最適化