行は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に達すると、そこからはエクステント単位でまとめて割り当てるように切り替わります。小さいうちは節約し、育ってきたら連続領域でまとめて確保する、という段階的な方針です。

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

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

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

挿入パターンのまとめ

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

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

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

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

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

ディスクI/Oを減らすキャッシュ

バッファプール（Buffer Pool）は、InnoDBがディスク上のデータページとインデックスページをメモリ上にキャッシュしておく領域です。ここで注意したいのは、バッファプールは検索でたどるページ数そのものを減らす仕組みではない、という点です。B-treeを何ページたどるかは変わりません。変わるのは、そのページをディスクから読むのか、すでにメモリにあるものを使うのか、という部分です。よくアクセスされるページがメモリに載っていれば、遅いディスクI/Oを避けられ、処理が速くなります。

バッファプールは16KBのページ単位で、ディスク上のInnoDBページをキャッシュします。載るのはB-treeのデータページやインデックスページだけでなく、undoログやチェンジバッファなど、InnoDBが扱う各種ページです。ディスク上の1ページとバッファプール上の1フレームは1対1に対応し、ページサイズが16KBである限り、ページを格納するメモリ領域も16KBです。

制御ブロックとバッファフレーム

バッファプール内の各ページは、制御ブロック（control block）とバッファフレーム（buffer frame）の2つで管理されます。バッファフレームは、ページデータそのものを置く16KBのメモリ領域です。制御ブロックには、ページの状態、このページを参照中のスレッド数（バッファフィックス数）、I/Oの状態、各種リストへのリンクといった、ファイルには書かない管理用の情報が入ります。

データ本体と管理情報を分けておくことで、ページの中身に触れずに状態やリンクだけを操作できます。

ページを管理するリストとハッシュ

バッファプールは、制御ブロックを複数のリストと、検索用のハッシュテーブルで管理します。それぞれ役割が違い、ページの配置・追い出し・書き出しに使われます。

ページを読むときの流れはこうです。まずページハッシュで、そのページがすでにバッファプールにあるか調べます。なければ空きリストからブロックを取り、空きがなければLRUリストの末尾から追い出し候補を探して置き換えます。読み込んだページはLRUリストに載ります。ページを更新すると、そのブロックはフラッシュリストにも登録され、適切なタイミングでディスクへ書き出されます。

LRUを2つに分ける理由

LRUリストは、素朴なLRU（Least Recently Used、最近最も使われていないものから捨てる）ではなく、2つのサブリストに分けた変形LRUで管理されます。なぜひと工夫が必要なのでしょうか。

素朴なLRUでは、新しく読んだページは必ずリストの先頭に入ります。ここで大きなテーブルの全件スキャンや事前読み込み（read-ahead。次に必要になりそうな連続ページを先読みする処理）が走ると、スキャン対象のページが一気に先頭へなだれ込み、それまで頻繁に使っていたホットなページを末尾へ押し出してしまいます。多くは1回しか読まないページなのに、大事なページを追い出してしまうわけです。

そこでLRUリストを、頻繁に使うページのnew（young）サブリストと、あまり使われていないページのoldサブリストに分けます。既定ではバッファプールの3/8がoldサブリストです。ディスクから新しく読んだページは、先頭ではなくmidpoint（newとoldの境界）に挿入されます。こうすると、1回しか読まないスキャン由来のページはいきなりnew側へは入らず、old側でしばらく過ごしてから追い出されます。

oldサブリストのページが再びアクセスされ、かつ最初にアクセスされてから一定時間（既定1000ミリ秒）が経っていれば、そのページはnewサブリストの先頭へ移ります（young化）。すぐに再アクセスされないページは、他のページのyoung化に押されて徐々に末尾へ寄り、やがて追い出し対象になります。一時的なスキャンがホットデータを追い出しにくくなるのが、この2分割の狙いです。

追い出しとフラッシュ

バッファプールに空きがなく新しいページを読みたいとき、LRUリストの末尾付近から追い出せるブロックを探します。その候補がクリーン（未更新のまま）なら、そのまま捨てて構いません。しかしダーティ（メモリ上で更新済みでまだディスクへ書いていない）なら、そのまま捨てると更新内容が消えてしまいます。そこで、追い出す前にディスクへ書き出します。この書き出しをフラッシュと呼びます。フラッシュには、目的と契機の違うLRUフラッシュとリストフラッシュの2種類があります。

LRUフラッシュ

LRUフラッシュは、追い出し用の空きブロックを確保するためのフラッシュです。新しいページを読むには、使っていないブロックを1つ追い出す必要があります。その候補がクリーンならそのまま追い出せますが、ダーティなら追い出す前にフラッシュしなければなりません。

ただ、追い出しのたびに1件ずつフラッシュを待つと読み込みが遅れます。特にLRU末尾付近にダーティページが続くと、待ち時間が積み重なります。そこで、バックグラウンドのページクリーナースレッドが、追い出しに備えてLRU末尾のダーティページを前もってフラッシュしておきます。こうしておけば、いざ追い出しが必要になったとき、すでにクリーンになったブロックをすぐ使えます。いずれにせよLRUフラッシュは、LRUリストの末尾方向からダーティページを探し、追い出し用のブロックを確保するために行うフラッシュです。

リストフラッシュ

