InnoDBのデータ格納構造

2026/08/08

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

フィールド	意味
`FIL_PAGE_PREV`	前のページ番号。左端など前がなければ`FIL_NULL`
`FIL_PAGE_NEXT`	次のページ番号。右端など次がなければ`FIL_NULL`

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

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

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

階層	大きさ	役割
ページ	16KB	データ格納の最小単位
エクステント	64ページ（1MB）	連続した領域をまとめて割り当てる単位
セグメント	可変（複数エクステント）	インデックスのリーフ用・非リーフ用といった管理単位
フラグメントページ	1ページ	小さなセグメント向けの個別ページ

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

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

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

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

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

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

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

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

2種類のレコード

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

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

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

レコード	heap_no	役割	格納値
Infimum	0	下端。どのユーザーレコードよりも小さいとみなす	`"infimum\0"`（8バイト）
Supremum	1	上端。どのユーザーレコードよりも大きいとみなす	`"supremum"`（8バイト）

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

たとえばページに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のすぐ手前に位置します。

ブロック	サイズ	中身
`n_owned` + `info_bits`	1バイト	`n_owned`（4ビット）はページディレクトリのスロットが代表するレコード数。`info_bits`（4ビット）は削除マークなどのフラグ
`status` + `heap_no`	2バイト	`status`（3ビット）はレコードの種類（通常・ノードポインタ・infimum・supremum）。残り13ビットが`heap_no`（ページ内の通し番号）
`next`	2バイト	キー順で次のレコードへの相対オフセット。単方向リンクリストのポインタ

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ではインラインに残します。行外に出すときのページ内の残り方は、行フォーマットで異なります。

行フォーマット	行外に出すときの扱い
COMPACT / REDUNDANT	先頭768バイト程度と約20バイトのポインタをリーフに残し、残りを外部ページへ
DYNAMIC（MySQL 8.4の既定）	約20バイトのポインタだけをリーフに置き、値本体は外部ページへ
COMPRESSED	DYNAMICと同様だが、`KEY_BLOCK_SIZE`によってリーフに残す量を変えられる

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

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

非リーフノード（ルートと中間）のユーザーレコードには、行データではなく子ページへの案内であるノードポインタが入ります。中身は「キープレフィックス＋子ページ番号（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フィールドで、それ以降のカラムは持ちません。

NULLは値ではなく状態

SQLのNULLは「0」でも「空文字」でもなく、「値が存在しない」という状態です。InnoDBはこの状態を、MySQL 8.4で標準的なCOMPACT系（COMPACT・DYNAMIC・COMPRESSED。既定の行フォーマットはDYNAMIC）では、データ領域を使わずに表現します。NULLのフィールドにはデータを1バイトも置かず、代わりに「このフィールドはNULLだ」という印だけを別の場所に立てます。値がないものにわざわざ領域を割り当てないので、オーバーヘッドは最小限で済みます。一方、古いREDUNDANT行フォーマットでは、可変長カラムのNULLはデータ部を使いませんが、固定長カラムのNULLでもその固定長分のデータ領域を予約します。

ここでフィールドという語を整理しておきます。フィールドとは、テーブルの1カラムに対応する値の格納領域です。レコードは、レコードヘッダーとメタデータ（NULLビットマップや可変長フィールドの長さ情報）に続いて、データ部が並ぶ構造です。データ部はORIGIN（データ先頭）から始まり、主キーや各カラムが定義順に置かれます。このデータ部の「1カラム分」が1フィールドです。id、name、emailの3カラムなら、データ部はフィールド0（id）、フィールド1（name）、フィールド2（email）の順に並びます。レコードヘッダーやNULLビットマップはフィールドには含まれず、フィールドの有無や長さを管理する補助情報です。

内部ではUNIV_SQL_NULLで表す

InnoDBの内部処理では、フィールドの長さを表す値として特殊な定数UNIV_SQL_NULLを使います。フィールドの長さがこの値になっていれば、そのフィールドはNULLだと解釈され、データへのポインタは無効として扱われます。比較やオフセット計算のたびに「長さがUNIV_SQL_NULLか」を見てNULLかどうかを判定するので、行フォーマットの違いをまたいで一貫した扱いができます。

NULLビットマップ

COMPACT系の行フォーマット（COMPACT・DYNAMIC・COMPRESSED）では、NULLになり得る（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のすぐ下（アドレスの大きい側）から始まります。

図にある「可変長フィールドの長さ情報」は、VARCHARやTEXTのように値のバイト数が行ごとに変わるカラムの長さを記録したメタデータで、NULLビットマップよりもさらにアドレスの小さい側（record start寄り）に置かれます。可変長フィールドが0個なら、この領域そのものが存在せず、レコードはNULLビットマップから始まります。

なぜデータ領域を割り当てないのか

