行は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. 以上すべてが失敗したら、セグメントの完全に空いたエクステント、テーブルスペースのフラグメントエクステント、テーブルスペースの完全に空いたエクステントの順にエクステントを取得し、先頭ページ（フラグメントなら最初の空きページ）を割り当てる。

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

ディスク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='user01'の注文id=102を入れるとき、そのキーが載るセカンダリリーフ（ページ42）がバッファプールになければ、ディスク上のページ42は読みません。ディスクのページ42にはすでに(user01,101)と(user01,103)があり、新しい(user01,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のすべてをバッファする）でした。設定値はいつでも変更でき、変更は新しい操作のバッファ有無にだけ効きます。すでに溜まっている分のマージには影響しません。

適応的ハッシュインデックスとは

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

user_id='user01'、name='Alice'を探すとき、ハッシュインデックスに載っていればルートと中間ノードを経ることなくリーフ上のレコードへ直接アクセスすることができます。

ハッシュインデックスの構築

ハッシュ値の生成

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

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

同じプレフィックスを持つレコードが複数あるときは、キー未満とキー以上の境界に接する1レコードだけをハッシュインデックスに登録します。

ハッシュインデックスに登録されるレコード

等価検索で一致するレコードが存在するケースを考えます。プレフィックスに対してレコードが一意に定まる場合（この例ではn_fields=2、n_bytes=0）、キー以上の最小値は探している行そのものなので、そのレコードへの参照が登録されます。

等価検索で一致するレコードが存在しないケースでは、探しているキー未満の最大値とキー以上の最小値のうち、探しているキーと同じプレフィックスを持つ方を登録します。以降の例はプレフィックスをuser_id列のみ（n_fields=1、n_bytes=0）とします。

検索しているuser01,Bobは存在しないレコードです。左のuser01,Aliceは同じuser_id、右のuser02,Bobは別のuser_idなので、プレフィックスが同じ左が登録されます。

検索しているuser02,Aliceは存在しないレコードですが、左のuser01,Aliceは別のuser_id、右のuser02,Bobは同じuser_idなので、右が登録されます。

インデックスは、今検証中のn_fieldsとn_bytesの組み合わせについて、仮にハッシュエントリがあった場合に有効だったかをメモリ上のカウンタで数えます。バッファプールの各ページも、同じ組み合わせでハッシュエントリが有効だった回数を独自に保持します。両方の数が閾値を超えると、そのページにハッシュエントリを作ります。今の組み合わせでは有効とみなせない検索になると、n_fieldsとn_bytesを選び直し、インデックス側のカウンタはリセットされます。

ハッシュエントリの削除

適応的ハッシュインデックスは肥大化し続けるわけではありません。参照先のB-treeリーフページがバッファプールから追い出されると、そのページを指すハッシュエントリは削除されます。ページ分割やページ破棄などでB-treeの構造が変わったときも、該当するエントリは削除されます。検証中のn_fieldsとn_bytesが変更され、新しい組み合わせでインデックス側とページ側の両方の数が再び閾値を超えたときも、そのとき検索していたページの古いエントリを削除してから新しいエントリを作ります。

redoログとは

redoログは、InnoDBがクラッシュリカバリを実現するための仕組みです。INSERT・UPDATE・DELETEでバッファプール内のページを更新すると、そのページをフラッシュする前に、どのページのどの位置に何を書いたかという変更履歴をredoログに記録します。もしサーバーがクラッシュしても、再起動時にチェックポイント以降のredoログを古い順に適用すれば、ディスクへ反映しきれていなかった変更を復元できます。

B-tree上のページ10のuser_id='user01'のnameをAliceからBobへ更新すると、コミットした直後は次のようになります。バッファプール上のページ10はすでにuser01,Bobですが、データファイル上の同じページはまだuser01,Aliceです。ディスクへ永続化されているのは、ページ10のnameをBobにしたという変更履歴だけです。

LSNとチェックポイント

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

チェックポイントLSNは、このLSN以前の変更はすでにディスク上のデータページへ反映されているという境界を表します。チェックポイントより前のログ領域は上書きして再利用することができます。チェックポイントを進めるには、そのLSNまでの変更をすべてデータページへフラッシュしておく必要があります。

ログバッファ

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

トランザクションの変更がコミットされると、その変更を記述した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で設定できます。

クラッシュリカバリ

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

undoログとは

undoログは、1つの読み書きトランザクションに紐づくundoレコードの集まりです。undoレコードは、クラスタ化インデックスの行に対する最新の変更を打ち消す情報が1件分入ったものです。行を1回変更するたびにundoレコードが1件増え、それらはundoログにまとめて置かれます。

InnoDBでは主に2つの用途があります。

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

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

undoログの場所

通常テーブル向けのundoログはundoテーブルスペースのrollback segmentに、一時テーブル向けはグローバル一時テーブルスペースのrollback segmentに割り当てられます。

rollback segmentはundoスロットの配列を持ち、スロットには先頭undoページの番号が入ります。undoページとundoレコードは同じテーブルスペース上の別領域にあります。undoレコードはundoページに複数件載ります。1ページに収まらなくなると、同じundoログに次のページをつなぎます。

undoログの種類と寿命

1つのトランザクションには、必要になった種類だけundoログが割り当てられます。通常テーブルのINSERTだけなら1本です。通常テーブルと一時テーブルの両方で、INSERTとUPDATE（またはDELETE）を行うと4本になります。

通常テーブル向けのundoログはundoテーブルスペースに置かれ、ROLLBACKとMVCCの両方に使われます。一時テーブル向けのundoログはグローバル一時テーブルスペースに置かれます。一時テーブルは作ったセッションからしか見えないので、他のトランザクションが古い値を読む必要はなく、ROLLBACKにだけ使われます。

通常テーブルでは、INSERTとUPDATEでコミット後にundoログを残すかが異なります。

INSERT用のundoログは、コミット完了時に破棄または再利用されます。コミット後に他のトランザクションが読む可能性がある古い値が存在しないからです。UPDATE用（DELETEを含む）のundoログは、コミット後も残します。他のトランザクションがまだ更新前の値を読んでいることがあるからです。他のトランザクションから読まれなくなったら回収されます。

MVCCとは

MVCC（Multi-Version Concurrency Control）は、読み取りと書き込みが互いを待たせることなく並行して処理を行えるように、トランザクションごとに一貫したスナップショットを提供する仕組みです。

InnoDBでは、行の更新時にレコードをその場で書き換える一方、更新前の状態を再構築するための情報をundoログに記録します。削除時も直ちには物理削除せず、レコードに削除マークを付与してundoログに変更前の状態を残します。

読み取り処理は、トランザクション開始時などに作成したRead Viewを手がかりに、各レコードのトランザクションIDと照合して参照すべきバージョンを選択します。最新レコードが参照すべき時点より新しい、または未コミットである場合は、undoログの情報を適用して過去のバージョンを復元して読み取ります。

Read Viewの構造

Read Viewは、読み取り処理で各レコードの可視性を判定するためにメモリ上に構築される内部データ構造です。トランザクションを管理するメモリ上のオブジェクトに紐づけて保持されます。作成時点でアクティブだったトランザクションIDや境界値を記録し、どの変更まで参照できるかを判定します。主要なフィールドは次のとおりです。

可視性の判定

対象レコードのトランザクションID（DB_TRX_ID）をidとし、Read Viewの情報と照合して次の順序で可視性を判定します。

1. id < m_up_limit_idまたはid == m_creator_trx_idであれば可視。Read View作成前にコミット済み、または自トランザクションによる変更であるため。
2. id >= m_low_limit_idであれば不可視。Read View作成後に開始されたトランザクションによる変更であるため。
3. m_idsにidが含まれていれば不可視。Read View作成時点で未コミットだったため。
4. 上記のいずれにも該当しなければ可視。Read View作成前にコミット済みの変更であるため。

レコードが不可視と判定された場合、DB_ROLL_PTRを使ってundoログを過去へたどり、上記の条件を満たす可視なバージョンを復元します。

システムカラムとundoレコード

クラスタ化インデックスのリーフレコードには、MVCCを制御するためのシステムカラムが付与されています。

DB_TRX_IDは、読み書きトランザクションの開始時にグローバルカウンタから昇順で発行されます。DB_ROLL_PTRはundoログ内のアドレスを指しており、レコードが更新されるたびに過去のバージョンへ連鎖するundoチェーンが形成されます。

レコードの操作種別ごとのシステムカラムとundoレコードの紐づきは次のとおりです。

セカンダリインデックスの可視性判定

セカンダリインデックスのレコードにはDB_TRX_IDやDB_ROLL_PTRが存在せず、undoチェーンもありません。そのため、ページヘッダに記録された最新の変更トランザクションIDであるPAGE_MAX_TRX_IDを利用して可視性を判定します。

判定手順は次のとおりです。

1. レコードに削除マークが付いている場合は、セカンダリインデックスのみでは可視バージョンを判断できないため、クラスタ化インデックスを参照します。
2. 削除マークがなく、PAGE_MAX_TRX_ID < m_up_limit_idであれば、ページ内の全レコードがRead View作成前にコミット済みとみなせるため、クラスタ化インデックスを参照せずにレコードをそのまま返します。
3. PAGE_MAX_TRX_ID >= m_up_limit_idの場合は、未確定の変更が含まれている可能性があるため、クラスタ化インデックスを参照し、DB_TRX_IDとDB_ROLL_PTRを用いて可視バージョンを復元します。

不要バージョンのpurge

削除マークが付いたレコードや更新前の古いバージョンは、過去のスナップショットを参照しているRead Viewが存在する間は保持し続ける必要があります。

参照するRead Viewがすべて終了して不要になったレコードやundoログは、バックグラウンドで動作するpurgeスレッドによって回収されます。削除マーク付きレコードは物理削除され、対応するundoログ領域は再利用のために解放されます。

purgeスレッドは、自分用のRead Viewであるpurge viewを持ちます。開いているRead Viewのうち最も古いものをコピーして更新し、そのm_low_limit_noより小さいトランザクション番号のundoログや削除マーク付きレコードを回収します。

分離レベルとRead Viewのライフサイクル

Read Viewをいつ作り、いつまで使うかは、トランザクション分離レベルによって異なります。

READ UNCOMMITTED

Read Viewによる可視性判定を行いません。ページ上の最新レコードをそのまま読み取るため、コミット前の変更が見えてしまうダーティリードが発生します。

READ COMMITTED

SELECTを実行するたびに新しいRead Viewを作成します。クエリごとにスナップショットが更新されるため、同一トランザクション内であっても、他トランザクションがコミットした最新の値が次回のSELECTで反映されます。

REPEATABLE READ

トランザクション内で最初にSELECTを実行した時点、またはSTART TRANSACTION WITH CONSISTENT SNAPSHOTを実行した時点でRead Viewを作成します。

このRead Viewはトランザクションがコミットまたはロールバックされるまで保持され、後続のクエリでも同じスナップショットを使い続けます。そのため、他トランザクションが更新をコミットしても結果は変わりません。自トランザクションによる変更はm_creator_trx_idによって常に見えます。

SERIALIZABLE

autocommitが無効な明示的トランザクションでは、通常のSELECTが共有ロック付きの読み取りに置き換わり、Read Viewによる読み取りは行いません。対象行が他トランザクションによって更新中の場合は待機が発生します。一方、autocommit=1の単独SELECTに限り、ロックを取得せずRead Viewで読み取ります。