Engineering
Glossvation Engineering
アルゴリズム

DB インデックスの中身を理解する ~ B-tree / B+ Tree と MySQL・PostgreSQL・NoSQL の実装差

RDBMS の主役インデックスである B+ Tree を、二分探索木との違い・ディスク IO 前提の設計・分割/マージの挙動から解説。InnoDB のクラスタードインデックス、PostgreSQL の heap+index 構造、そして NoSQL (MongoDB / Cassandra / DynamoDB / CouchDB) での採用状況まで整理する。

Glossvation ·

なぜ 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 回のランダム readL1 比
L1 cache~1 ns1×
メモリ~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 の逆:

  1. 葉から値を除去
  2. 使用率が閾値 (多くの実装で 50%) を下回ったら、
  3. 隣の兄弟から借りる (redistribute) か、兄弟とマージする
  4. マージが伝播してルートが空になれば木の高さが 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 なら:

  1. root → 葉で 2026-01-01 の位置を 1 回だけ特定 (IO 3〜4 回)
  2. そこから 葉を右に連続スキャン
  3. 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 で、 「インデックスで参照されていない列だけ更新」 かつ 「同一ページ内に新バージョンが入る」 ときは インデックス更新をスキップします。

PostgreSQL の B-tree は Lehman & Yao (1981) の B-link tree に基づいており、 各ノードに 「右隣へのポインタ」 を持ち、 書き込み中のノードを読み取りがロックせずに辿れる 設計。 これが PostgreSQL の高い並行性の一因です。

MySQL InnoDB vs PostgreSQL — 違いを一行で

観点InnoDBPostgreSQL
テーブル本体の格納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+ TreeLSM 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 設計・クエリチューニング・ストレージ選定まで、 一本の筋で判断できるようになります。

関連記事