リストフラッシュは、redoログのチェックポイントを進めるためのフラッシュです。redoログはクラッシュリカバリ用に変更履歴を記録しますが、ファイルの合計サイズには上限があり、古い領域をリングバッファとして再利用（上書き）します。上書きしてよいのは「その変更はもうディスク上のデータページへ反映済み」と言える範囲だけです。この境界を表すのがチェックポイントLSNで、これを進めるには、そのLSN以前の変更をすべてディスクのデータファイルへ書き出しておく必要があります。書き出していないと、クラッシュ後に古いログが必要になったとき、対応するページがディスクにないことになってしまいます。

フラッシュリストは、各ページの「最も古い更新のLSN」順に並んでいます。つまり末尾ほど古い変更を持つページです。リストフラッシュでは、このフラッシュリストの末尾（最も古いダーティページ）から順にディスクへ書き出します。十分な数を書き出せればチェックポイントLSNを進められ、redoログの再利用できる範囲が広がります。リストフラッシュは、チェックポイントの進行に合わせてバックグラウンドで継続的に行われます。

セカンダリインデックス更新の読み込みを先送りする

チェンジバッファ（Change Buffer）は、主に非ユニークなセカンダリインデックスへのINSERT・UPDATE・DELETEを、対象ページがバッファプールにないときに一時的に溜めておく仕組みです。溜めた変更は、あとでそのページがバッファプールへ読み込まれたタイミングでまとめて適用（マージ）します。狙いは、セカンダリインデックスを更新するためだけのディスクからのランダム読み込みを先送りして減らすことです。

なぜセカンダリインデックスで問題になるのかを押さえておきます。クラスタ化インデックス（主キー）のページは、挿入も更新もキー順で近い位置に集まりやすく、バッファプールに載っていることが多いです。一方、セカンダリインデックスは非ユニークなことが多く、更新される順序もばらばらになりがちで、更新したいリーフページがバッファプールにないことが頻繁に起きます。そのたびにディスクからページを読むとランダムI/Oがかさみます。チェンジバッファは、そういうとき毎回ページを読む代わりに変更内容だけを別のB-treeに記録し、後でまとめて適用します。

redoログとの違い

InnoDBには、I/Oを減らす仕組みとしてredoログもあります。名前も役割も似て見えますが、減らすI/Oの向きが逆です。

redoログは、変更したページを実際にディスクへ書き出すタイミングを先送りします。変更内容をまずログに記録しておけば、対象のデータページ自体は後からバックグラウンドで書き出せるため、コミットのたびにページの書き出し完了を待つ必要がありません。つまり書き出し側のI/Oを整えます。

チェンジバッファは、ページをディスクから読み込むタイミングを先送りします。セカンダリインデックスを更新したいのに対象ページがメモリにないとき、そのページを読まずに変更だけを記録し、実際に読むのは必要になったときまで遅らせます。つまり読み込み側のランダムI/Oを減らします。redoログが「書き出し」、チェンジバッファが「読み込み」を受け持つ、と対で覚えると整理できます。

どこに保存されるか

チェンジバッファに溜まっているのは、まだ実際のインデックスページへ反映していない未適用の変更です。ということは、サーバーをshutdownしてもこの変更が失われてはいけません。マージは対象ページが読み込まれるときに行うため、shutdown時点ではマージ待ちの変更が残っている可能性があり、次回起動後に正しく適用できなければデータの整合性が壊れます。

そこで、チェンジバッファの実体はディスク上にも永続化されます。チェンジバッファ用のB-treeは、通常のInnoDBデータページと同じくシステムテーブルスペース内に置かれます。メモリ上ではバッファプールの一部を占め、ディスク上ではB-treeとして保持されます。永続化の仕組みも他のページと変わりません。InnoDBはWAL（Write-Ahead Logging）を採用しており、ページをディスクへ書く前に変更をredoログへ記録します。コミット時にはredoログをフラッシュすればよく、実際のデータページ（チェンジバッファのB-treeページを含む）は後からバックグラウンドで書き出されます。再起動時にはredoログのリカバリでチェンジバッファも復元され、該当ページが読まれるたびにマージされます。

このB-treeのキーは「テーブルスペースIDとページ番号」の組み合わせで、どのセカンダリインデックスのどのページに対する変更かを識別します。各エントリには、適用すべき変更（挿入レコード、削除マーク、物理削除）が入ります。

注文テーブルに、非ユニークなセカンダリインデックス（customer_id）があるとします。customer_id='alice01'の注文id=102を入れるとき、そのキーが載るセカンダリリーフ（ページ42）がバッファプールになければ、ディスク上のページ42は読みません。ディスクのページ42にはすでに(alice01,101)と(alice01,103)があり、新しい(alice01,102)はチェンジバッファにだけ残ります。あとでページ42がディスクからバッファプールへ読まれると、102がメモリ上のリーフへマージされ、チェンジバッファのそのエントリは消えます。ディスク上のページ42は、このマージだけでは書き換わらず、ダーティページがフラッシュされるタイミングでディスクに書き込まれます。

バッファできる操作

チェンジバッファが扱う操作は3種類です。

UPDATEは、セカンダリインデックスでは「旧キーの削除マーク」と「新キーの挿入」に分解され、上記の組み合わせになります。主な対象は非ユニークなセカンダリインデックスです。

いつマージされるか

対象ページがバッファプールへ読み込まれたとき

SELECTや範囲スキャンなどでそのセカンダリインデックスのページがディスクから読まれるとき、チェンジバッファのB-treeを引き、そのページ宛ての変更があればマージします。読むついでに反映するので、先送りしていた読み込みが1回で片付きます。

バックグラウンドのpurge

purgeは、削除マーク付きレコードのうちどのRead Viewからも不要になったものを物理削除するバックグラウンド処理です。セカンダリインデックスではUPDATEが削除マークと挿入で表されるため、purgeがセカンダリインデックスのページを読むとき、そのページ宛てのチェンジバッファのエントリがあればマージされます。また、システムがアイドルに近いときやslow shutdown時には、メインスレッドが積極的にマージを進め、チェンジバッファが肥大化しすぎるのを防ぎます。

サーバー再起動後のリカバリ

クラッシュリカバリのときも、該当ページが読み込まれる過程でマージされます。

マージは必ず成功しなければなりません。マージは対象ページを読み込む処理の一部としてその場で行われ、失敗しても後からやり直す手段がないからです。そこでチェンジバッファは、変更を溜める時点で各ページの空き領域をビットマップで追跡し、実際の空き容量を超えるような変更は溜めないようにしています。こうして、マージを実行する段階になって初めて「空きが足りない」と分かるような不整合が起きないようにしています。

バッファされない場合

ユニークなセカンダリインデックスへのINSERTは、原則としてバッファできません。一意性を確認するには結局その対象ページを読む必要があり、読むならわざわざ先送りする意味がないからです。unique_checks=0のときは例外的にバッファできる場合がありますが、重複を挿入してしまうリスクがあります。なお、ユニークセカンダリでもDELETE_MARKや物理DELETEはバッファ対象になり得ます。

また、チェンジバッファのマージ処理は昇順インデックス向けに設計されているため、降順インデックスが関わるものには使われません。降順インデックスとは、CREATE INDEX ... ON t (col DESC)のように列を降順でソートするインデックスです。セカンダリインデックス自体が降順インデックス列を含む場合と、主キーに降順インデックス列を含むテーブルのセカンダリインデックスの場合が該当し、いずれも降順が関与するためチェンジバッファは使われません。

サイズと有効化の設定

チェンジバッファが占める最大サイズは、バッファプールに対する割合で指定します。innodb_change_buffer_max_sizeの既定は25で、バッファプールの最大25パーセントまで使えます。最大値は50です。

どの操作をバッファするかはinnodb_change_bufferingで制御します。MySQL 8.4では既定がnone（バッファしない）で、8.0系では既定がall（INSERT・DELETE_MARK・DELETEのすべてをバッファする）でした。設定値はいつでも変更でき、変更は新しい操作のバッファ有無にだけ効きます。すでに溜まっている分のマージには影響しません。

B-treeたどりを飛ばす近道

適応的ハッシュインデックス（Adaptive Hash Index）は、点検索（等価検索）を速くするための機構です。通常のB-tree検索では、ルートから中間ノードを経てリーフまで複数ページをたどる必要があります。もし同じキーへの検索が何度も繰り返されるなら、毎回この経路をたどるのは無駄です。適応的ハッシュインデックスは、InnoDBがB-treeの検索パターンを監視し、よくアクセスされるリーフページについて、キー値からバッファプール上の着地レコードへ直接飛べる参照を自動で構築します。

user_id='alice01'、name='Alice'を探すとき、ハッシュに載っていればルートと中間ノードを経ずに、リーフ上のそのレコードへ着地します。

左が毎回たどるページ、右がハッシュから同じリーフへ飛ぶ参照です。着地点はバッファプール上のレコードなので、対象ページがメモリにないときはこの近道は使えません。

「適応的」というのは、開発者が設定するのではなく、InnoDBが実際の検索傾向を見て必要なところだけ勝手に作る、という意味です。テーブルがほぼメモリに収まり、適したワークロードであれば、この近道によってインメモリデータベースに近い検索性能が得られます。トランザクション機能や信頼性を犠牲にするわけではありません。有効・無効はinnodb_adaptive_hash_indexで切り替えられます。MySQL 8.4では既定がOFFですが、8.0系では既定がONでした。

何をキーにハッシュを作るか

各ハッシュエントリは、インデックスキーのプレフィックス（先頭部分）からハッシュ値を計算し、そのプレフィックスに対応するバッファプール上の着地レコードへの参照を持ちます。点検索でキーが指定されると、ハッシュテーブルを引いて該当レコード（とそのページ）へ直接アクセスします。

プレフィックスはn_fields（列数）とn_bytes（バイト数）で定義されます。n_fieldsはプレフィックスに含めるインデックスキー列の数で、先頭からn_fields列を列全体として使います。n_bytesは、その次の列の先頭何バイトを含めるかです。列の境界でちょうど終わるならn_bytesは0になります。

例えば(user_id, name)の複合セカンダリインデックスで、user_id='alice01'、name='Alice'という行を考えます。n_fields=2、n_bytes=0なら、プレフィックスはuser_idとnameをまるごと使った'alice01' + 'Alice'です。一方n_fields=1、n_bytes=3なら、user_id列全体に加えて次のname列の先頭3バイトだけを使い、'alice01' + 'Ali'がプレフィックスになります。

構築のきっかけも決まっています。同じ検索パターン（同じプレフィックス）でのヒットが連続した回数を、InnoDBがインデックスごとにメモリ上のカウンタで数えており、テーブルの列やユーザーが直接参照・設定できるものではありません。この回数が一定を超えると、そのとき検索していたページに対してハッシュエントリが作られます。検索パターンが変わるとカウンタはリセットされます。逆に、ハッシュでヒットしない検索が続くと、新規の構築は控えられます（すでにあるエントリを消すわけではありません）。

検索パターンに合わせて調整する

プレフィックスの具体的な長さ（n_fieldsとn_bytes）は固定ではなく、検索でヒットしやすく、かつエントリ数を抑えられる長さが選ばれます。

