B木・B+木とデータベースインデックスの関係

概要¶

B木・B+木の仕組みと、なぜデータベースのインデックスに使われているかを解説した記事の紹介ポスト（sadkatwt の記事）。

詳細¶

B木（B-Tree）とは¶

自己平衡探索木の一種。通常の二分探索木と違い、各ノードが複数のキーと複数の子を持てる。

         [30]
        /    \
   [10,20]  [40,50]
   /  |  \   /  |  \
 [5] [15] [25] [35] [45] [55]

特性: - 全ての葉が同じ深さ（平衡） - ノードあたりのキー数: t-1 ≤ keys ≤ 2t-1（t = 最小次数） - 検索・挿入・削除がすべて O(log n)

B+木（B+ Tree）とは¶

B木の変種で、データはすべて葉ノードにのみ格納 し、内部ノードはインデックスとしてのみ使う。さらに葉ノード同士がリンクリストで連結される。

         [30]
        /    \
   [10,20]  [40,50]   ← 内部ノード（インデックスのみ）
       ↓         ↓
[5→10→15→20→25→30→35→40→45→50→55]  ← 葉ノード（実データ、連結）

なぜデータベースは B+木を使うのか¶

観点	B木	B+木
範囲検索	遅い（中間ノードも辿る）	速い（葉を連結リストで辿るだけ）
ディスクI/O	多い	少ない（葉ノードに全データが集中）
フルスキャン	非効率	効率的（葉を左から右に辿るだけ）
空間効率	各ノードにデータ	内部ノードにはキーのみ（軽量）

MySQL InnoDB での B+木インデックス¶

-- クラスタインデックス（主キー = B+木のリーフにデータ行）
CREATE TABLE users (
    id INT PRIMARY KEY,    -- 主キー → クラスタインデックス
    name VARCHAR(100),
    email VARCHAR(200),
    INDEX idx_email (email)  -- セカンダリインデックス
);

-- セカンダリインデックス: 葉ノードに「email + 主キー」を格納
-- → email で検索 → 主キーを取得 → クラスタインデックスで行を取得（ダブルルックアップ）

カバリングインデックスで二重ルックアップを回避¶

-- email と name を一緒に返すクエリ
SELECT name FROM users WHERE email = 'alice@example.com';

-- email のみのインデックス → email検索 → 主キー取得 → 行取得 (2回のB+木ルックアップ)
INDEX idx_email (email)

-- カバリングインデックス → B+木の葉ノードだけで完結（1回のルックアップ）
INDEX idx_email_name (email, name)

B+木の高さとアクセス数¶

ページサイズ 16KB、キーサイズ 8バイト、ポインタ 6バイトとすると: - 1ノードに約 16384 / (8+6) ≈ 1170 キーが入る - 高さ2のB+木: 1170² ≈ 137万件 をカバー - 高さ3のB+木: 1170³ ≈ 16億件 をカバー

→ 大規模テーブルでも 2〜3回のディスクI/O で目的の行にたどり着ける

なぜ重要か / いつ使うか¶

インデックスが効くクエリの設計: WHERE 句・ORDER BY・JOIN の列にインデックスを張る意味を理解できる
EXPLAIN の読み方: Using index（カバリング）vs Using index condition の違いを把握できる
複合インデックスの列順: 左端から使われる性質（Leftmost prefix rule）の理由が分かる
面接での必須知識: 「なぜインデックスを使うと速いのか」に B+木の構造で答えられる