B-treeインデックス

B-treeは「ソートされた分岐する索引」

B-treeは、キーをソート順に保持しながら1つのノードから複数の子に分岐する木構造です。 ルートから葉に向けて辿っていくだけで、目的の値に対数時間で到達できます。 以下のインタラクティブ図解で、実際に探索の動きを見てみましょう。

探索の手順

1. ルートノードのキーと目的の値を比較する
2. 目的の値がキーに一致すれば発見。そうでなければ、どの子に降りるか（値の範囲）を判断する
3. 子ノードに降りて1〜2を繰り返す
4. 葉ノードまで来ても見つからなければ「該当なし」

ノードあたりのキー数と木の高さ

本記事の図解はデフォルトでノードあたり最大3キーに設定していますが（上のコントロールで変更可能）、実際のRDBMSではノードあたり数百〜数千キーが入ります。 そのため、10億件のデータでも木の高さはわずか3〜4段程度で済み、ディスクI/Oが極めて少ない探索が可能です。

挿入とノード分割

「挿入モード」に切り替えて値を追加してみてください。ノードのキー数が上限を超えると、中央値を親に押し上げて分割する動きが見られます。 こうして木の高さは最小限に保たれ、常にバランスした状態が維持されます。

葉ノードにあるのは「キー + 行ID」

B-treeの葉ノードには、検索キーそのものだけでなく、そのキーが指す実データがどのページにあるかを示す行IDが入っています。 つまり検索の流れは「B-treeを数段辿る」→「行IDを取得」→「そのページを1回読む」の3ステップ。

なぜ「対数時間」で1件を取り出せるか、これで物理的に見えてきます。 B-treeを辿るのに数ページ、そこから行IDを得てテーブル本体を1ページ読む。 合計でも数回のページ読み取りで済むため、1000万件でも数ミリ秒で1件が引ける。

B-treeが向いていない検索

• 先頭ワイルドカード（LIKE '%foo'）
• 関数変換を経た比較（WHERE LOWER(name) = ...）
• 暗黙の型変換を伴う比較

いずれも「ソート順が使えなくなる」ため、B-treeを辿ることができずフルスキャンに落ちます。