同一リーフページ内で同じプレフィックスを持つレコードは1つのグループになり、各グループからは左端または右端の1件だけがハッシュに登録されます。1ページあたりのエントリ数を抑えるためです。ハッシュの目的は、正確なレコード位置をピンポイントで当てることではなく、該当ページ（またはページ内の着地点）へ到達することにあります。だからプレフィックスがユニークでなくても構いません。代表レコードに着いたあと、ページ内を少し走査して目的のキーを探せば足ります。ユニークにしなければ1エントリで複数レコードをカバーでき、メモリ効率が良くなります。左端と右端のどちらを取るかは、そのインデックスの検索パターンに応じて決まります。

検索頻度の高いページほど構築の閾値に達しやすく、限られた容量の中で優先的にハッシュ化されます。検索パターンが変わったときには推奨プレフィックスが更新され、ハッシュが作り直されます。

エントリが消えるとき

適応的ハッシュインデックスは増える一方ではなく、次の契機で削除されます。

参照先のB-treeリーフページがバッファプールから追い出されると、そのページを指すハッシュエントリは削除されます。メモリ上にないページへの参照は無効だからです。また、ページ分割やページ破棄などB-tree構造が変わったときも、該当するエントリが削除されます。ハッシュエントリは「キーKはページPにある」と記録していますが、分割でレコードが別のページへ移ると、この対応が壊れてしまうためです。

右端への連続昇順挿入で分割が起きる場合は、この削除の影響が小さく済みます。新しく挿入されたレコードだけが新ページへ移り、既存レコードはページ番号ごと旧ページにそのまま残るため、既存キーと「そのキーがどのページにあるか」という対応関係は分割の前後で変わりません。そのため、旧ページのハッシュエントリが分割で消えたあとに同じキーへ検索が来ても、B-treeをたどれば以前と同じ旧ページに行き着いてすぐ見つかり、以前と同じ対応関係でハッシュエントリがすぐに作り直されます。

クラッシュしても変更を失わないための記録

redoログは、InnoDBがクラッシュリカバリを実現するために持つ変更履歴です。INSERT・UPDATE・DELETEでバッファプール内のページを更新すると、そのページをディスクへ書き出す前に、まず「どのページのどの位置に何を書いたか」という変更内容をredoログに記録します。もしサーバーがクラッシュしても、再起動時にチェックポイントLSN（LSNはLog Sequence Numberの略で、redoログに記録された変更の順序を表す通し番号）以降のredoログをLSNの若い順に適用すれば、ディスクへ反映しきれていなかった変更を復元できます。

ここで自然にわく疑問は、「更新したページをそのままディスクへ書けばいいのでは」というものです。実は、それだと性能が持ちません。コミットの時点では、更新したページの多くはまだバッファプール内にあります。コミットのたびに関係するダーティページをすべてディスクへ書き出すと、そのつど大量のランダムI/Oが発生します。一方、redoログは追記型で、順番に書いていくシーケンシャルな書き込みで済みます。コミット時にはredoログだけをディスクへフラッシュし、実際のページは後からバックグラウンドでゆっくり書き出せます。こうすればコミットのレスポンスを保ちつつ、クラッシュ時にも変更を失いません。この「先にログ、後からページ」という考え方をWAL（Write-Ahead Logging）と呼びます。

ページ10のnameをAliceからBobへ更新し、コミットした直後は次の配置になります。バッファプール上のページ10はすでにBobですが、データファイル上の同じページはまだAliceです。ディスクへ先に乗っているのは、redoファイルへ追記した「ページ10のnameをBobに」という記録です。

矢印はコミット時にディスクへ書き出される経路です。データファイル側のページ10は、あとからフラッシュされるまでAliceのままです。クラッシュしても、redoの記録からバッファプール上のBobを復元できます。

ログファイルの構成

redoログは、ログバッファ（Log Buffer）というメモリ領域を経て、ディスク上のredoログファイルへ書き出されます。MySQL 8.0.30以降・8.4では、redoログはデータディレクトリ配下の#innodb_redoディレクトリに複数のファイルとして置かれ、InnoDBは既定でこれを32個のファイルに保とうとします。各ファイルのサイズは、innodb_redo_log_capacityで指定するredoログ全体の合計容量の32分の1で、実際に使われている「使用中（ordinary）」ファイルと、次に使う予定でファイル名に_tmpが付く「予備（spare）」ファイルの2種類があります。

書き込みはLSNの若い順にファイルをまたいで進み、複数のファイル全体を1つの大きなリングとして扱います。リングといっても、データページどうしをポインタでつなぐ方式ではありません。各ファイルが「次のファイル」への参照を中に持っているわけではなく、次に使うファイルは番号順で決まります。#ib_redo0の次は#ib_redo1、最後のファイルの次はまた#ib_redo0です。あるファイルがend_lsnで終わると、次のファイルはそのend_lsnから始まります。あるファイルの内容がすでにチェックポイントを通過し、データページへ反映済みとみなせるようになると、そのファイルは上書きして再利用できます。ファイル単位で使用中・予備を入れ替えられる構造のおかげで、innodb_redo_log_capacityを変更してもサーバーを再起動せずに容量をオンラインで変えられます。

容量の指定方法はバージョンで異なります。MySQL 8.0.30以降はinnodb_redo_log_capacityで合計容量（32ファイル分の合計サイズ）を指定し、既定は100MBです。この変数は実行中にも変更できます。それ以前はinnodb_log_file_size（既定48MB）とinnodb_log_files_in_group（既定2）でファイルサイズと個数を指定していましたが、MySQL 8.4では非推奨です。

