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

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

ただし、クエリが必要とするカラムがすべてセカンダリインデックスのリーフに載っている値、つまりインデックスキーの列と主キーの列だけで足りる場合は、クラスタ化インデックスをたどり直す必要がありません。たとえばuser_id列にセカンダリインデックスを張ったusersでSELECT id FROM users WHERE user_id = 'user01'のように、取り出すのが主キー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に達すると、そこからはエクステント単位でまとめて割り当てるように切り替わります。小さいうちは節約し、育ってきたら連続領域でまとめて確保する、という段階的な方針です。

ページの中はどうなっているか

InnoDBのページ（既定16KB）は、ただ行を詰め込んだ領域ではなく、決まった区画に分かれています。リーフノードでも非リーフノードでも、この骨格は同じです。

このうちレコードが置かれるのはUser Records（ヒープ領域）です。区画の役割はいくつもありますが、まずは「先頭に管理情報、真ん中にレコード、末尾に検索用の索引」という並びを押さえておけば十分です。図ではその3つをセルの色で分けています。

2種類のレコード

ページに入るレコードは、ユーザーレコードとシステムレコードの2種類に分かれます。

システムレコード（InfimumとSupremum）

InfimumとSupremumは、InnoDBが各ページに必ず1つずつ用意する特別なレコードです。データを持つためではなく、レコード列の両端を示す番兵として機能します。

キー順にレコードを読むには、いちばん小さいレコードから次、その次、とたどります。そのため「いまこのページの先頭はどれか」をどこかに覚えておく必要があります。番兵がないとその先頭はユーザーレコード自身なので、先頭より小さいキーが入るたびに、覚えている先頭が古くなります。

たとえばページにid=101とid=102があるとき、id=50を入れても先頭の覚えを101のままにしておくと、走査は101から始まり50には届きません。行はページに置いたのに、キー順では存在しないのと同じです。id=101を消すときも同じで、先頭の覚えを102へ付け替え忘れると、残ったレコードを見失います。反対側も同様で、id=200を末尾に付けたあと「次がない」を終端とみなす処理を忘れると、存在しない先を読みに行きます。空のページでは覚える先頭そのものがないので、挿入も走査も、レコードがあるときとは別の手順になります。分岐を1つでも落とすと、鎖が切れるか、ページの外を読むことになります。

InfimumとSupremumを両端に固定しておくと、走査の起点と終点は変わりません。どの挿入も「すでにある2件のあいだに挟む」同じ手順です。id=50はInfimumと101のあいだ、id=200は102とSupremumのあいだ、空のページでもInfimumとSupremumのあいだです。走査はInfimumから始めてSupremumに当たったら終わる、と決められます。heap_noはページ内の通し番号で、Infimumが常に0、Supremumが常に1になります。

ユーザーレコード

ユーザーレコードは、アプリケーションが実際に格納したデータに対応するレコードで、heap_noは2以降になります。リーフノードなら行データ（またはセカンダリインデックスのキーと主キー）が入ります。非リーフノード（ルートと中間）には行本体は置かず、代わりに「このキー以上は子ページNへ」という案内（ノードポインタ）が入ります。たとえばid=101を探すとき、非リーフの1件が「101以上はページ42」と書いてあれば、次に読むのはページ42です。

物理的な並びと論理的な並びは別

新しいレコードは、ヒープ領域の末尾（HEAP_TOP）に追加されていきます。つまりディスク上での物理的な並びは、おおむね挿入した順です。ところが検索や走査で使いたいのはキー順です。この2つの順序はどう両立しているのでしょうか。

答えは、各レコードが持つnextという「キー順で次のレコード」を指すポインタです。物理的にはバラバラの位置にあっても、nextをたどればキーの小さい順に一巡できます。挿入のたびに、新しいレコードが正しいキー順の位置に入るようnextがつなぎ替えられます。

DELETEした直後のレコードは、すぐには消えません。まず削除マークが付くだけで、ヒープ領域はそのまま残ります。あとからpurgeという処理が物理削除して、その隙間を空きとして管理します。次に同じくらいのサイズのレコードを挿入するとき、その隙間が再利用されることがあります。このため、ヒープの中身は「挿入順にきれいに並んだ列」ではなく、削除の穴が空いたり埋まったりした状態になります。