NULLは値がない状態なので、そもそも格納する値がありません。仮にデータ領域を割り当ててしまうと、「0が入っているフィールド」と「NULLのフィールド」の区別が難しくなり、解釈が曖昧になります。ビットやオフセットのフラグで「NULLである」と明示すれば、データ領域を一切使わずに状態を伝えられ、区別も明確です。加えて、NULLの多い行ではデータを省けるぶんレコードが小さくなり、1ページに載る行数を増やせます。

ALTER TABLE ADD COLUMNとビットマップ

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

ここが少しややこしい点です。同じDEFAULT NULLの新カラムでも、その行がInstant ADDの前に挿入されたか後かで、NULLの表し方が変わります。ADD前からある既存の行には、物理レコードに新カラムの領域がなく、NULLビットマップにもそのカラム用のビットがありません。そのため、ビットマップではNULLを表せず、別の方法で補います。一方、ADD後に挿入された行には新カラムが物理レコードに含まれるので、通常のNullableカラムと同じくビットマップのビットでNULLを表します。

メタデータの登録

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

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

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

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

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

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

インデックスでのNULL

主キー（クラスタ化インデックス）

主キーのカラムには通常NOT NULL制約が課されます。主キーがNULLになり得ると、B-treeのキー順序や一意性の保証に支障が出るため、InnoDBは主キーにNULLを含むテーブル定義を基本的に許容しません。MySQLのCREATE TABLEでも、主キーはデフォルトでNOT NULLになります。

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

セカンダリインデックスのキーには、Nullableなカラムを含められます。ここで誤解しやすいのは、UNIQUE制約が付いていればNULLも1行しか入れられない、と思ってしまう点です。実際にはそうではなく、UNIQUEなセカンダリインデックスでも、キー列のいずれかがNULLの行は何行でも挿入できます（キー列がすべてNULLの場合も含みます）。一意性チェックではNULL同士を「等しくない」とみなすため、NULLを含むキーは重複と判定されないからです。実装内部では、比較時にnulls_unequalやハンドラ側のHA_NULL_ARE_EQUALといったフラグで、NULL同士を等価とみなすかどうかが切り替わります。MySQLの通常のUNIQUE制約は、上記のとおりNULL同士を等しくない扱いにします。

レコード比較でのNULL

レコード同士を比較するとき、どちらかのフィールドがNULLだと特別な処理になります。両方がNULLなら、nulls_unequalが有効なときは「等しくない」とし、そうでなければ比較を続けます。一方がNULLで他方が非NULLのときは、インデックスカラムが昇順（ASC）ならNULLを最小として扱い、ソート順ではNULLが先に来ます。降順（DESC）で定義されているときは逆にNULLを最大として扱い、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	1
Slot1	104	4
Slot2	supremum	5

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の育ち方が変わる

B-treeのリーフページは、INSERTでレコードが増えるほど埋まっていきます。空きがあればそのページに入りますが、満杯になるとページ分割が起き、新しいページが割り当てられて木が広がります。このとき、どの方向にどう伸びるかは、主キー（またはインデックスキー）の挿入順序で大きく変わります。同じ件数を入れても、順序次第でページの詰まり具合が変わり、結果として範囲スキャンの速さやディスク使用量に差が出ます。

InnoDBはページを割り当てるとき、単にエクステントの先頭から順番に取るのではなく、ヒント（次に使いたいページ番号）と方向を手がかりにした最適化を行います。

直前の挿入と比べて向きを決める

ヒントと方向は、今回の挿入位置と前回の挿入位置を比べて決まります。ページヘッダーには最後に挿入したレコードへのポインタ（PAGE_LAST_INSERT）が記録されていて、挿入処理ではカーソルが指すレコード（insert_point）をこれと突き合わせます。この比較だけで、昇順連続・降順連続・ランダムのいずれかを判定します。2点しか見ない単純なヒューリスティックですが、AUTO_INCREMENTのような典型的なパターンはこれで十分に捉えられます。

昇順の連続挿入

主キーを1, 2, 3のように昇順（AUTO_INCREMENTを含む）で入れると、新しいレコードは常にページの末尾（Supremumの直前）に付きます。前回入れたレコードのすぐ後ろに、次のレコードが入るパターンです。

検出条件は「insert_pointとPAGE_LAST_INSERTが一致する」ことです。このとき右方向（昇順）への連続挿入と判定され、ヒントは現在のページ番号 + 1、方向はFSP_UPになります。新しいページは現在のページの右隣（ページ番号が1大きい側）を優先して割り当てます。論理的に連続するレコードが物理的にも連続したページに並ぶので、範囲スキャンでのシーケンシャルI/Oが効きます。

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

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

998〜1000は旧ページに残ったままです。1001だけが新ページの先頭に載ります。

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

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

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