LSNとチェックポイント

LSN（Log Sequence Number）は、redoログの論理的な位置を表す番号です。ログはLSNの小さい順に生成され、リカバリでもLSNの若い順に適用します。途中を飛ばすことはできません。

チェックポイントLSNは、「このLSN以前のredoログが記述する変更は、すでにディスク上のデータページへ反映されている」という境界を表します。チェックポイントより前のログ領域は上書きして再利用できます。チェックポイントを進めるには、そのLSNに対応する変更をすべてデータページへフラッシュしておく必要があります。バッファプールのリストフラッシュが、まさにこの目的で行われます。redoログの再利用できる範囲と、ダーティページをどれだけ書き出したかは、こうして連動しています。

複数ファイルを1つのリングとして見たときの配置は、次のようになります。図の各箱が#innodb_redo内の1ファイルです。実際は既定32個ですが、ここでは3個に省略しています。矢印はファイル内のポインタではなく、番号順の「次のファイル」です。#ib_redo0の末尾LSN=4000から#ib_redo1が始まり、#ib_redo2の書き込み先端LSN=7200の次は、一周して#ib_redo0へ戻ります。#ib_redo0はチェックポイントLSN=4000より前なので上書きしてよく、#ib_redo1と#ib_redo2はリカバリに必要なので残します。

チェックポイントLSNを進めるほど、再利用できる区間が広がります。進めるには、そのLSN以前の変更を持つダーティページを先にフラッシュしておく必要があります。

ログバッファ

ログバッファは、redoログファイルへ書き出す前にredoログレコードを一時的に置くメモリ領域です。コミットやページ更新で生成されるredoログは、まずここに書かれ、その後バックグラウンドのログライタースレッドがディスクへフラッシュします。多くの行を更新・挿入・削除するトランザクションほどredoログも増えますが、ログバッファを大きくしておくと、コミットまでディスクへの書き込みを待たずにバッファへ溜められ、ディスクI/Oの回数を減らせます。

サイズと配置

ログバッファのサイズはinnodb_log_buffer_sizeで指定します。MySQL 8.4では最小値が1MB、既定が64MBです。既定はバージョンで異なり、8.0では16MBでした。ログバッファはバッファプールとは別に確保され、redoログ専用に使われます。中身は論理的なLSNの範囲に対応して並び、ログライタースレッドはバッファ内のデータを順にディスクへ書き出します。書き出し済みの範囲を超えてログライターが先へ進むことはありません。

並行書き込みと順序保証

トランザクションの変更がコミットされると、その変更を記述したredoログが生成されます。書き込みは大まかに次の手順です。

1. ログバッファ内に書き込む領域（バイト数）を予約する。予約によりstart_lsnからend_lsnの範囲が割り当てられる。
2. 予約した範囲へredoログデータを書き込む。
3. 書き込み後、「start_lsnからend_lsnまで書き込み済み」という情報をrecent writtenバッファに登録する。

複数スレッドが同時にログバッファへ書くと、書き終わる順序がLSNの並びと一致しないことがあります。たとえばスレッドAがLSN100〜150、スレッドBが150〜200を予約したとき、Bが先に書き終わってAがまだ途中、という状態が起こり得ます。ところがログライターは、リカバリで先頭から順に適用できるように、ディスクへLSNの若い順に書かなければなりません。100〜150がまだ埋まっていないのに150〜200だけをディスクへ書くことはできず、Aの完了を待つ必要があります。

recent writtenバッファは、各スレッドが「自分の範囲を書き終えた」ことを登録する補助構造です。ログライターは、登録されたリンク（start_lsn → end_lsn）の連鎖をたどることで「このLSNより前はすべてバッファに書き込み済み」と判断でき、その境界までをディスクへフラッシュします。リンクが途切れている箇所では該当スレッドの完了を待ちます。これで、複数スレッドの並行書き込みと、ログライターの順序保証が両立します。

フラッシュの制御

ログバッファをいつディスクへフラッシュするかは、innodb_flush_log_at_trx_commitで制御します。

耐久性と性能のトレードオフを、この設定で選べます。既定の1が最も安全です。

クラッシュリカバリ

クラッシュ後の再起動時、InnoDBはリカバリ処理を行います。チェックポイントLSNから、ディスク上のredoログに記録された末尾まで、LSNの順にredoログを適用します。適用とは、各ログレコードが記述する「ページのどの位置にどのバイト列を書くか」に従い、該当ページを読み込んでバッファプール上で変更を反映することです。反映されたページはダーティになり、その後のフラッシュでディスクへ書き出されます。こうして、未フラッシュだったダーティページの内容がredoログを通じて復元されます。

リカバリでは、まずチェックポイント以降のredoログをすべて適用します。ここにはクラッシュ時点で未コミットだったトランザクションの変更も含まれます。redoの適用が終わると、MySQLサーバーはアプリケーションなどからのクライアント接続をできるだけ早く受け付け始めます。未コミットだったトランザクションのロールバックは、undoログを使ってバックグラウンドスレッドが行い、新しいクライアントからのクエリ処理と並行して進むことがあります。redoは物理的な変更の再現、undoは論理的な取り消しという、役割の異なる2つを組み合わせて、クラッシュ直前の一貫した状態に戻します。

変更を元に戻すための記録

undoログは、トランザクションの変更を「元に戻すための情報」を記録する仕組みです。InnoDBでは主に2つの用途があります。

1つはROLLBACK時の取り消しです。トランザクションがコミットされずに終わった場合、そのトランザクションが行った変更をundoログに基づいて打ち消し、データを変更前の状態へ戻します。

