DB インデックスの中身を理解する ~ B-tree / B+ Tree と MySQL・PostgreSQL・NoSQL の実装差
RDBMS の主役インデックスである B+ Tree を、二分探索木との違い・ディスク IO 前提の設計・分割/マージの挙動から解説。InnoDB のクラスタードインデックス、PostgreSQL の heap+index 構造、そして NoSQL (MongoDB / Cassandra / DynamoDB / CouchDB) での採用状況まで整理する。
なぜ B-tree / B+ Tree を学ぶのか
CREATE INDEX を書いたとき、DB の中で何が起きているのか。
答えは 「B+ Tree が組み立てられる」 で、
MySQL InnoDB も PostgreSQL も、既定のインデックスは B+ Tree 系 です。
さらに MongoDB (WiredTiger) や CouchDB のような NoSQL でも B-tree 系が使われており、
「永続化ストアの索引といえば B+ Tree」 と言える状況が今も続いています。
[[binary-tree]] で扱った二分探索木 (BST) はメモリ上では高速ですが、 ディスク IO を前提にすると致命的に遅い。 その問題を解くのが B-tree で、 さらに範囲検索に強く作り直したのが B+ Tree です。 本稿では、
- B-tree と B+ Tree の違い (本質は 「葉だけに値を置くか」)
- ディスク IO を減らすための fanout 設計
- 分割 (split) / マージ (merge) の挙動
- MySQL InnoDB の クラスタードインデックス と PostgreSQL の heap + index の違い
- NoSQL (MongoDB / Cassandra / DynamoDB / CouchDB / Lucene) での採用状況と LSM Tree との対比
を順に整理します。
前提: ディスク IO は 「桁違いに遅い」
B-tree 設計の出発点は 1972 年の Bayer & McCreight の論文で、 「ディスクを 1 回読むコスト」 ≫ 「CPU で N 回比較するコスト」 という非対称が前提です。
現代 (NVMe SSD) でも感覚としては、
| ストレージ | 1 回のランダム read | L1 比 |
|---|---|---|
| L1 cache | ~1 ns | 1× |
| メモリ | ~100 ns | ~100× |
| NVMe SSD | ~100 µs | ~100,000× |
| HDD | ~10 ms | ~10,000,000× |
つまり 「ディスクを読む回数を減らせば、他は多少無駄でも勝つ」。 B-tree はこの前提で、「1 ノード = 1 ページ (8KB 〜 16KB)」 単位で読み書きします。
二分探索木ではなぜダメか
BST は 1 ノードに値 1 個しか持ちません。
1 億件を保持すると木の高さは約 27 (= log2(10^8))。
毎階層で 1 ページ読むと ディスク IO が 27 回 になります。
B-tree は 1 ノードに数百個のキーを詰め込み (= fanout を上げる)、 高さ 3〜4 で 1 億件を捌けるようにします。 IO が 27 回 → 3〜4 回 で、これが数桁の速度差になります。
B-tree と B+ Tree の違い
B-tree (元祖)
- 各ノードがキーと値 (レコードへのポインタ) の両方を持つ
- 全ノードに値がある ので、中間ノードでヒットすれば浅い探索で済む
- ただし ノードあたりに詰めるキー数が減る (値も一緒に持つため)
B+ Tree (DB で主流)
- 値 (または値へのポインタ) は葉ノードだけに置く
- 中間ノードは 「キー + 子へのポインタ」 だけなので、 同じページサイズにより多くのキーを詰められる → fanout が上がる → 木が低くなる
- 葉ノード同士を 双方向リンクリスト で繋ぐ
→ 範囲検索
WHERE created_at BETWEEN ? AND ?が 葉の横移動 だけで済む
[ 50 | 100 ] ← 内部ノード (キーのみ)
/ | \
[10,30] [60,80] [120,150] ← 内部ノード
/... /... /...
葉→ [1,5,10] ⇄ [11,20,30] ⇄ [51,55,60] ⇄ ... ← 葉は双方向リンク
↓ ↓ ↓
値 値 値
実務インパクト: ORDER BY id LIMIT 100 やレンジスキャンが速いのは、
この 「葉の横移動」 のおかげ。
範囲検索・ソート・GROUP BY の多くが B+ Tree の恩恵を受けます。
ノードの構造 (ページレイアウト)
InnoDB のページ (既定 16KB) の中身は概ねこんなイメージです。
┌──────────────────────────────────────┐
│ ページヘッダ (チェックサム等) │
├──────────────────────────────────────┤
│ スロット: ソート済みキー配列 │
│ [ key1 | key2 | key3 | ... ] │
├──────────────────────────────────────┤
│ ペイロード (値 or 子ページ番号) │
│ [ rec1 | rec2 | rec3 | ... ] │
├──────────────────────────────────────┤
│ 空き領域 (分割判定に使う) │
├──────────────────────────────────────┤
│ ページフッタ (次/前ページへのリンク) │
└──────────────────────────────────────┘
1 ページで扱えるキー数を fanout (次数) と呼び、 これが大きいほど木が低くなります。 InnoDB では経験的に 1 ノードあたり数百 〜 千のキーを持ち、 3 段 (root / 中間 / 葉) で 数億行 を捌けます。
挿入 (split): 「満員なら 2 つに割る」
B+ Tree の挿入は再帰的ですが、本質は 1 行:
葉ノードに空きがあれば単に追加。 満員なら中央値を親に昇格させて 2 ページに分割。
擬似コードで骨格だけ
func (t *BPlusTree) Insert(k Key, v Value) {
leaf := t.findLeaf(t.root, k)
leaf.add(k, v) // ソート位置に挿入
if leaf.isOverflow() { // 1 ページに収まらない
right := leaf.splitHalf() // 後半を別ページへ
promote := right.firstKey()
t.insertToParent(leaf, promote, right) // 親に中央値を昇格
}
}
伝播
親もオーバーフローすれば さらに上に split を伝播。 最終的に ルートが split されたとき、新しい root が 1 段上に生まれる ので、 B+ Tree の高さは root split 時のみ増える。 全葉から root までの距離が常に等しい (= 完全バランス木) のはこのためです。
現場で起きること
- ランダム PK (UUIDv4 など) は挿入位置が毎回ばらけて 大量の split と IO を発生させる。 Twitter Snowflake や UUIDv7 のような 時系列 ID が好まれるのはこの理由。
- 昇順 PK (AUTO_INCREMENT) は常に右端に追加される → split が 右端のみで済み効率的。 これが MySQL で AUTO_INCREMENT PK が推奨される技術的根拠。
削除 (merge / redistribute): 「スカスカになったら統合」
削除は split の逆:
- 葉から値を除去
- 使用率が閾値 (多くの実装で 50%) を下回ったら、
- 隣の兄弟から借りる (redistribute) か、兄弟とマージする
- マージが伝播してルートが空になれば木の高さが 1 下がる
ただし 実際の DBMS は厳密にマージを走らせないことが多い です。
InnoDB も PostgreSQL も、削除で空いたページは 「空き領域」 として再利用するだけで、
積極的な縮退はしません (OPTIMIZE TABLE / VACUUM FULL で初めて再構築)。
これが 「インデックスがどんどん肥大化する」 問題の原因。
検索と範囲検索
単一キー検索 — O(log_fanout n)
root → 中間 → 葉 と 3 回ページを読むだけ
fanout が 500 なら、log500(10^9) ≈ 3.4 で 数億件でも 3〜4 IO。
範囲検索 — 葉の横リンクをなぞる
SELECT * FROM orders
WHERE created_at BETWEEN '2026-01-01' AND '2026-03-31'
ORDER BY created_at;
B+ Tree なら:
- root → 葉で
2026-01-01の位置を 1 回だけ特定 (IO 3〜4 回) - そこから 葉を右に連続スキャン
2026-03-31を超えたら停止
ランダム IO が 1 回だけ、あとはシーケンシャル IO になるので、 範囲検索は DBMS の最大の得意分野になります。
MySQL (InnoDB) の実装 — クラスタードインデックス
InnoDB の最大の特徴は 主キーの B+ Tree が行本体そのもの であること (= クラスタードインデックス)。
PK B+ Tree (= テーブル本体)
葉ノード = 行データそのもの
[PK=1 | col_a=.. | col_b=.. | ... ]
[PK=2 | col_a=.. | col_b=.. | ... ]
...
Secondary Index (例: col_a)
葉ノード = col_a 値 + PK 値 (行本体へのポインタではない!)
[col_a='foo' | PK=42]
現場で効く帰結
- PK 検索は 1 回の B+ Tree 探索 で行まで取れる (最速)
- セカンダリインデックスだけだと、追加で PK の B+ Tree を再度辿る (=
JOINを内部で 1 回やっているのと同じ) → これが有名な カバリングインデックス の根拠 - PK を変更すると全セカンダリインデックスを書き換える 羽目になる → PK は不変であるべき
- PK がない / 不適切だと、InnoDB は 内部で 6 バイトの隠し ID を作って PK にする
PostgreSQL の実装 — heap + 非クラスタード B-tree
PostgreSQL は InnoDB と設計が大きく違います。
Heap (テーブル本体)
ページ単位で行が順不同に並ぶ (ヒープ)
各行には (block_number, offset) = CTID が付く
Index (B-tree)
葉ノード = キー + CTID
[key='foo' | CTID=(5, 3)]
- PK インデックスも普通のインデックスの一つ (特別扱いしない)
- 全インデックスの葉には CTID (heap 内の物理位置) が入っている
- PK を変更してもインデックス構造は壊れない (= PK 変更は InnoDB より軽い)
MVCC との結合
PostgreSQL は追記型 MVCC で、UPDATE 時に新しい行バージョンを別の heap 位置に書きます。 すると すべてのインデックスを新しい CTID で更新する必要がある。 この重さを緩和するのが HOT (Heap-Only Tuple) update で、 「インデックスで参照されていない列だけ更新」 かつ 「同一ページ内に新バージョンが入る」 ときは インデックス更新をスキップします。
Lehman & Yao の B-link Tree
PostgreSQL の B-tree は Lehman & Yao (1981) の B-link tree に基づいており、 各ノードに 「右隣へのポインタ」 を持ち、 書き込み中のノードを読み取りがロックせずに辿れる 設計。 これが PostgreSQL の高い並行性の一因です。
MySQL InnoDB vs PostgreSQL — 違いを一行で
| 観点 | InnoDB | PostgreSQL |
|---|---|---|
| テーブル本体の格納 | PK の B+ Tree の葉 | ヒープ (順不同) |
| PK の位置づけ | 特別 (クラスタードキー) | 普通のインデックスの一つ |
| セカンダリインデックスの葉 | PK 値 | CTID (物理位置) |
| PK 変更のコスト | 重い (全セカンダリ書換) | 軽い |
| UPDATE 時のインデックス更新 | 列が変われば更新 | HOT 以外は全インデックス更新 |
| 範囲スキャン | PK 順に葉を辿れば連続 IO | ヒープはランダム (ただし CLUSTER で整列可) |
両方とも B+ Tree 系 という共通点はありつつ、
テーブル本体と索引の関係 が根本的に違う。
これを知らないと 「PostgreSQL ではなぜ ORDER BY PK LIMIT が意外と遅いのか」 のような
挙動差が理解できません。
NoSQL での B-tree 採用状況
「NoSQL は B-tree を使わない」 は誤解で、実際は 用途によって使い分けられています。
B-tree 系を使う NoSQL
MongoDB:
インデックスは B-tree。ストレージエンジン WiredTiger も内部で B+ Tree を使っています。
範囲クエリ { field: { $gte: ... } } が速いのは RDBMS と同じ理由。
CouchDB: 全ドキュメントが B+ Tree で管理され、MVCC も B+ Tree に組み込まれています。 append-only な書き込みでツリーを更新する独特の設計。
DynamoDB:
内部実装は公開されていないものの、
パーティション内のアイテムはソートキーで B-tree 的に並び、
Query API での範囲取得が O(log n) + スキャン で成立する点は同じ構造を示唆。
Elasticsearch / Lucene: テキストの転置インデックスは別構造 (FST) ですが、 数値・日付・位置情報には BKD Tree (B+ Tree の多次元拡張) を使っています。
B-tree を使わない NoSQL — LSM Tree
一方、書き込みヘビー系の NoSQL は LSM Tree (Log-Structured Merge Tree) を採用:
- Cassandra、ScyllaDB ([[cassandra-data-structure-architecture]])
- HBase、BigTable
- RocksDB、LevelDB
- MongoDB の WiredTiger も LSM モードを選択可能
LSM Tree は 「書き込みを常にメモリの SSTable に append し、 バックグラウンドで compaction してソート済みファイルを作る」 方式。
| 観点 | B+ Tree | LSM Tree |
|---|---|---|
| 書き込み | ランダム IO (split あり) | 常に append — 書き込み圧倒的に速い |
| 読み込み | 1 回の木探索で決着 | 複数 SSTable を調べる (Bloom filter で緩和) |
| 空間効率 | 削除で空きが残りがち | compaction で再構築される |
| 得意分野 | 読み多め・範囲検索 | 書き込み多め・時系列ログ |
どちらが優れているかではなく、ワークロードで選ぶ。 検索・分析系なら B+ Tree、IoT のテレメトリ流し込みなら LSM Tree、が目安。
落とし穴とインデックス設計 Tips
1. ランダム PK (UUIDv4) は B+ Tree の敵
挿入位置が毎回ばらけて 右端以外でも split が起き、 インデックスがすぐ 70% 使用率くらいに落ちる。 → UUIDv7 (時刻順) や Snowflake のような単調増加 ID、 あるいは PK を bigint の AUTO_INCREMENT にし UUID は別カラムで持つ戦略を取る。
2. 「カーディナリティが低い列」 単独のインデックスは効かない
性別やフラグ列など、 値のバリエーションが数個しかない列に単独でインデックスを張っても、 B+ Tree をほぼ全走査することになり、オプティマイザは使わない選択をする。 → 複合インデックス で先頭列が高カーディナリティ、後続列でフィルタする設計に。
3. 複合インデックスは 「左端一致」
INDEX(a, b, c) は WHERE a = ?、WHERE a=? AND b=? では使えるが、
WHERE b = ? 単独では使えない。
B+ Tree 上で 左から辞書順にソート されているため。
4. インデックスは書き込みコスト
セカンダリインデックスが 10 個あるテーブルの INSERT は、
行本体 + 10 本の B+ Tree 更新。
「とりあえず足しておく」 インデックスは書き込み性能を確実に殺す。
使っていないインデックスは pg_stat_user_indexes / sys.schema_unused_indexes で定期的に棚卸し。
5. インデックス肥大化
前述のとおり、通常の削除では B+ Tree は縮まない。
長期運用でインデックスサイズが 2 倍、3 倍になることはザラ。
PostgreSQL なら REINDEX CONCURRENTLY、
MySQL なら OPTIMIZE TABLE で定期的な再構築を計画に入れる。
6. NULL の扱いは DBMS で違う
- PostgreSQL: NULL も B-tree に含まれ、
IS NULLもインデックスで引ける - MySQL InnoDB: NULL も入るが、
IS NULLの最適化は版によって挙動差 - Oracle: NULL をインデックスに含まない (歴史的仕様)
7. 書き込みヘビーなら B+ Tree より LSM の選択肢
秒間数万件のテレメトリを RDBMS に突っ込んで 「インデックスが追いつかない」 と悩む前に、 Cassandra / ScyllaDB など LSM Tree 系を検討する選択肢を知っておく。 RDBMS 側で踏ん張るなら、挿入時のインデックスを最小化し、 バッチで再構築する ETL 設計に寄せる。
まとめ: RDBMS のインデックスの中身は B+ Tree で、 MySQL InnoDB と PostgreSQL は同じ B+ Tree 系ながら 「テーブル本体と索引の結び方」 が根本的に違う。 NoSQL でも MongoDB / CouchDB / Lucene の数値型などは B-tree 系を使う一方、 書き込みヘビー系 (Cassandra / HBase / RocksDB) は LSM Tree で別の最適解を取る。
「CREATE INDEX の中身は B+ Tree、
split / merge / fanout で IO が決まる」
という視点を持つと、
インデックス設計・PK 設計・クエリチューニング・ストレージ選定まで、
一本の筋で判断できるようになります。
関連記事
- アルゴリズム·
二分木 (Binary Tree) を Java で自作する ~ BST / 走査 / バランス崩れの実例
二分木、特に二分探索木 (BST) を Generics で実装。挿入・探索・削除の計算量、3 種類の走査、偏った木がなぜ遅くなるかとその対策 (AVL / Red-Black Tree) まで。
- アルゴリズム·
連結リストを Java で自作する ~ 計算量・ArrayList との境界・現場での使いどころ
連結リストを Generics で自前実装しつつ、ArrayList との計算量・メモリ・キャッシュ効率の比較、現代の Java でこの構造を選ぶ数少ない場面を整理する。
- アルゴリズム·
Singleton パターン ~ 2020 年代の Java では `enum` 一択の理由
伝統的な Singleton の 4 実装と、各々のスレッド安全性・シリアライズ耐性・リフレクション耐性。結論として現代は enum Singleton で終わり。