B+tree（実際の DB 実装）

このレッスンで分かること

B-tree と B+tree の構造的な違い

リーフ連結リストがなぜ範囲検索を強くするのか

InnoDB が採用するクラスタード B+tree の正体

B+tree とは

リーフを連結リストで結ぶ B+tree が範囲検索に強い理由。本レッスンでは、B+tree の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

B+tree の特徴

B+tree は B-tree を改良したデータ構造で、現代の主要 DB が標準的に採用しています。基本構造は B-tree と同じですが、次の 2 点が違います。

データはリーフだけに保存 — 内部ノードはキーだけ、データはリーフのみ
リーフ同士が連結リストでつながる — 範囲スキャンが高速

diagram (will load when visible)

なぜリーフだけにデータを置くのか

B-tree では内部ノードにもデータがあるため、ノードに入るキーの数が減ります。1 ページ 16KB のうち、データに半分使ったらキーは半分しか入りません。

B+tree は内部ノードを キーだけ にしました。これで 1 ノードに 1000 個以上のキーを詰め込めます。深さがさらに浅くなり、I/O 回数が減ります。

実データはリーフだけにあるので、検索ではどんなキーでも 必ずリーフまで 降りる必要があります。B-tree なら運がよければ内部ノードで見つかりますが、B+tree はそれがない代わりにツリーが浅く速い、という設計トレードオフです。

リーフ連結リストの威力

B+tree の最大の武器は、リーフ同士が双方向連結リスト でつながっていることです。

範囲検索 WHERE age BETWEEN 30 AND 50 を考えます。

ツリーを辿って age=30 を含むリーフに到達
そのリーフから 連結リストを右に辿る
age=50 を超えたら停止

これにより、範囲内のデータを シーケンシャル I/O で取り出せます。シーケンシャル I/O は SSD / HDD ともにランダム I/O より圧倒的に速いので、範囲スキャンが極めて効率的になります。

B-tree では各範囲要素ごとに木を辿り直さなければならず、これは大きな差です。

「B+tree は範囲検索を、hash は等価検索を」と覚えるとよい。

クラスタードインデックスとセカンダリインデックス

InnoDB (MySQL の標準ストレージエンジン) は クラスタードインデックス を採用しています。これは「テーブル本体が B+tree のリーフそのもの」という構造です。

プレーンテキスト

クラスタード B+tree (PRIMARY KEY)
                  [ 30 | 60 ]
                /     |     \
        [行データ]  [行データ]  [行データ]
        (id=10,20)  (id=40,50)  (id=70,80,90)

リーフに行データそのものが入っているため、PRIMARY KEY での検索は 1 回の B+tree 走査 で済みます。

それ以外のカラムにインデックスを貼ると、それは セカンダリインデックス と呼ばれ、リーフには 主キー値 が入ります。

プレーンテキスト

セカンダリ B+tree (email)
リーフ: email='alice@ex.com' → primary_key=1
       email='bob@ex.com'   → primary_key=2

WHERE email = ? で検索すると、

email セカンダリインデックスを辿って主キーを得る
その主キーで PRIMARY のクラスタードインデックスを再走査 して行データを得る

この 2 段階を テーブル参照 (lookup) と呼びます。SELECT * だとほぼ常にこの 2 段階が発生します。

PostgreSQL の場合

PostgreSQL は InnoDB と違い、ヒープテーブル + B+tree インデックス の構造です。テーブル本体はヒープに格納され、PRIMARY KEY もただのセカンダリインデックス扱いです。

InnoDB なら PRIMARY KEY の連続挿入は B+tree の末尾に追加するだけで速いですが、ランダムな PRIMARY KEY (UUIDv4) を使うと B+tree の中間に挿入が散らばり、ページ分割が頻発して遅くなります。AUTO_INCREMENT や UUIDv7 が好まれる理由です。

ページ分割とフラグメンテーション

リーフが満杯のときに新しい行が挿入されると、リーフが分割されます。長期運用すると 断片化 が進み、空き領域が散らばって I/O 効率が落ちます。

PostgreSQL は REINDEX（オンライン実行なら REINDEX CONCURRENTLY）、MySQL は OPTIMIZE TABLE で再構成できます。VACUUM は不要タプルの回収が主目的であり、インデックス断片化の解消には使いません。本番では定期メンテナンスが必要です。

実務の影響

主キーは 連番 (AUTO_INCREMENT) か順序付き UUID を使う
SELECT * は本当に必要な列だけにする（テーブル参照の回避）
WHERE の条件はインデックス順に並べる
範囲検索が多いカラムには B+tree インデックスを貼る（hash は不可）

やってみよう

MySQL で EXPLAIN SELECT * FROM users WHERE email = ? を実行し、type=ref と key=email_idx が出るか確認
UUIDv4 を主キーにしたテーブルに 100 万件挿入する時間と、AUTO_INCREMENT で同じことをする時間を比較
ANALYZE TABLE を実行して統計情報を更新し、EXPLAIN の出力が変わるか観察

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. 計算量はどう求めれば良いですか？

A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

Q. 覚えるべき定番アルゴリズムは何ですか？

A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

次のレッスン

次は ハッシュインデックス で、リーフを連結リストで結ぶ B+tree が範囲検索に強い理由を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

B+tree（実際の DB 実装）の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. B+tree（実際の DB 実装）とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン