B-tree の仕組み

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

B-tree が二分探索木と違う 3 つのポイント

なぜディスクストレージに B-tree が向くのか

ノードの分割と統合がどう自動でバランスを保つか

B-tree の仕組みとは

多分木である B-tree がなぜディスクに向くかを学ぶ。本レッスンでは、B-tree の仕組みの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

なぜ二分探索木ではないのか

ソート済みデータを高速に検索したいなら、二分探索木 (BST) や 赤黒木 が定番です。これらは O(log n) で検索できます。ところが、DB のインデックスは B-tree という多分木を使います。なぜでしょうか。

答えは ディスクアクセスの単位 にあります。

メモリアクセスは数ナノ秒ですが、SSD でもページ読み込みは数十マイクロ秒、HDD は数ミリ秒です。ディスク I/O はメモリより 1 万倍から 100 万倍遅い のです。

二分探索木で 100 万行を検索すると、ノードを 20 回辿ります。各ノードが別々のディスクページにあると、最悪 20 回の I/O が必要です。これは耐えられません。

diagram (will load when visible)

B-tree の発想

B-tree は 「1 ノードに大量のキーを詰める」 ことでこの問題を解決します。1 ノード = 1 ディスクページ（典型的には 4KB or 16KB）に設計され、1 ノードに 100 個以上のキーを格納できます。

すると、1000 万行のインデックスでも木の深さはたった 3 〜 4 段になります。検索 1 回あたり 3 〜 4 回の I/O で済むのです。

B-tree の構造

B-tree は次の性質を持ちます。

多分木 — 1 ノードが m 個の子を持てる（m は数百が典型）
ソート済み — ノード内のキーは昇順
常に平衡 — 全リーフが同じ深さ
半分以上埋まる — 各ノードは最低 m/2 個のキーを持つ

例として 4 分木の B-tree を考えます（実際は 100 分木以上）。

プレーンテキスト

                  [ 30 | 60 ]
                /     |     \
        [10|20]   [40|50]   [70|80|90]

ルートに 2 つのキー 30, 60 があり、3 つの子があります。「30 未満」「30 以上 60 未満」「60 以上」の 3 分割です。

検索の流れ

50 を検索するとき、ルートの 30, 60 を見て「30 以上 60 未満」だから真ん中の子へ。[40|50] の中を二分探索して 50 を発見。検索は 2 回の I/O で完了です。

挿入とノード分割

B-tree は挿入によってノードが満杯になると、自動で 分割 (split) します。

プレーンテキスト

[10|20|30|40] が満杯のとき 25 を挿入

分割: 中央値 25 を親に押し上げ
                [25]
              /     \
        [10|20]   [30|40]

ノードが半分の状態で 2 つに割れ、中央値が親に上がります。親も満杯ならさらに分割。これが伝播してルートまで及ぶことを 木の成長 と呼びます。B-tree が成長するのは下ではなく上で、ルートが置き換わる仕組みです。

これにより全リーフは常に同じ深さに保たれ、最悪検索時間が O(log_m n) で保証されます。

削除とノード統合

逆に削除でノードが半分未満になると、隣接ノードと 統合 (merge) したり、キーを 再配分 (redistribute) したりします。これもバランスを保つための自動メカニズムです。

B-tree の計算量

操作	計算量
検索	O(log_m n)
挿入	O(log_m n)
削除	O(log_m n)
範囲スキャン	O(log_m n + k)

m が 100 のとき、1000 万行で log_100(10^7) ≒ 3.5 です。深さ 3 〜 4 段で全ての操作が完結します。

B-tree が DB の標準的なインデックス構造なのは「ディスク向きの定数で軽い」から。理論的計算量だけ見ても本質はわからない。

オリジナルの B-tree と B+tree

実は世にいう B-tree の多くは正確には B+tree です。違いは「実データをリーフだけに持つか、内部ノードも持つか」です。

B-tree (オリジナル) — 内部ノードもリーフもキー + データを持つ
B+tree — 内部ノードはキーだけ、データはリーフにのみある。リーフ同士は連結リスト

ほとんどの DB (MySQL InnoDB、PostgreSQL、Oracle、SQL Server、TiDB) は B+tree を採用しています。次のレッスンで詳細を見ます。

やってみよう

紙の上で 4 分 B-tree に 5, 10, 15, 20, 25, 30 を順に挿入し、ノード分割を観察する
MySQL の InnoDB のページサイズが 16KB であることを確認する（SHOW VARIABLES LIKE 'innodb_page_size'）
「なぜディスクページサイズと B-tree のノードサイズを揃えるのか」を 1 文で説明できるか確認

よくある質問

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

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

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

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

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

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

次のレッスン

次は B+tree（実際の DB 実装） で、多分木である B-tree がなぜディスクに向くかを学ぶを学びます。

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

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

理解度チェック (30 秒)

Q. B-tree の仕組みとは何か、1 文で説明してください。

この章のポイント

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

関連レッスン