レコードヘッダーの中身

各レコードには、データ本体の直前にレコードヘッダーが付きます。サイズは行フォーマットで決まり、COMPACT・DYNAMIC・COMPRESSEDでは5バイト、REDUNDANTでは6バイトです。ヘッダーは、データ本体の先頭であるORIGINよりも手前（アドレスの小さい側）に置かれます。以下はCOMPACT系の5バイトヘッダーで、ORIGINから遠い側から近い側へと並べています。表のいちばん下のnextが、ORIGINのすぐ手前に位置します。

heap_noとstatusの詰め方には、地味ですが効いてくる工夫があります。heap_noは13ビット、statusは3ビット必要です。素直に別々のバイトに置くと、statusに1バイト（5ビット余る）とheap_noに2バイトで合計3バイトかかります。ところが同じ2バイトの中に16ビットとして詰めれば収まります。この工夫でCOMPACT系のヘッダーは5バイトに収まっており、詰めない場合の6バイトより1レコードあたり1バイト小さくなります。1ページに載る行数はレコードのサイズに反比例するので、この1バイトが積み重なると効いてきます。

可変長フィールドの長さの並び

レコードヘッダーと同じく、ORIGINより手前（アドレスの小さい側）には、可変長フィールドの長さ情報も置かれます。可変長フィールドとは、VARCHARやTEXTのように値のバイト数が行ごとに変わるカラムです。INTのような固定長は常に同じサイズなので長さを記録する必要がありませんが、可変長は「このフィールドは何バイトか」が分からないと、データ部のどこで次のフィールドに切り替わるかを判断できません。そこで、各可変長フィールドの実際の長さをメタデータとして持ちます。

この長さ情報は逆順で並びます。データ部がフィールド1、2、3の順なら、長さ情報はL3、L2、L1の順です。つまり最後のフィールドの長さがレコードの先頭バイトに近い側に、先頭フィールドの長さがORIGINに近い側に置かれます。各長さは、値の大きさに応じて1バイトまたは2バイトで表されます。

可変長のrec_1、rec_2、rec_3をこの順に持つレコードでは、バイトの並びは次のとおりです。

リーフに載る行データと行外保存

リーフノードのユーザーレコードには、そのインデックスで定義されたすべてのカラムがそろいます。クラスタ化インデックスなら主キーと行の全カラム、セカンダリインデックスならインデックスキーと主キーです。非リーフのノードポインタがキーの先頭部分（プレフィックス）しか持たないのと違い、リーフは値を先頭だけに切り詰めることはしません。

ただし、値がすべてそろっていることと、その値をディスク上のどこに置くかは別の話です。ここで問題になるのがTEXTやBLOBのような大きな可変長データです。これをすべてリーフの行に詰めると、1行が巨大になり、1ページに載る行数が激減します。そこでInnoDBは、行がページに収まらないとき、長い可変長カラムを行外（専用の外部ページ）に置き、リーフの行にはそこへのポインタや先頭の一部だけを残せます。短い値や、行全体がページに収まる場合は、行外に出さずリーフ内に置きます。TEXTやBLOBでも40バイト以下なら、DYNAMICではインラインに残します。行外に出すときのページ内の残り方は、行フォーマットで異なります。

リーフのレコードには「このフィールドは行外にある」という印が付き、必要になったときだけ外部ページを読みます。おかげで、通常のリーフページには多くの行を載せたまま、大きな値も扱えます。

非リーフに載るノードポインタ

非リーフノード（ルートと中間）のユーザーレコードには、行データではなく子ページへの案内であるノードポインタが入ります。中身は「キープレフィックス＋子ページ番号（4バイト）」です。検索でこのページに来たとき、探しているキーがどの子ページの範囲に入るかを見て、その子ページ番号へ降ります。

