行はB-treeに載っている

InnoDBのテーブルは、内部的にはB-treeインデックスとして格納されます。主キーで作られるインデックスをクラスタ化インデックスと呼び、行データそのものがこのB-treeのリーフ（末端）に載ります。つまり「テーブル」と「主キーのB-tree」は、InnoDBでは同じものを指しています。

B-treeは、ルート（根）を頂点にリーフへ向かって枝分かれする木構造です。目的の行を探すときは、ルートから枝をたどって該当するリーフページへ降りていきます。木の高さ（段数）が低いほど、1件を探すために読むページが少なくて済みます。

各ノードは1ページ（既定16KB）です。リーフノードには実際の行データ、リーフでない中間ノードやルートには「どのキー範囲がどの子ページにあるか」を示す案内（ノードポインタ）が入ります。上の図は3段ですが、これは説明用の一例で、段数が3で固定されているわけではありません。

ディスクI/Oを減らすための木の形

B-treeがこの形をしているのは、ディスクの読み書きの特性に合わせるためです。InnoDBはデータをページ単位（既定16KB）で読み書きし、木を1段降りるたびに、その段のページを1枚読みます。ディスク、とくにHDDでは、目的の位置まで磁気ヘッドを動かすシーク（seek）に時間がかかり、1回のランダムな読み込みはメモリアクセスに比べて桁違いに遅くなります。そのため、1件を探すのに何段降りるか、すなわち何枚のページを読むかが、そのまま速さを左右します。

もし各ノードが子を2つしか持たない二分木だったらどうなるでしょうか。二分木のノードは1つのキーと左右2つの子への参照しか持たないため、16KBのページのごく一部しか使わず、大半が無駄になります。しかも子が2つなので木の高さはおよそlog2(N)まで伸び、たとえば数億件では30段近くにもなります。1段ごとにページを1枚読む（HDDならシークを1回起こす）とすれば、1件を探すのに数十回のシークが必要になり、実用に耐えません。

B-treeは逆に、1ページを1ノードと決めたうえで、そのページにできるだけ多くのキーと子への参照（ノードポインタ）を詰め込みます。どうせ1ページを丸ごと読むのだから、中身を目一杯使おうという発想です。1ノードが持つ子の数をファンアウトと呼び、これが大きいほど、同じ件数を覆うのに必要な段数は少なくなります。

InnoDBの実際の数字で見てみます。非リーフの1件のノードポインタは、キー本体（主キーがBIGINTなら8バイト）に子ページ番号やレコードヘッダーなどが加わって十数バイト程度です。16KBのページにはこれがおよそ1000〜1200件入るので、ファンアウトはおよそ千になります。すると、ルートの下にリーフが並ぶ2段でリーフは約千枚、3段で約千×千＝約百万枚、4段で約十億枚を覆えます。1枚のリーフには行の大きさに応じて数十から数百行が載るので、3段でおよそ数千万から数億行、4段でおよそ数百億行を格納できる計算です。だからこそ、行が数件の小さなテーブルではルートがリーフを兼ねる1段で済み、数千万から数億行の大きなテーブルでも木の高さは3〜4段に収まって、1件の検索はたかだか3〜4回のページ読み込みで完了します。

逆に、主キーを必要以上に大きくすると、非リーフに載るキーが大きくなってファンアウトが下がり、同じ件数でも段数が増えて効率が落ちます。主キーをできるだけ小さく保つのがよいとされるのは、これが理由の1つです。

リーフに何が載るかはインデックス次第

同じB-treeでも、リーフに格納される内容はインデックスの種類で変わります。

セカンダリインデックスのリーフには行本体が入っていません。そのため、セカンダリインデックスで検索したあとに他のカラムも必要になると、リーフに載っている主キーを使って、あらためてクラスタ化インデックスをたどり直します。この2段階のたどり直しは検索コストを押し上げる要因になります。

user_id='alice01'の行のnameが欲しいとき、セカンダリリーフにはuser_idと主キーid=101しかありません。行本体は、そのidでクラスタ化インデックスをたどった先のリーフにあります。

矢印はセカンダリリーフに載っている主キーを使った、クラスタ化リーフへのたどり直しです。

ただし、クエリが必要とするカラムがすべてセカンダリインデックスのリーフに載っている値、つまりインデックスキーの列と主キーの列だけで足りる場合は、クラスタ化インデックスをたどり直す必要がありません。たとえばuser_id列にセカンダリインデックスを張ったusersでSELECT id FROM users WHERE user_id = 'alice01'のように、取り出すのが主キーidと検索条件のuser_idだけなら、セカンダリインデックスのリーフを読むだけで結果を返せます。このように必要な列をインデックスに含めておく工夫を、カバリングインデックスと呼びます。

なお、行本体を別領域（ヒープ）に置き、インデックスのリーフにはその場所への参照だけを持たせる設計のエンジンもあります。InnoDBはそうではなく、主キーのB-treeのリーフに行本体そのものを載せます。

同じ高さのページは横につながっている

木構造というと縦のつながりだけを思い浮かべがちですが、InnoDBのB-treeでは、同じ高さ（レベル）のページどうしが双方向リンクリストで横にもつながっています。これはリーフに限らず、中間ノードでも同じです。各レベルごとに独立したリストがあり、各ページのヘッダーに「前のページ」「次のページ」の番号を持ちます。範囲検索で実際に横へ進むのは行データのあるリーフのリストで、目的の先頭キーが載るリーフへ木を降りたあと、このリンクをたどって隣のリーフへ次々と進めます。

WHERE id BETWEEN 100 AND 200のような範囲検索は、まず先頭の100が載るリーフへ木を降り、そこからFIL_PAGE_NEXTをたどって右へ読み進めるだけで済みます。リーフどうしが物理的にも近い場所に並んでいれば、この読み進めは連続したディスクアクセスになり効率が良くなります。

テーブルスペースという入れ物

B-treeのページは、テーブルスペースという入れ物の中に配置されます。テーブルスペースは、大きい順にセグメント・エクステント・ページという階層で領域を管理します。

エクステントは64ページ分の連続領域です。まとめて割り当てるのは、連続した領域を確保しておけば範囲スキャンでの読み進めが速くなるからです。

リーフと非リーフは別セグメントに分ける

InnoDBは、B-treeの非リーフノード（ルートと中間）とリーフノードを別々のセグメントに割り当てます。範囲検索ではリーフを横に連続してたどるため、リーフどうしを物理的に近い領域へ固めておくと、シーケンシャルな読み込みになりオーバーヘッドが減ります。案内役の非リーフと、実データを持つリーフとで、望ましい配置が違うわけです。

いきなり大きく取らず少しずつ増やす

新しいテーブルを作った直後から1MBのエクステントを丸ごと確保すると、行が数件しかない小さなテーブルでは領域が無駄になります。そこでInnoDBは、セグメントを作った当初はフラグメントページとして1ページずつ割り当てます。これらは複数セグメントで共有する領域（共有エクステント）に置かれます。使用ページが32に達すると、そこからはエクステント単位でまとめて割り当てるように切り替わります。小さいうちは節約し、育ってきたら連続領域でまとめて確保する、という段階的な方針です。