直後の1件（1000）を残すのは、その後も昇順の連続挿入が続いたときに、適応的ハッシュインデックス（AHI）が使えるようにするためです。AHIは「次に挿入するキーはこのページに入る」という推測を、そのページにある実際のレコードとキーを比較して確かめます。たとえば続けて52を挿入するときは、旧ページ内の51と1000という実レコードに52を挟み込めるかを見るだけで、挿入位置が正しいと確認できます。もし1000も新ページへ移してしまい旧ページが51の次でSupremumになっていたら、比較できる実レコードが旧ページの右端になく、隣の新ページまで読みに行かないと挿入位置を確認できません。1件を残しておくことで、隣のページを読みに行かずに済み、連続挿入でもAHIによる高速化が保たれます。

一方、新ページ側には大きなキーが数件しか残らないことがあります。右端への純粋な昇順分割と違い、移る件数が少ないまま新しいページが増えるので、隙間の多い（スパースな）ページが並びやすくなります。

分割する前に、右隣ページがすでに存在して空きがあれば、そのページへ直接挿入して分割を避けられる場合もあります。ただし右端への昇順挿入では常に木の最も右のページへ入るため、右隣が存在することは少なく、多くの場合は分割になります。

降順の連続挿入

主キーを1000, 999, 998のように降順で入れると、新しいレコードは常にページの先頭付近（Infimumの直後）に付きます。前回入れたレコードのすぐ前に、次のレコードが入るパターンです。

検出条件は「insert_pointの直後（論理順で次のレコード）とPAGE_LAST_INSERTが一致する」ことです。このとき左方向（降順）への連続挿入と判定され、ヒントは現在のページ番号 - 1、方向はFSP_DOWNになります。新しいページは現在のページの左隣を優先します。降順ではページが満杯になると、左方向へ新しいページを伸ばす形で木が育ちます。

ランダム挿入

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

このとき連続挿入とは判定されず、ヒントは現在のページ番号 + 1、方向はFSP_UPという既定値が使われます。ヒントと方向は昇順と同じですが、実際の挿入位置はページ内のあちこちになるため、分割は中央付近で行う一般的な分割になります。新規ページは右隣を優先するものの、論理的な連続性が保証されないので、範囲スキャン時のディスクアクセスは昇順・降順ほど最適化されません。

挿入パターンのまとめ

挿入パターン	検出条件	ヒント	方向	新規ページの配置優先
昇順	`PAGE_LAST_INSERT` == insert_point	page_no + 1	`FSP_UP`	右隣
降順	`PAGE_LAST_INSERT` == insert_pointの次	page_no - 1	`FSP_DOWN`	左隣
ランダム	上記のいずれでもない	page_no + 1	`FSP_UP`	右隣（既定）

昇順・降順の連続挿入は、それぞれ右方向・左方向への物理的な連続配置を促し、範囲スキャンを速くします。ランダム挿入ではその最適化が働かず、ページのフラグメンテーション（隙間の多いページが散らばること）が進みやすくなります。DELETEやUPDATEでレコードが減り、ページの使用率がマージ閾値（既定50%）を下回ると、隣のページとのマージが試みられ、スパースなページの解消につながります。もっとも挿入だけの追記型ワークロードではマージは起きにくく、右端への昇順ではほぼ満杯のページが並びます。溜まったフラグメンテーションはOPTIMIZE TABLEでテーブルを再構築すればまとめて解消できます。

ヒントページから実際に割り当てるまで

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

ヒントページがセグメントに属していて空いていれば、そのまま割り当てる。
ヒントページを含むエクステントが空いていて、セグメントの未使用率が閾値未満で、かつ使用ページ数が32以上なら、そのエクステント全体をセグメントに割り当ててヒントページを使う。
方向が指定されていて、未使用率が閾値未満で、使用ページ数が32以上なら、右方向では新規エクステントの先頭ページ、左方向では末尾ページを割り当てる。
ヒントページを含むエクステントがセグメントに属し空きがあれば、ヒントページの位置から順に探し、最初の空きページを割り当てる。
セグメントに空きページがあれば、割り当て済みエクステントの先頭（オフセット0）から探し、最初の空きページを割り当てる。
セグメントの使用ページ数が32未満なら、テーブルスペースのフラグメントエクステントからページを割り当てる。
以上すべてが失敗したら、セグメントの完全に空いたエクステント、テーブルスペースのフラグメントエクステント、テーブルスペースの完全に空いたエクステントの順にエクステントを取得して割り当てる。

段階が進むほど「理想的な連続配置」から離れていきますが、まず理想を狙い、駄目なら次善へ落とす、という順序になっています。使用ページ数が32未満のうちはフラグメントページから細かく取る点は、テーブルが小さいうちに領域を無駄にしない方針とつながっています。