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

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フィールドで、それ以降のカラムは持ちません。