挿入順序とページの割り当て

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

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