ページ内でも速く探したい

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ポインタをたどって順に比較し、目的のレコードを特定します。件数が少ないので、この線形探索はすぐに終わります。