BツリーとB+ツリーの仕組みとデータベースインデックスへの応用
概要¶
データベースのインデックスが BツリーやB+ツリーで実装されている理由を、ディスク構造から段階的に説明。線形探索の限界 → インデックスの必要性 → 多レベルインデックス → M-way探索木 → Bツリー（ルール付きM-way木）→ B+ツリー、という流れで本質を理解できる。
詳細¶
なぜディスク上の探索が遅いのか¶
ディスクの構造：
┌─────────────────────────────────────┐
│ Track 1: [Block][Block][Block]... │
│ Track 2: [Block][Block][Block]... │
│ Track N: [Block][Block][Block]... │
└─────────────────────────────────────┘
データ取得フロー：
[アプリ] → [RAM（処理）] ← [ディスク（保存）]
↑
ブロック単位でデータを転送
- ディスクはブロック単位（例: 812バイト）でデータを読む
- 1行100バイトのテーブル → 1ブロックに8行格納
- 1000行 → 約125ブロックを線形スキャン → 非常に遅い
インデックスで探索を高速化する¶
インデックスとは¶
テーブル（ディスク上）:
Row 1: id=1, name="Alice", ... ← 100 bytes
Row 2: id=2, name="Bob", ...
...
インデックス（別ブロックに保存）:
id=1 → ポインタ → Row 1のブロックアドレス
id=2 → ポインタ → Row 2のブロックアドレス
...
| 項目 | 値 |
|---|---|
| インデックスの1エントリサイズ | ID(10B) + ポインタ(6B) = 16B |
| 1ブロックに収まるエントリ数 | 812 ÷ 16 ≈ 50エントリ |
| 1000行分のインデックスブロック数 | 1000 ÷ 50 = 20ブロック |
| 検索コスト | インデックス20ブロック + データ1ブロック = 21ブロック |
→ 125ブロックから21ブロックに削減できるが、まだ改善の余地がある。
多レベルインデックス（Multi-Level Index）¶
レベル2（スパースインデックス）:
┌──────────────────────┐
│ [10] [30] [50] ... │ ← 上位インデックス
└───┬──────┬──────┬────┘
↓ ↓ ↓
レベル1（デンスインデックス）:
[1..20] [21..40] [41..60] ← 下位インデックス
↓ ↓ ↓
実データブロック（テーブル）
インデックスを上下逆にするとツリー構造に見える。 インデックスが自動で成長・縮小できれば理想 → Bツリー誕生の背景
M-Way 探索木¶
BST（二分探索木）の拡張で、1ノードに複数のキーを持てる木。
- BST: 1ノード1キー → 木の高さが深くなる
- M-Way: 1ノードがm-1個のキーとmポインタ → 木の高さを抑えられる
なぜ m-1 キー？
ポインタ数 m に対して、境界として必要なキー数は m-1 個
例）4ポインタ → 3キー (K1, K2, K3)
P1(<K1) | K1 | P2(K1..K2) | K2 | P3(K2..K3) | K3 | P4(>K3)
問題点：挿入ルールがないため木が偏る（最悪ケースで線形リスト化）
Bツリー：ルール付きM-Way探索木¶
Bツリー = M-Way探索木 + 以下のルール
1. 各ノード（ルート除く）は最低 ⌈m/2⌉ 個の子ノードを持つ
2. ルートは最低2つの子ノードを持つ
3. すべての葉ノードは同じレベルにある（完全バランス）
4. 挿入はボトムアップで行われる（オーバーフロー時にスプリット）
Bツリーの挿入例（4-way / m=4）¶
初期状態（空）に 10, 20, 40 を挿入：
[10 | 20 | 40]
50を挿入 → オーバーフロー → スプリット：
[40]
/ \
[10|20] [50]
60, 70 を挿入：
[40]
/ \
[10|20] [50|60|70]
80を挿入 → 右ノードがオーバーフロー → スプリット：
[40 | 70]
/ | \
[10|20] [50|60] [80]
B+ツリー：リンクリスト付きBツリー¶
| 特性 | Bツリー | B+ツリー |
|---|---|---|
| レコードポインタ | 全ノードが持つ | 葉ノードのみが持つ |
| 内部ノードのキー | データのコピーなし | 葉ノードにコピーが存在 |
| 葉ノードの連結 | なし | 双方向リンクリスト |
| 範囲検索 | ツリーを複数回走査 | リンクリストを辿るだけ |
B+ツリーの葉ノード（リンクリスト構造）:
[1→ptr][5→ptr][10→ptr] → [15→ptr][20→ptr][30→ptr] → [40→ptr]...
↑葉ノード1 ↑葉ノード2 ↑葉ノード3
- スパースインデックス（内部ノード）：木の探索に使用
- デンスインデックス（葉ノード）：実データへのポインタを保持
範囲クエリ（
WHERE id BETWEEN 10 AND 30）は葉ノードのリンクリストを辿るだけで効率的に処理できる。
まとめ：データベースとの関係¶
ディスクI/O削減の進化：
線形スキャン → 単一インデックス → 多レベルインデックス → Bツリー → B+ツリー
O(N) O(N/50) O(log N) O(log N) O(log N + range)
PostgreSQL、MySQL（InnoDB）、SQLite などの主要DBはB+ツリーをデフォルトインデックスとして採用している。
なぜ重要か / いつ使うか¶
- 「なぜインデックスを張ると速くなるのか」を原理から説明するとき
- データベース設計面接でインデックスの質問が来たとき
- スロークエリを調査してインデックス戦略を議論するとき
EXPLAIN ANALYZEの結果を読み解くための下地として