もう1つはMVCC（Multi-Version Concurrency Control）です。ある時点のスナップショットを見ている読み取りからは、他のトランザクションがすでにコミットした最新の行が「まだ見えてはいけない」ことがあります。そのとき、undoログに残された古いバージョンをたどって、その読み取りから見えるべきバージョンを復元します。

redoログとの役割の違い

undoログとredoログは名前が似ていますが、記録するものが正反対です。redoログは「何を変更したか」を物理的に記録し、クラッシュ後に変更を再現するために使います。undoログは「変更をどう取り消すか」を論理的に記録し、ROLLBACKや古いバージョンの復元に使います。

両者は補い合う関係でもあります。通常の（永続テーブル向けの）undoログへの書き込み自体もredoログに記録されるため、undoの永続性はredoによって保証されます。クラッシュ後のリカバリでredoを適用してundoログを復元し、それから未コミットのトランザクションをundoで巻き戻す、という流れになります。なお、ユーザー一時テーブル向けのundoはクラッシュリカバリに不要なため、redoには記録されません。

どこに保存されるか

undoログは、rollback segmentが保持します。MySQL 8.0では専用のundoテーブルスペース（初期化時に既定で2つ作られる）に置かれ、システムテーブルスペース（ibdata1）には格納されません。undoログがibdata1に置かれていたのは主にMySQL 5.7以前です。rollback segmentはINSERT用とUPDATE用のundoログを持ち、各undoログのレコードは、通常のインデックスページと同じ16KB単位のundoページに記録されます。

1つのトランザクションが複数の変更を行うと、そのトランザクションに属するundoログは連鎖状につながります。ROLLBACK時には、この連鎖を逆にたどることで、変更を順に取り消していけます。

2種類のundoログ

undoログは、操作の種類に応じて2つに大別されます。

この2つは、寿命の扱いも違います。INSERTのundoはROLLBACK専用なので、トランザクションがコミットされれば破棄されるか、再利用のためにキャッシュされます。挿入した行は、コミットしてしまえば「元に戻す」必要も「古いバージョンとして見せる」必要もないからです。

一方、UPDATEのundoはhistory listに入り、まだ古いバージョンを参照しているRead Viewがある間は保持されます。不要になったあと、purgeによって回収されます。更新前の値は、まだ古いスナップショットを見ている読み取りにとって必要になり得るため、コミット後すぐには捨てられないわけです。

読み取りと書き込みを待たせ合わない

MVCC（Multi-Version Concurrency Control、マルチバージョン並行制御）は、読み取りと書き込みを同時に走らせながら、読み取りには一貫したスナップショットを見せる仕組みです。InnoDBでは、行を更新・削除しても古いバージョンをすぐには物理削除せず、undoログに残します。読み取り側はRead View（読み取りビュー）というスナップショットを持ち、各レコードに付いたトランザクションIDを手がかりに、自分が見るべきバージョンを選びます。おかげで、読み取りは書き込みを待たず、書き込みも読み取りを待たずに進めます。

なぜ古いバージョンをすぐ消さないのか、具体例で考えます。トランザクションAがSELECTを実行している最中に、トランザクションBが同じ行をUPDATEしてコミットしたとします。Aは、Bのコミット前のデータを同じスナップショットとして見続ける必要があります。そこでBが書き込んだ最新レコードはAには見せず、Bの更新前のバージョンをundoログから復元して返します。つまり、Bがコミットしたあとでも、Aが参照を続けている間は古いバージョンを保持しておかなければなりません。この保持と、不要になったあとの回収を担うのがpurgeです。

Read Viewが持つ情報

Read Viewは、ある時点で「どのトランザクションの変更を見るか、見ないか」を決めるための情報です。SELECTを実行するとき、あるいはカーソル（クエリ結果を1行ずつ取り出す仕組み）を開くときに、そのトランザクション用のRead Viewが作られます。保持する情報は次のとおりです。

m_up_limit_idは、アクティブなトランザクションがあればm_idsの最小値、なければm_low_limit_idになります。m_low_limit_idは、Read Viewを作った時点で「次に割り当てられる」トランザクションIDです。

可視性の判定

レコードに格納されたトランザクションID（DB_TRX_ID）を、Read Viewの情報と照らして、そのバージョンが見えるかどうかを判定します。ロジックは次のとおりです。

1. id < m_up_limit_idまたはid == m_creator_trx_idなら、その変更は見る。
2. id >= m_low_limit_idなら、その変更は見ない（ビュー作成後に開始したトランザクションの変更）。
3. 上記以外で、m_idsが空なら、その変更は見る。
4. m_idsにidが含まれるなら見ない。含まれないなら見る。

考え方としては、m_idsに含まれるということは、そのトランザクションがビュー作成時点でまだアクティブ（未コミット）だったということです。アクティブなトランザクションの未コミット変更は、読み取り側には見せません。逆に、m_idsに含まれず、かつm_up_limit_id以上m_low_limit_id未満のトランザクションは、ビュー作成前にコミット済みなので、その変更は見ます。

クラスタ化インデックスに付くシステムカラム

undoチェーンをたどるための情報は、クラスタ化インデックス（主キー）のリーフレコードに付くシステムカラムが持っています。システムカラムとは、CREATE TABLEで定義した列とは別に、InnoDBが内部管理のために持たせる列のことです。公式マニュアルが挙げるシステムカラムは次の3つです。