キープレフィックスは、行を一意に識別するのに必要な最小限のキーです。インデックスキー全体ではなく、先頭からn_uniqueフィールド分だけを載せます。なぜ全体を載せないのでしょうか。ノードポインタが小さいほど、1つの非リーフページにより多くのノードポインタを載せられます。1ページに載るノードポインタが多いということは、そのページ1枚でより多くの子ページを指し示せるということです。すると、同じ件数のデータでも、より少ない段数の木で全体を覆えます。木を1件たどるにはルートからリーフまで各段で1ページずつ読むので、段数が少ないほど、1件を探すために読むページも少なくて済みます。

n_uniqueは一意に識別するのに必要なフィールド数です。主キーが1列なら1、複合主キーなら主キーの列数になります。非ユニークなセカンダリインデックスでは、インデックスキーに主キーを足した組み合わせが一意性の単位になり、その列数がn_uniqueになります。ユニークなセカンダリインデックスでは、ユニークキーの列だけがn_uniqueで、主キーは必ずしも含まれません。

親ノード上では、各ノードポインタのキーが、その子ページが担当するキー範囲の下限を表します。隣り合う2本のノードポインタのキーをP、P'とすると、そのあいだの子ページにはP以上P'未満のキーが入る、という対応になります。

主キーがINT1列（n_unique=1）で、リーフのレコードが(id=101, rec_2, ...)のとき、非リーフのノードポインタは(101)＋子ページ番号だけです。複合主キーがINT + VARCHAR(50)（n_unique=2）で、リーフが(id=101, rec_2, ...)なら、キープレフィックスは(101, rec_2)の2フィールドで、それ以降のカラムは持ちません。

SQLのNULLは「0」でも「空文字」でもなく、「値が存在しない」という状態です。InnoDBはこの状態をデータ領域を使わずに表現します。

NULLビットマップ

COMPACT系の行フォーマット（COMPACT・DYNAMIC・COMPRESSED）では、Nullableなフィールドの分だけレコード内にNULLビットマップを持ちます。行フォーマットREDUNDANTではこのビットマップを持たず、各フィールドのオフセット情報にNULLかどうかを書き込みます。ビットマップのサイズは、Nullableなフィールド数を8で割って切り上げたバイト数です。0個なら0バイト、1〜8個なら1バイト、9〜16個なら2バイトと増えます。

各Nullableフィールドにはビットが1つ割り当てられ、フィールドの定義順に並びます。ビットが1ならそのフィールドはNULL、0なら非NULLです。NULLのフィールドには長さ情報もデータも格納されません。レコードを走査するときは、Nullableフィールドに来るたびにビットマップを見て、ビットが1ならそのフィールドを読み飛ばします。

NULLビットマップは、データ先頭であるORIGINから見てレコードヘッダー側にあります。ヘッダーは5バイトで、その直前にビットマップが置かれます。

図では、上へ行くほどアドレスが小さく、下へ行くほど大きくなります。record startとORIGINは、どちらも領域の内部ではなく、隣接する領域の境界を指しています。record startはレコードの最もアドレスの小さい位置、つまり先頭バイトの手前の境界で、可変長フィールドがあればここから長さ情報が並び始めます。ORIGINは、メタデータ（可変長フィールドの長さ情報・NULLビットマップ・レコードヘッダー）とフィールドデータ本体とのあいだの境界で、フィールド1のデータはORIGINのすぐ下（アドレスの大きい側）から始まります。

ALTER TABLE ADD COLUMNとビットマップ

ALTER TABLE ... ADD COLUMNでは、ALGORITHM=INSTANTによってテーブル全体の再構築を避けられる場合があります。この方式をInstant ADDと呼びます。既存の行は物理的に書き換えず、新カラムの値はデフォルトとして参照され、新しく挿入する行だけが新カラムを物理レコードに含めます。一方、再構築が行われる場合は、全レコードを新しい構造で書き直すため、NULLビットマップも新スキーマに合わせて作り直されます。

メタデータの登録

