B-Tree・B+Treeとは（全体像）
B-Treeは、たくさんのデータの中から目的のものを速く探すための、木のような構造だよー。ふつうの木と違って、1つの節にたくさんの目印（キー）を入れられるので、段数（深さ）が浅くて済むのー。
身近にたとえると、分厚い本の索引。1ページに多くの見出しが並ぶから、何百万件あっても数段たどれば目的に着く感じだよー。
押さえるのは、B-Treeは「2分木」ではない（多分木）こと、そしてB+Treeが範囲検索に強くてDBの索引の定番ということだよー。
詳しく：多分木であることとB+Treeだけ覚えれば戦える
ここが記事の心臓部。まずB-Treeの特徴を見ていこーね。
B-Treeの特徴
| 特徴 | 内容 |
|---|---|
| 多分木 | 1つの節にたくさんの目印（キー）を持てる（2分木ではない） |
| 浅い | 100万件でも深さ3〜4段ほどで探せる |
| 自動で平衡 | 挿入や削除のたびにバランスを保つ |
ここで一番のひっかけが「B-Treeは2分木（バイナリツリー）」という誤解。名前は似ているけれど、B-Treeは1つの節に複数の目印を持つ「多分木」だよー。だから浅く、ディスクの読み出しが少なくて速いのー。
次に、B+Tree（B-Treeの発展形）。
B+Treeの特徴
| 特徴 | 内容 |
|---|---|
| 葉だけに実データ | いちばん下の節（葉）にだけ実データを置く |
| 葉どうしをリンク | 葉が横につながっていて、範囲検索が速い |
| DBの定番 | RDBMSのインデックスで広く使われる |
B+Treeは、葉どうしがつながっているので「〇〇以上△△以下」のような範囲検索が速い。だからデータベースの索引（インデックス）の標準として広く使われているのー。
なお、書き込みを速くすることに振ったLSM-Treeという別の構造もある（B-Treeとは別もの）よー。
わかりやすく言い換えると
要するに、分厚い本の索引でイメージするとラクだよー。
①B-Tree … 1ページに多くの見出し（多分木）。だから数段で目的に着く（2分木ではない）
②B+Tree … 見出しの実体は最後のページにまとめ、ページ同士をつなぐ（範囲検索が速い）
③DBの定番 … B+Treeはデータベースの索引で広く使われる
つまり、「B-Treeは多分木（2分木ではない）」「B+Treeは範囲検索に強くDBの定番」、この2点が試験の急所なのー。
試験のツボ
🔴 一番出る：B-Treeの特徴
①1つの節にたくさんの目印を持つ多分木（2分木ではない）
②深さが浅く、自動でバランスを保つので速い
🔴 次に出る：B+Tree
①葉（いちばん下の節）だけに実データを置き、葉どうしをつなぐ
②範囲検索が速く、データベースの索引の定番
🟡 押さえると安定：LSM-Treeとの対比
①LSM-Treeは書き込みを速くすることに振った別の構造
②B-Tree／B+Treeとは別もの
よくある間違い
①「B-Treeは2分木（バイナリツリー）である」→ ✗ B-Treeは1つの節に複数の目印を持つ多分木。2分木ではない。
②「B+Treeは範囲検索が苦手である」→ ✗ B+Treeは葉どうしがつながり、範囲検索が速い。DBの索引の定番。
③「LSM-TreeはB-Treeと同じものである」→ ✗ LSM-Treeは書き込みを速くすることに振った別の構造。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（B-Treeの特徴）
B-Treeに関する次の記述のうち、正しいものはどれか。
- B-Treeは1つの節にたくさんの目印を持つ多分木で、浅い段数で速く探せる構造である
- B-Treeは1つの節に必ず1つの目印しか持てない2分木のことだとされているものである
- B-Treeは画面に木の絵を表示するための機能のことだとされているものである
- B-Treeはデータを必ず暗号化するための命令のことだとされているものである
解答は 1 だよー。
B-Treeは、1つの節にたくさんの目印（キー）を持つ多分木で、浅い段数で速く探せる構造なのー。分厚い本の索引が数段で引ける感じだよー。
選択肢2の「2分木」、選択肢3の「木の絵を表示」、選択肢4の「暗号化」はどれも誤りなのー。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 多分木で浅く速い |
| 2 | ✗ | 2分木ではなく多分木 |
| 3 | ✗ | 木の絵を表示する機能ではない |
| 4 | ✗ | 暗号化の命令ではない |
オリジナル問題2（B+Tree）
B+Treeに関する次の記述のうち、正しいものはどれか。
- B+Treeは範囲検索がとても苦手で、データベースでは使われないものだとされているものである
- B+Treeはデータを必ずすべて削除するための専用の命令のことだとされているものである
- B+Treeは葉だけに実データを置き葉をつなぐので、範囲検索が速くDBの索引の定番である
- B+Treeは画面の明るさを決めるための専用の設定のことだとされているものである
解答は 3 だよー。
B+Treeは、葉（いちばん下の節）だけに実データを置き、葉どうしをつなぐので、範囲検索が速く、データベースの索引の定番なのー。
選択肢1の「範囲検索が苦手」、選択肢2の「削除する命令」、選択肢4の「明るさの設定」はどれも誤りなのー。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 範囲検索は得意 |
| 2 | ✗ | 削除する命令ではない |
| 3 | ✓ | 葉にデータ＋葉リンクで範囲に強い |
| 4 | ✗ | 明るさの設定ではない |
オリジナル問題3（LSM-Treeとの対比）
B-TreeとLSM-Treeに関する次の記述のうち、正しいものはどれか。
- LSM-TreeはB-Treeとまったく同じもので、違いはないものだとされているものである
- LSM-Treeは書き込みを速くすることに振った、B-Treeとは別の構造である
- LSM-Treeは画面を必ず点滅させるための設定のことだとされているものである
- LSM-Treeはデータを必ず暗号化するための命令のことだとされているものである
解答は 2 だよー。
LSM-Treeは、書き込みを速くすることに振った、B-Treeとは別の構造なのー。CassandraやRocksDBなどで使われているよー。同じものではないので注意だよー。
選択肢1の「まったく同じ」、選択肢3の「点滅させる」、選択肢4の「暗号化」はどれも誤りなのー。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | B-Treeとは別もの |
| 2 | ✓ | 書き込み最適化の別構造 |
| 3 | ✗ | 点滅させる設定ではない |
| 4 | ✗ | 暗号化の命令ではない |
まとめ
押さえどころ
- 🔴 B-Treeの特徴 ＝ 1つの節にたくさんの目印を持つ多分木（2分木ではない）。浅く、自動でバランスを保ち速い。
- 🔴 B+Tree ＝ 葉だけに実データ＋葉どうしをつなぐ。範囲検索が速く、データベースの索引の定番。
- 🟡 LSM-Treeとの対比 ＝ 書き込みを速くすることに振った別の構造。B-Treeとは別もの。
次に学ぶ
執筆: SikakuQuest編集部