可視性の判定とundoチェーンのたどりに使うのはDB_TRX_IDとDB_ROLL_PTRです。クラスタキーとは、クラスタ化インデックス（行本体を載せるB-tree）を並べる基準のキーのことで、通常は主キーがそれにあたります。DB_ROW_IDはその代替で、主キー（またはNOT NULLのUNIQUEインデックス）があるテーブルではどのインデックスにも現れません。

DB_TRX_IDに入るトランザクションIDは、InnoDBが内部で管理するmax_trx_idという1つのグローバルなカウンタから発行されます。新しい読み書きトランザクションが始まるたびにこのカウンタが増えていくので、DB_TRX_IDは常に昇順です。6バイトで表現できる範囲は0から2^48-1（約281兆）まであり、1秒間に数万件のトランザクションをさばき続けても使い切るまでに数百年かかる大きさです。上限に達すると0へ戻ってしまい、古いトランザクションIDと新しいトランザクションIDを区別できなくなるおそれがありますが、通常運用の時間スケールでは実質的に心配しなくて構いません。

各操作での動き

INSERTでは、その時点のトランザクションIDがDB_TRX_IDに入ります。DB_ROLL_PTRは、この挿入を取り消すためのundoレコードを指し、将来ROLLBACKするときに使います。

UPDATEは、クラスタ化インデックスでは通常in-place（同じ位置での書き換え）です。更新前の値をundoログへ書き出したうえで、同じレコード位置のデータを書き換え、DB_TRX_IDを更新トランザクションのIDに、DB_ROLL_PTRをそのundoレコードへ付け替えます。読み取り側は、必要ならDB_ROLL_PTRからundoをたどって更新前のバージョンを復元します。ただし、主キー（クラスタキーの順序を決めるフィールド）が変わる場合は、旧レコードに削除マークを付けて新レコードを挿入する形になります。一方、更新後のサイズが増えて同じページに収まらない場合は、削除マーク＋挿入ではなく、ページの再編成や分割を伴う更新として、同じレコードを別の位置へ移しつつ書き換えます。

DELETEでは物理削除ではなく削除マークが付きます。削除マーク付きレコードのDB_TRX_IDには削除したトランザクションのIDが入り、DB_ROLL_PTRは削除前の内容を保持するundoレコードを指します。

セカンダリインデックスからの遡及

セカンダリインデックスのレコードには、DB_TRX_IDもDB_ROLL_PTRもありません。undoチェーンはクラスタ化インデックスにしか存在しないのです。代わりに、セカンダリの各ページには、そのページを最後に更新したトランザクションIDとしてPAGE_MAX_TRX_IDがページヘッダに保持されます。

セカンダリインデックス経由で検索したときの可視性判定は、おおむね次の流れです。

1. セカンダリのレコードに削除マークが付いている場合は、セカンダリだけでは可視バージョンを決められないため、対応するクラスタ化インデックスのレコードをlookupする。
2. 削除マークがなく、PAGE_MAX_TRX_IDがRead Viewのm_up_limit_id未満なら、そのページへの最後の変更はビュー作成より前に確定でコミット済みなので、ページ上のレコードをそのまま使える。
3. PAGE_MAX_TRX_IDがm_up_limit_id以上なら、そのページにはビュー作成時点でまだ見えないはずの変更が含まれている可能性があるため、レコードごとに対応するクラスタ化インデックスのレコードをlookupする。
4. クラスタ側へ行った場合は、クラスタ側のDB_TRX_IDとDB_ROLL_PTRを使い、Read Viewから見えるバージョンをundoチェーンから構築する。

UPDATEでセカンダリインデックスのキーが変わった場合、InnoDBは「旧キーの削除マーク」と「新キーの挿入」で表現し、旧キーのレコードは削除マークが付いたまま残ります。セカンダリにはundoチェーンがないため、削除マーク付きのレコードを読むときは対応するクラスタ化インデックスをlookupし、クラスタ側のundoをたどって可視バージョンを取得します。

削除マークとpurge

DELETEやUPDATE（旧キーの削除）を実行しても、InnoDBはレコードをすぐには物理削除しません。まず削除マークを付ける論理削除を行います。まだ古いバージョンを見ているRead Viewが存在するかもしれないからです。purgeはバックグラウンドで動き、どのRead Viewからも参照されなくなった削除マーク付きレコードを物理削除します。同時に、そのレコードの古いバージョンを保持していたundoログも不要になるので、その領域を解放して他のundoに再利用できるようにします。

purgeが参照するのは、システム内で最も古いアクティブなRead Viewをクローンしたpurge viewです。なぜ最古の1つだけで足りるのでしょうか。最古のRead Viewは、最も古いスナップショットを持つ、つまりどのRead Viewよりも多くの変更を「見えない」と判定する、最も保守的な視点だからです。purge viewで「このトランザクションの削除は見える（古いバージョンはもう不要）」と判断できるなら、それより新しいRead Viewはすべて同じかそれ以降のスナップショットを持つので、やはり古いバージョンを必要としません。逆に、purge viewで「まだ見えない」と判断されるなら、少なくとも最古のRead Viewが古いバージョンを必要とする可能性があるため、purgeしてはいけません。こうして、最古のRead View1つの判定だけで、purgeは「どのアクティブなRead Viewからも参照されない」と安全に言えるレコードだけを削除できます。

Read Viewをいつ作り、いつ解放するか