Instant ADDされたカラムのデフォルト値は、カラム定義に紐づくデフォルト情報として保持されます。保持場所は、永続的にはデータ辞書（テーブル定義を格納するシステム領域）、実行時にはテーブルを開いたときメモリへ読み込まれる辞書キャッシュ内のカラム定義です。DEFAULT NULLの場合は、長さをUNIV_SQL_NULLとして登録します。UNIV_SQL_NULLはメモリ上でフィールドの長さとしてNULLを表す定数で、データへのポインタは無効です。オフセット構築やフィールド取得のときに参照されます。

既存レコード（Instant ADD前に挿入されたもの）

既存レコードの物理データには新カラムの領域がありません。レコードを読むたびに作られるオフセット配列（各フィールドの位置やNULLかどうかを保持するメモリ上の構造）を構築する処理で、そのカラムが物理レコード内にないと分かると、インデックス側のデフォルト情報を参照してオフセットを決めます。デフォルトがNULLなら、該当フィールドにデフォルト値であるというフラグREC_OFFS_DEFAULTとNULLであるというフラグREC_OFFS_SQL_NULLが立ちます。物理レコード上のビットマップは書き換えず、オフセット配列のフラグでデフォルトでありNULLであることを表現し、フィールド取得時は長さをUNIV_SQL_NULLとして返します。

このオフセット配列は永続化されず、SELECTで行を返すとき・レコード比較時・特定フィールドの取得時など、物理レコードにアクセスするたびにメモリ上に作り直されます。

新規レコード（Instant ADD後に挿入されたもの）

新規挿入では、新カラムを含めた物理レコードが作られます。InnoDBはページへ書き込む前に、挿入する行を、各フィールドの値とその値がNULLかどうかをまとめたタプルという中間的な形でメモリ上にいったん保持します。NULLのフィールドは長さをUNIV_SQL_NULLとします。これをページ上の物理レコードへ変換するとき、Nullableなフィールドを先頭から順に見ていき、NULLのフィールドがあればNULLビットマップの対応するビットを1にします。DEFAULT NULLの新カラムがNULLで挿入される場合も、通常のNullableフィールドと同じように該当ビットが1になり、データ部にはそのフィールドを置かず、ビットマップだけでNULLを表します。

セカンダリインデックスのNULL

セカンダリインデックスのキーには、Nullableなカラムを含められます。

UNIQUE制約を設定したインデックスでも、キー列にNULLを含む行は何行でも挿入できます。一意性のチェックではNULL同士を等しいとみなさないため、重複違反には該当しません。

インデックスのB-treeを走査・構築する際の比較処理では、メモリ上のフィールド長がUNIV_SQL_NULLかどうかでNULLを判定します。NULLと非NULL値を比較するとき、昇順（ASC）のインデックスではNULLを最小値として扱い、降順（DESC）では最大値として扱います。比較する両方のフィールドがNULLの場合は等価とみなします。

ページ内でも速く探したい

1つのページ（既定16KB）には、数十から数百件のレコードが載ります。目的のレコードを、この中からどう素早く見つけるかという問題があります。

レコードはヒープ領域に挿入順で置かれ、キー順のつながりはレコードヘッダーのnextポインタで表されます。nextは単方向リンクリストなので、N番目のレコードへ行くには先頭からnextをN回たどるしかありません。配列のように「何番目」を直接指定して飛ぶことができず、そのままでは二分探索も使えません。ページ内に100件あれば、最悪100回たどることになります。

Page Directory（ページディレクトリ）は、この制約を補うための索引です。ページ内に飛び石のようにスロットを置き、まずスロットへの二分探索でおおよその位置まで一気に絞り、そこからnextを数回たどって目的のレコードにたどり着けるようにします。

スロットは飛び石

Page Directoryは全レコードにスロットを用意するわけではなく、おおよそ4〜8レコードごとに1つのスロットを置くスパースな構造です。スパースとは、全件を網羅せず一部だけを持つことを指します。

なぜ全件に持たせないのかというと、全レコード分のポインタを並べるとスロット領域が大きくなり、そのぶんユーザーレコードに使える領域が減るからです。飛び石で足りるのは、スロットで大まかな位置まで絞ったあと、残りの数件はnextをたどれば済むためです。この「二分探索で範囲を絞る」と「短い線形探索で仕上げる」の2段構えが要点です。

