挿入順序で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未満のうちはフラグメントページから細かく取る点は、テーブルが小さいうちに領域を無駄にしない方針とつながっています。