B-treeインデックスの仕組み

「インデックスを貼れば速くなる」という話は知っていても、なぜ速くなるのかを説明できる人は意外と少ないものです。仕組みを理解すると、どのカラムにインデックスを貼るべきか、なぜ効かない場合があるのかを自分で判断できるようになります。

図1: B-treeの構造

B-tree とは

B-treeインデックス? は「バランス木（Balanced Tree）」の略で、MySQL（InnoDB）がインデックス? の実装に使っているデータ構造です。

木構造の特徴は検索の効率にあります。100万行のテーブルを線形探索（端から1件ずつ確認）すると最大100万回の比較が必要ですが、B-treeを使うと約20回の比較で見つかります。これは log₂(1,000,000) ≈ 20 という対数の性質によるものです。

B-treeは以下の3種類のノードで構成されます。

リーフノードが双方向にリンクされている点が重要です。これにより範囲検索が効率的になります。

ルート:     [50]
           /    \
内部:   [20,30]  [70,90]
        /  |  \    /  |  \
リーフ: [10,15] [20,25] [30,35] ...（双方向リンク）

InnoDB では2種類のインデックス構造があります。

InnoDB のテーブルはプライマリキー順にデータが物理的に並んでいます。リーフノードに実際の行データが格納されているため、プライマリキーでの検索は非常に高速です。

-- プライマリキー検索は最速
SELECT * FROM users WHERE id = 42;

プライマリキー以外のカラムに貼るインデックスです。リーフノードにはプライマリキーの値が格納されています。

-- email にセカンダリインデックスがある場合
SELECT * FROM users WHERE email = 'alice@example.com';

この検索は2段階になります：

図2: インデックスを使った検索の流れ

SELECT * FROM products WHERE sku = 'ABC-001';

B-treeをルートから辿り、該当のリーフノードを O(log n) で特定します。

SELECT * FROM orders WHERE created_at BETWEEN '2026-01-01' AND '2026-03-31';

開始値をB-treeで特定したあと、リーフノードのリンクを辿って終了値まで順に読みます。インデックスなしだとテーブル全体を舐める必要があります。

SELECT * FROM users ORDER BY last_name;

last_name にインデックスがあると、リーフノードはすでにソート済みです。EXPLAIN の Extra に Using filesort が出ていたら、インデックスでソートが完結していない証拠です。

カバリングインデックス? とは、クエリが必要とするすべてのカラムがインデックスに含まれている状態です。セカンダリインデックスの場合、通常はインデックスでプライマリキーを見つけてから元テーブルにアクセスしますが、必要なカラムがすべてインデックスに入っていれば元テーブルへのアクセスが不要になります。

-- name と email だけ取得する場合
SELECT name, email FROM users WHERE name = 'Alice';

-- name と email を含む複合インデックスを作成
ALTER TABLE users ADD INDEX idx_name_email (name, email);

EXPLAIN の Extra に Using index と表示されればカバリングインデックスが効いています。これは最も高速な状態です。

インデックスはタダではありません。以下のコストがあります：

次のエピソードでは、インデックスを貼ったのになぜか使われない——そういうケースを体系的に学びます。