スロットの中身と代表レコード

各スロットは、指し示すレコードのページ先頭からの相対オフセットを2バイトで持ちます。スロットにはオフセットだけが入り、「そのスロットが何件を代表するか」という管轄数は入っていません。管轄数は、スロットが指すレコード側のヘッダーにあるn_owned（4ビット）に格納されます。スロットが指すレコードは必ず代表となり、代表でないレコードはn_owned = 0です。役割をスロットとレコードヘッダーに分けることで、スロットを2バイトに抑えつつ、二分探索に必要な管轄数も参照できます。

各スロットの代表レコードは、そのスロットが管轄するレコード群のうちキー順で最も大きい（最後の）レコードです。管轄範囲は「前のスロットの代表の次」から「このスロットの代表」まで、両端を含みます。

Slot0は常にInfimum、Slot N-1は常にSupremumを指すため、スロット数は最低でも2です。ユーザーレコードがあれば、Slot1〜N-2がその代表を指します。

管轄数は、両端のスロットだけ扱いが違います。Slot0の管轄数は常に1です。Slot0には前のスロットがないので、管轄範囲の始点はレコード列の先頭であるInfimumになり、Infimumより小さいレコードは存在しないため、終点もInfimum、つまり管轄はInfimum自身の1件だけです。一方、Slot N-1の管轄数は1〜8で、最後の数件のユーザーレコードとSupremumを含みます。Supremumは「どのレコードより大きい」仮想レコードなので、必ずこのスロットの末尾に含まれます。中間のSlot1〜N-2は各4〜8件を管轄します。

ページ内での配置

Page Directoryは、ページの末尾側から先頭（オフセット0）側へ向かって成長します。File Trailerの直前、Free Spaceの直後付近に、各スロット（2バイトずつ）が並びます。スロットの個数そのものはPage Directoryには持たず、Page HeaderのPAGE_N_DIR_SLOTSが保持します。

この2つの領域は、あいだのFree Spaceを挟んで反対の端から中央へ向かって伸びていきます。ユーザーレコードはページの先頭側から下へ、Page Directoryはページの末尾側から上へ成長し、Free Spaceを少しずつ埋めていきます。Page Directoryの末尾側の端にあるSlot0（Infimum用）は位置が固定で動かないため、反対側から伸びてくるユーザーレコードと衝突しません。

スロットを1つ増やすときは、まず差し込む場所を空けます。差し込み位置よりFree Space側にあるスロットを、それぞれ2バイトずつページ先頭方向（Free Space側）へずらし、できた隙間に新しいスロットのオフセットを書き込みます。

ここで、ずらしたスロットの中身は書き換える必要がありません。スロットが持つのは指し先レコードのオフセット（位置）だけであり、レコード自体が動いていなければその位置は変わらないからです。スロットを別の場所へコピーしても、値はそのままで済みます。

具体例

キー順で101から108までの8件が載るページを考えます。論理的な並び（nextポインタ）は次のとおりです。

Page Directoryが次のようにスロットを置いたとします。

Slot0は常にInfimumを指します。Slot1は104を代表とし、101〜104の4件を管轄します。Slot2は常にSupremumを指し、105〜108とSupremumの5件を管轄します。スロットが指すのは各グループの末尾（代表）で、途中のレコードはnextでつなぎます。

各帯の右端が、そのスロットが指す代表レコードです。検索ではまず代表へ飛び、そのグループ内だけnextをたどります。

検索の2段階

1. スロットの二分探索

検索キーKに対し、Slot0からSlot N-1までを二分探索します。各スロットが指すレコードのキーとKを比べ、Kがそのレコードより大きいかどうかで範囲を半分ずつ絞ります。最終的に、範囲が隣り合う2スロットのあいだに収まった時点で終わります。