InnoDBがサポートする分離レベルは、READ UNCOMMITTED、READ COMMITTED、REPEATABLE READ、SERIALIZABLEの4つです（既定はREPEATABLE READ）。ここでいうSELECTは、FOR UPDATEやFOR SHAREを付けない通常のSELECTです（対して、これらを付けたものはロックを取って待つ読み取りになります）。この通常のSELECTがロックを取らずRead Viewに基づいて読まれるのは主にREAD COMMITTEDとREPEATABLE READです。この2つでは、可視性の判定ロジック自体は共通で、Read Viewをいつ作るか（いつ作り直すか）が違います。作り直すタイミングが変わればm_idsやm_low_limit_idの内容も変わるため、見える範囲が変わります。一方、READ UNCOMMITTEDとSERIALIZABLEは、Read Viewの使い方そのものが異なります。

REPEATABLE READ

BEGINで始めた明示的なトランザクションでは、最初に通常のSELECTを行ったときにRead Viewが作られ、COMMITまたはROLLBACKまで同じスナップショットを使い続けます。同じトランザクション内で何度SELECTしても、Read Viewを作り直しません。START TRANSACTION WITH CONSISTENT SNAPSHOTを使った場合は、最初のSELECTを待たずにトランザクション開始時点でRead Viewが作られます。INSERTやUPDATEを行う読み書きトランザクションでも、最初の読み取りでRead Viewを作り、コミットまたはロールバックまで保持します。自分の変更はm_creator_trx_idにより常に見えます。

一方、BEGINを書かずautocommit=1（既定）のままSELECTだけを実行する場合、そのSELECT1文が1つのトランザクションです。文の実行中にRead Viewが作られ、文の終了とともにトランザクションが自動コミットされてRead Viewも解放されます。次のSELECTは別トランザクションなので、原則としてまた新しいRead Viewが作られます（後述のAC-NL-RO最適化で再利用される場合を除く）。

READ COMMITTED

通常のSELECTのたびに新しいRead Viewが作られます。同じトランザクション内でも、文ごとにスナップショットが更新されます。たとえば、あるトランザクションの中でSELECTを2回実行する間に、別のトランザクションが対象の行をUPDATEしてコミットしたとします。REPEATABLE READなら1回目のRead Viewを2回目でも使い続けるため、2回のSELECTは同じ値を返します。一方READ COMMITTEDでは2回目のSELECTのときに新しいRead Viewが作られるため、コミット済みの新しい値が見えるようになり、同じトランザクション内でも1回目と2回目でSELECTの結果が変わり得ます。

READ UNCOMMITTED

FOR UPDATEなどを付けないSELECTでもRead Viewによる可視性判定を行いません。ページ上にある最新版のレコードをそのまま読むため、まだコミットされていない他トランザクションの変更が見えてしまうことがあります（ダーティリード）。ある時点の見え方に固定して読むわけではない、という点がREAD COMMITTEDとの違いです。それ以外（ロック読みやUPDATE、DELETEなどのロックの扱い）は、READ COMMITTEDと同じです。

SERIALIZABLE

基本はREPEATABLE READに近いですが、autocommitが無効なとき（明示的なトランザクション中）は、通常のSELECTをSELECT ... FOR SHARE相当に置き換え、読んだ行に共有ロックを掛けます。対象行をまだコミットしていない他トランザクションが変更中なら、その終了を待ってから最新のコミット済み値を見ます。共有ロック中、他セッションは同じ行を読めます（別セッションのFOR SHAREも共存できます）が、その行のUPDATEやDELETEは、自トランザクションがコミットまたはロールバックするまで待たされます。一方、autocommitが有効なままの単独SELECTはそれ自体が読み取り専用の1トランザクションになるので、ロックを取らずRead Viewで読め、他トランザクションを待たせずに済みます。

これらとは別に、AC-NL-RO（Auto-Commit Non-Locking Read-Only、autocommitで動く非ロックの読み取り専用SELECT）向けの最適化があります。autocommit=1のままSELECTだけを実行する場合、MySQLは1文ごとに新しいトランザクションを開始・終了するため、本来は文ごとに新しいRead Viewを用意する必要があります。しかしRead Viewを新しく作るには、その時点でアクティブな読み書きトランザクションのID一覧（m_ids）をコピーする必要があり、そのためにInnoDB全体で共有するmutex（複数のスレッドが同時に同じデータへアクセスして壊さないよう、一時的に排他ロックをかける仕組み）を取得します。読み取り専用の負荷でこの処理を毎回行うと、mutexの競合がボトルネックになりかねません。そこでAC-NL-ROの場合は、直前に使ったRead Viewが「アクティブな読み書きトランザクションを1つも見ていなかった（m_idsが空）」状態で、かつそのRead Viewを作った時点のmax_trx_id（次に割り当てられるトランザクションID）から今までのあいだに新しいmax_trx_idが発行されていなければ、新しいRead Viewを作らずそのまま使い続けます。max_trx_idが変わっていないということは、その間に新しい読み書きトランザクションが1つも始まっていないということなので、作り直しても結果は同じになるはずだからです。これはREPEATABLE READの「同じトランザクション内で同じスナップショットを保つ」という一貫性のための仕組みとは目的が異なり、あくまでmutex取得やID一覧コピーの手間を省くための実装上の最適化です。

Read Viewは、トランザクション終了時やカーソルクローズ時に解放され、再利用可能なプールへ戻されます。InnoDBは、Read View用のメモリ領域をあらかじめいくつか確保しておき、このプールから使い回すことで、Read Viewを作るたびにメモリの確保・解放が発生するコストを避けています。先に説明したAC-NL-ROの再利用は「同じ内容のRead Viewをそのまま使い続ける」最適化ですが、このプールはそれとは別の話で、「Read View用の入れ物（メモリ領域）」そのものを使い終わったら回収し、次の別のトランザクションに割り当て直すための仕組みです。