はじめに
この記事では、MySQL InnoDBのB+Treeインデックスの内部実装を深掘りします。
以前の記事（InnoDB B+Treeの仕組みを日本語でわかりやすく解説、記事ID:370）では概要を紹介しました。今回はMySQL 8.0のソースコード（storage/innobase/btr/）を追いながら、以下を解説します：
- Clustered IndexとSecondary Indexの違い
- B+Treeのページ（ノード）構造
- 検索・挿入・削除の内部動作
- ノード分割とマージ
- ロック（Latch）戦略
元ネタは公式ドキュメントとソースコードです。
そもそもB+Treeって何？
B+Treeは「大量のデータから目的のレコードを高速に見つける」ためのデータ構造です。
たとえるなら辞書です： – 辞書の「あ行」「か行」…のインデックスタブ = 内部ノード（Internal Node） – 実際の単語が載っているページ = リーフノード（Leaf Node）
B+Treeの特徴： – 全データはリーフノードにある（内部ノードはキーとポインタだけ） – リーフノード同士がリンクリストで繋がっている（範囲検索が高速） – 木の高さが均一（どのキーも同じ回数のI/Oでたどり着ける）
[Internal Node]
| 10 | 20 | 30 |
/ | | \
[Leaf] [Leaf] [Leaf] [Leaf]
1,3,5,8 10,12,15 20,22,25 30,35,40
↔ ↔ ↔
（リーフ同士が双方向リンクリストで接続）InnoDBのデフォルトページサイズは16KB。1ページに数百〜数千のキーが入るため、数百万行のテーブルでも木の高さは通常3〜4段で済みます。
Clustered IndexとSecondary Index
InnoDBのインデックスには2種類あります。これがInnoDBの最大の特徴です。
Clustered Index（クラスタードインデックス）
テーブルのデータそのものがB+Treeのリーフノードに格納されます。テーブル = Clustered Indexです。
Clustered Index（PRIMARY KEY = id）:
[id: 10 | 20]
/ \
[id:1, name:"Alice", age:25] [id:10, name:"Bob", age:30]
[id:3, name:"Carol", age:22] [id:12, name:"Dave", age:28]
↑ リーフに行データ全体が入る- PRIMARY KEYがあればそれがClustered Indexになる
- PRIMARY KEYがなければ、最初のUNIQUE NOT NULLインデックスが使われる
- どちらもなければ、InnoDBが内部的に6バイトの隠しROW_IDを生成する
Secondary Index（セカンダリインデックス）
Clustered Index以外のインデックスです。リーフノードにはPRIMARY KEYの値が格納されます。
Secondary Index（KEY = name）:
[name: "Carol" | "Dave"]
/ \
[name:"Alice", PK:1] [name:"Carol", PK:3]
[name:"Bob", PK:10] [name:"Dave", PK:12]
↑ リーフにはPK値だけ（行データはない）Secondary Indexで検索すると、まずPK値を取得し、次にClustered Indexを引いて行データを取得します。この2段階の検索をブックマークルックアップ（または「テーブルに戻る」）と呼びます。
PostgreSQLとの違い
PostgreSQLにはClustered Indexの概念がありません。テーブル（Heap）とインデックスは完全に分離しています。
| InnoDB | PostgreSQL | |
|---|---|---|
| テーブル構造 | Clustered Index（B+Tree） | Heap（順序なし） |
| セカンダリインデックスのリーフ | PK値 | ctid（物理位置） |
| テーブルへの戻り | PK→Clustered Index検索 | ctid→Heap直接アクセス |
PostgreSQLのctid（物理位置）による直接アクセスはInnoDBのPK検索より高速ですが、VACUUMでctidが変わるとインデックスの更新が必要になるトレードオフがあります。
ページ（ノード）の内部構造
B+Treeの各ノードは1つのページ（16KB）です。ページの内部構造を見てみましょう。
ページレイアウト
- FIL Header (38B) ファイル管理情報
- Page Header (56B) ページ管理情報
- Infimum Record 最小の仮想レコード
- Supremum Record 最大の仮想レコード
- User Records 実際のレコード（↓方向に成長）
- Record 1 → Record 2 → Record 3 → …
- （Free Space）
- Page Directory 検索用スロット（↑方向に成長）
- FIL Trailer (8B) チェックサム
重要なポイント：
- Infimum / Supremum：ページ内の最小・最大を表す仮想レコード。レコードの単方向リンクリストの始点と終点
- User Records：キー順にリンクリストで繋がっている（物理的な並び順ではない）
- Page Directory：ページ内の二分探索用。4〜8レコードごとに1つのスロットを持つ
- Free Space：User Recordsは上から下へ、Page Directoryは下から上へ成長し、中央で出会う
レコードの検索（ページ内）
ページ内のレコード検索は2段階です：
1. Page Directoryで二分探索 → 大まかな位置を特定
2. レコードのリンクリストを線形探索 → 正確なレコードを特定Page Directoryのスロットは4〜8レコードごとなので、線形探索は最大8レコード分で済みます。
B+Treeの検索（ルートからリーフまで）
/* btr_cur_search_to_nth_level の簡略版 */
page = root_page;
for (level = tree_height; level > 0; level--) {
/* ページ内でキーを検索 */
slot = page_directory_binary_search(page, key);
record = linear_search_from_slot(slot, key);
/* 内部ノード: レコードが指す子ページへ移動 */
child_page_no = record->child_page_no;
page = buf_page_get(child_page_no); // Buffer Poolから取得
}
/* level == 0: リーフノードに到達 */挿入とノード分割
通常の挿入
リーフページに空きがあれば、キー順の正しい位置にレコードを挿入するだけです。
挿入前: [1] → [3] → [5] → [8]
INSERT key=4
挿入後: [1] → [3] → [4] → [5] → [8]物理的にはページ内のFree Space領域にレコードを書き、リンクリストのポインタを更新します。
ページ分割（Page Split）
ページが満杯のとき、新しいページを確保して分割します。
分割前:
Page A: [1, 3, 5, 8, 10, 12, 15] ← 満杯
INSERT key=7
分割後:
Page A: [1, 3, 5, 7, 8]
Page B: [10, 12, 15] ← 新しいページ
親ノード: [..., 10, ...] ← 分割点のキーを親に挿入InnoDBの分割ポイントは単純な中央分割ではありません。挿入パターンを考慮した最適化があります：
- 順次挿入（AUTO_INCREMENT等）：最後のレコードの直後で分割（新ページにほぼ空きが残る）
- ランダム挿入：ページの中央付近で分割
/* btr_page_get_split_rec の簡略版 */
if (insert_point == page_get_supremum_rec(page)) {
/* 末尾への挿入 → 挿入レコード自体を分割点にする */
split_rec = insert_rec;
} else {
/* それ以外 → ページの中央付近で分割 */
split_rec = page_get_middle_rec(page);
}分割のコスト
ページ分割は以下の操作を伴うため、コストが高いです：
- 新ページの確保
- レコードの移動
- 親ノードへのキー挿入（親も満杯なら連鎖分割）
- リーフのリンクリスト更新
- これら全体が1つのMTR（Mini-Transaction）としてアトミックに実行
削除とマージ
レコードの削除
InnoDBの削除は2段階です：
1. DELETE Mark: レコードに削除フラグを立てる（論理削除）
→ この時点ではレコードはページに残っている（MVCC用）
2. Purge: 不要になったレコードを物理的に削除
→ バックグラウンドのPurgeスレッドが実行ページマージ
Purge後にページの使用率が低くなると、隣接ページとのマージが検討されます。
マージ前:
Page A: [1, 3] ← 使用率が低い
Page B: [10, 12, 15]
マージ後:
Page A: [1, 3, 10, 12, 15] ← Page Bの内容を吸収
Page B: （解放）
親ノード: キー10を削除マージの閾値はMERGE_THRESHOLD（デフォルト50%）で制御できます：
-- テーブル単位で設定
CREATE TABLE t1 (...) COMMENT='MERGE_THRESHOLD=40';
-- インデックス単位で設定
CREATE INDEX idx1 ON t1(col1) COMMENT 'MERGE_THRESHOLD=30';ロック（Latch）戦略
B+Treeは複数スレッドが同時にアクセスします。ページの分割や削除が起きている最中に別のスレッドが検索すると、不整合が起きます。InnoDBはどうやって安全性と並列性を両立しているのでしょうか？
基本戦略：楽観的ロック
InnoDBはまず楽観的（Optimistic）にロックを取ります：
楽観的な読み取り:
1. ルートからリーフまでS-latch（共有ロック）で降りる
2. 各ページのS-latchは次のページに移る前に解放
→ 同時に複数スレッドが読み取り可能
楽観的な書き込み:
1. ルートからリーフまでS-latchで降りる
2. リーフページだけX-latch（排他ロック）に昇格
→ ページ分割が不要な場合はこれで十分悲観的ロック（ページ分割が必要な場合）
楽観的な書き込みでページが満杯だった場合、悲観的（Pessimistic）にやり直します：
悲観的な書き込み:
1. B+Treeのインデックス全体にSX-latch（準排他ロック）
2. ルートからリーフまで降りながら、分割に関わるページにX-latch
3. ページ分割を実行
4. ロック解放SX-latch（MySQL 5.7〜）は「読み取りは許可するが、他の書き込みはブロックする」ロックです。これにより、ページ分割中でも検索は継続できます。
ロックの種類
| ロック | 用途 | 他スレッドの読み取り | 他スレッドの書き込み |
|---|---|---|---|
| S-latch | 検索 | ✅ 許可 | ❌ ブロック |
| X-latch | ページ変更 | ❌ ブロック | ❌ ブロック |
| SX-latch | ツリー構造変更 | ✅ 許可 | ❌ ブロック |
まとめ
| トピック | ポイント |
|---|---|
| テーブル構造 | テーブル自体がClustered Index（B+Tree） |
| Secondary Index | リーフにPK値を格納。検索時はClustered Indexへの2段階アクセス |
| ページ構造 | 16KB。レコードはリンクリスト、Page Directoryで二分探索 |
| ノード分割 | 挿入パターンに応じた分割点の最適化 |
| 削除 | 2段階（DELETE Mark → Purge）。使用率低下でマージ |
| ロック | 楽観的→悲観的のエスカレーション。SX-latchで読み取りと構造変更を両立 |
次回はPostgreSQLのB-tree / GiST / GINを同じ切り口で解説し、InnoDBとの設計思想の違いを比較していきます。