二分探索ができるのは、スロットの並び方に理由があります。1つのスロットが持つのは代表レコード1件分のオフセット（2バイト）だけですが、そのスロットがすべて同じ2バイト幅で、Page Directoryに隙間なく連続して並んでいます。つまりPage Directory全体が、固定長要素の配列になっています。要素が固定幅で並ぶ配列では、「先頭からスロット番号×2バイト」の計算で目的のスロットの位置がすぐ求まるため、スロット番号を指定すればO(1)で任意のスロット（＝代表レコードのオフセット）へ飛べます。

2. スロット間の線形探索

二分探索で得た2スロットのあいだのレコード群は、通常4〜8件です。ここからnextポインタをたどって順に比較し、目的のレコードを特定します。件数が少ないので、この線形探索はすぐに終わります。

挿入順序とページの割り当て

B-treeのリーフページは、INSERTでレコードが増えるほど埋まっていきます。空きがあればそのページに入りますが、満杯になるとページ分割が起き、新しいページが割り当てられます。このとき、どのページ番号を割り当てるかは主キー（またはインデックスキー）の挿入順序で変わります。InnoDBはページを割り当てるとき、単にエクステントの先頭から順番に取るのではなく、ヒントとよばれる次に使いたいページ番号の情報と方向を手がかりにします。

ヒントと方向は、insert_pointとPAGE_LAST_INSERTを比較して決まります。insert_pointは、新しいレコードよりキーが小さく、すぐ左隣にあるレコードです（先頭ならInfimum）。PAGE_LAST_INSERTはページヘッダーに記録された最後に挿入したレコードへのポインタです。この比較だけで、昇順連続・降順連続・ランダムのいずれかを判定します。2点しか見ない単純なヒューリスティックですが、AUTO_INCREMENTのような典型的なパターンはこれで十分効果を発揮します。

昇順の連続挿入

主キーを1, 2, 3のように昇順で入れると、新しいレコードは常にページの末尾になります。

検出条件はinsert_pointとPAGE_LAST_INSERTが一致することです。このとき昇順の連続挿入と判定され、ヒントは現在のページ番号 + 1、方向はFSP_UPになります。新しいページは現在のページ番号 + 1を優先して割り当てます。

このパターンの分割では、既存のレコードはすべて旧ページに残り、新規レコードだけが新ページに移ります。分割後の旧ページはほぼ満杯のまま残り、右へ新しいページが伸びていきます。公式ドキュメントでも、昇順または降順で連続挿入した場合のインデックスページは約15/16まで埋まるとされています（The Physical Structure of an InnoDB Index）。

満杯のページの末尾へ1001を入れようとした直後は、次の配置になります。

昇順と判定されていても、insert_pointの右側にレコードが2件以上ある場合は分割のしかたが変わります。このときは直後の1件だけ旧ページに残し、2件目以降はすべて新ページへ移します。

たとえば、大きなキーを先に入れておいてから間を昇順で埋めると、このパターンに当てはまります。ページが次の状態のとき、直前に50を入れて、続けて51を入れようとして満杯になったとします。

分割後は次のようになります。直後の1件（1000）だけ旧ページに残し、それ以降を新ページへ移します。そのうえで51を旧ページへ挿入します。

直後の1件（1000）を残すのは、その後も昇順の連続挿入が続いたときに、適応的ハッシュインデックス（AHI）が使えるようにするためです。挿入位置を探すとき、AHIはまず挿入キーのハッシュからページ上のレコードを1件引き当て、その推測が正しいかを同じページ上のレコードだけで確かめます。確認するのは、引き当てたレコード以上で、かつそのすぐ次のレコード未満に挿入キーが収まるかです。たとえば続けて52を挿入するとき51を引き当てれば、旧ページ内の51と1000だけで51 <= 52 < 1000が成り立つと分かり、挿入位置が正しいと確認できます。

もし1000も新ページへ移してしまい、旧ページが51の次でSupremumになっていたら、51のすぐ次に比較できる実レコードがありません。AHIは新ページを読まず、旧ページが次のページを持たない木の右端かどうかだけを見ます。もしも木の右端ならこのページの末尾が挿入位置になりますが、右端でなければ次のページがあるため、引き当てた位置が正しい挿入位置かどうかAHIだけでは判断できません。その場合はB-treeのルートからたどる通常の検索で挿入位置を決めます。1件を残しておくことで、AHIによって高速な挿入位置の特定が可能になります。

