データベースのインデックスといえば B-tree インデックスが第一の選択肢ですが、「なぜ B-tree だと速いのか」「リーフノードとは何か」「対数的スケーラビリティとは何か」といった内部構造を理解しておかないと、複合インデックスの列順設計やチューニングの判断がブレやすくなります。
本記事では Use The Index, Luke!（Markus Winand 著）第1章の内容をもとに、B-tree インデックスの内部構造を整理します。
インデックスのエントリ構造
インデックスのエントリは次の2つで構成されます。
- キー: インデックスを張った列の値
- テーブル行への参照: ROWID（Oracle）／RID（SQL Server）／プライマリキー（InnoDB のセカンダリインデックス）
このエントリが リーフノード に格納されます。リーフノードはデータベースブロック／ページという最小 I/O 単位（数 KB）で、エントリを詰め込めるだけ詰め込みます。
一方、テーブル本体は ヒープ構造 でソートされていません。「行を挿入された順、もしくは空きブロックがあった順」に格納されます。
リーフノードと双方向連結リスト
リーフノード同士は 双方向連結リスト で順序付けされており、各ノードは前後のノードへのポインタを持ちます。
[リーフ1] ⇔ [リーフ2] ⇔ [リーフ3] ⇔ [リーフ4]
Aaron Abbott Adams Adler
Anders Auer Bauer Bergこの構造により以下が成立します。
- 新しいエントリを既存ノード間に挿入してもポインタの付け替えだけで済む
- インデックスを 順方向にも逆方向にも読める（
ORDER BY ... DESCでもインデックスが効く理由） - 範囲検索（
BETWEEN、> <、前方一致 LIKE）でリーフノードチェーンをそのまま舐められる
つまりインデックスのソート順は (1) リーフノード内の順序、(2) 双方向連結リストでつながれたリーフノード同士の順序、という 2 階層 で管理されます。
B-tree（バランス検索木）
リーフノード自体はディスク上にバラバラに置かれているので、特定のキーを発見するには別の仕組みが必要です。それが B-tree（バランス検索木） です。
B-tree は二分木（binary tree）ではなく balanced tree（全リーフまでの深さが等しい木）です。ブランチノード はその下にあるリーフノードたちの最大値を指し、ルートノード に到達するまで再帰的にレイヤを積みます。
[ルートノード]
Adams | Berg
/ \
[ブランチノード] [ブランチノード]
Abbott | Adams Bauer | Berg
/ \ / \
[リーフ1] [リーフ2] [リーフ3] [リーフ4]
Aaron Adams Bauer Berg
Abbott Adler Berry Berger検索（ツリー走査）はルートノードから始めて、検索値以上の最初のエントリを選びそのポインタが指すブランチノードに降りる、を木の深さ分繰り返してリーフノードに到達します。
各ノードに格納できるエントリ数を底とした対数 log(N) で深さが決まるため、対数的スケーラビリティ を持ちます。各ノードには数百単位のエントリが入るため、数百万行のテーブルでも木の深さは 4〜5、6 になることはほとんどありません。
これが B-tree インデックスの 強みの 1 つ目: 高速なリーフノード発見です。
インデックスを使った検索の3ステップ
インデックスを使った検索は以下の 3 ステップで行われます（Oracle の用語が分かりやすいので Oracle 用語で説明します）。
| ステップ | Oracle のオペレーション | 内容 |
|---|---|---|
| 1 | INDEX UNIQUE SCAN | ツリー走査だけ。ユニーク制約により結果が必ず1件と確定している場合 |
| 2 | INDEX RANGE SCAN | ツリー走査＋リーフノードチェーンの走査。一致するエントリが複数ありうる場合 |
| 3 | TABLE ACCESS BY INDEX ROWID | 直前のインデックススキャンが返した ROWID 群に対してテーブル本体から行を読む |
各 RDBMS のオペレーション名対応
| RDBMS | INDEX UNIQUE SCAN 相当 | INDEX RANGE SCAN 相当 | TABLE ACCESS 相当 |
|---|---|---|---|
| MySQL | type=const | type=ref / range | テーブルアクセスは暗黙（PRIMARY 経由） |
| PostgreSQL | Index Scan（unique） | Index Scan / Bitmap Index Scan | Bitmap Heap Scan 等 |
| SQL Server | Index Seek | Index Seek (range) | RID Lookup / Key Lookup |
| Db2 | IXSCAN | IXSCAN | FETCH |
「遅いインデックス」の正体
インデックスを使っているのにクエリが遅い、ということは普通に起きます。「劣化したインデックス」「アンバランスな木」という都市伝説がありますが、これらは誤りです。本当の原因は次の 2 つに集約されます。
(1) リーフノードチェーンの走査範囲が広い
INDEX RANGE SCAN で双方向連結リストをたどる範囲が広いほど遅くなります。WHERE last_name LIKE 'A%' で何万行もマッチするなら、それだけのリーフノードを舐める必要があります。
(2) 各行ごとのテーブルアクセス（TABLE ACCESS BY INDEX ROWID）が多い
リーフノードには ROWID しか入っていないので、SELECT 句の列を取るためにテーブル本体（ヒープ）にアクセスする必要があります。対象行が複数のテーブルブロックに散らばっていると 1 行ずつテーブルアクセスが発生します。
最悪の組み合わせ
「広範囲のインデックスアクセス＋大量の 1 行ずつテーブルアクセス」 で、この場合フルテーブルスキャン（マルチブロックリードでまとめて読める）の方が速くなります。インデックスを使っていれば最適、とは限りません。
オプティマイザは統計情報をもとに「フルスキャンの方が速い」と判断したらインデックスを無視するのは、この理由によるものです。
まとめ
- インデックスは 双方向連結リスト + B-tree という 2 つのデータ構造で実装され、論理順序と物理位置を分離している
- B-tree は balanced tree であり対数的スケーラビリティを持つ。数百万行でも深さは 4〜5
- インデックス検索は「ツリー走査 → リーフノードチェーン走査 → テーブルアクセス」の 3 ステップ
- 遅さの原因は後ろの 2 ステップ（リーフチェーン走査範囲＋テーブルアクセス回数）
- 「インデックスを使っていれば最適」とは限らない。広範囲スキャン＋大量テーブルアクセスはフルスキャンより遅い