降順の連続挿入

主キーを1000, 999, 998のように降順で挿入すると、新しいレコードは常にページの先頭になります。

検出条件は「insert_pointの直後（論理順で次のレコード）とPAGE_LAST_INSERTが一致する」ことです。このとき降順の連続挿入と判定され、ヒントは現在のページ番号 - 1、方向はFSP_DOWNになります。新しいページは現在のページ番号 - 1を優先します。このパターンの分割では、既存のレコードはすべて旧ページに残り、新規レコードだけが新ページに入ります。

満杯のページの先頭へ0を入れようとした直後は、次の配置になります。

降順と判定されていても、insert_pointの左側に実レコードがある場合は分割のしかたが変わります。このときはinsert_pointより左のレコードを新ページへ移し、insert_point自体は旧ページに残します。新規レコードも旧ページへ入ります。

たとえば、小さなキーを先に入れておいてから間を降順で埋めると、このパターンに当てはまります。ページが次の状態のとき、直前に1000を入れて、続けて999を入れようとして満杯になったとします。

分割後は次のようになります。insert_pointである3未満を新ページへ移し、3は旧ページに残します。そのうえで999を旧ページへ挿入します。

insert_pointを旧ページに残すのは、998, 997, 996, ...と降順での挿入が続いたときに、1や2のようなinsert_point未満のレコードが分割のたびに新ページに移ることを防ぐためです。

ランダム挿入

主キーやインデックスキーがUUID、ハッシュ値、他テーブルから取った非連続IDなどランダムな値だと、前回と今回の挿入位置が隣接しないので、昇順にも降順にも当てはまりません。

このとき連続挿入とは判定されず、ヒントは現在のページ番号 + 1、方向はFSP_UPという既定値が使われます。ヒントと方向は昇順と同じですが、分割点は昇順・降順の規則を使わず、レコード件数の中央付近に置きます。次の挿入が左右どちらに来ても空きが残るよう、ページをほぼ半分に割るためです。

実際に割り当てられるページ

ヒントとしてページ番号が得られても、そのページが空いているとは限りません。そこでInnoDBは、次の優先順位で実際に割り当てるページを決めます。ここでの未使用率は(セグメントの空きページ数 / セグメントの全ページ数) × 100で、閾値は既定で12.5%です。使用ページ数の閾値はエクステントサイズの半分で、既定の16KBページでは32です。

1. ヒントページがセグメントに属していて空いていれば、そのまま割り当てる。
2. ヒントページを含むエクステントがどのセグメントにも属しておらず完全に空いていて、セグメントの未使用率が閾値未満で、かつ使用ページ数が32以上なら、そのエクステント全体をセグメントに割り当ててヒントページを使う。
3. 方向が指定されていて、未使用率が閾値未満で、使用ページ数が32以上なら、空きエクステントを取り、右方向では先頭ページ、左方向では末尾ページを割り当てる。空きエクステントはセグメントの完全空きリストを先に見て、無ければテーブルスペースから取る。取ったエクステントがフラグメントなら、右方向でも先頭ではなく最初の空きページになる。
4. ヒントページを含むエクステントがセグメントに属し空きがあれば、ヒントページの位置から末尾へ順に探し、無ければエクステント先頭に戻って探し、最初の空きページを割り当てる。
5. セグメントに空きページがあれば、満杯ではないエクステント、無ければ完全に空いたエクステントのリスト先頭を1つ取り、その先頭から最初の空きページを割り当てる。
6. セグメントの使用ページ数が32未満なら、テーブルスペースのフラグメントエクステントからページを割り当てる。
7. 以上すべてが失敗したら、セグメントの完全に空いたエクステント、テーブルスペースのフラグメントエクステント、テーブルスペースの完全に空いたエクステントの順にエクステントを取得し、先頭ページ（フラグメントなら最初の空きページ）を割り当てる。

できるだけ理想的な連続配置に近くなるようにフォールバックします。