btree index (3)

PostgreSQL

_bt_insertonpg

指定したページにBTItemを登録する。
non-unique indexで重複したキーを登録する場合，以下のルールで登録する場所を決めている。

(1)指定したページに登録できる場合：同じキーの先頭に挿入する。(新しく登録するアイテムが先頭になる)

(2)指定したページの空き容量が足りず，ページのhigh keyとアイテムのキーが違う場合：ページを分割して登録する。

(3)指定したページの空き容量が足りず，ページのhigh keyとアイテムのキーが同じ場合：空き容量があるページが見つかるまで，右のページを探していく。
ただし空き容量が見つかる前に，high keyとアイテムのキーが違ったら，そこに登録しなければならないので，ページを分割する。また，high keyとアイテムのキーが一致していても，乱数で100分の1の確率で右のページに進むのをやめて，そこでページを分割する。重複するキーが非常に多い場合は一番右のページまで進むのに時間がかかるため，乱数で適当に止めている。

    while (PageGetFreeSpace(page) < itemsz &&
           !P_RIGHTMOST(lpageop) &&
           _bt_compare(rel, keysz, scankey, page, P_HIKEY) == 0 &&
           random() > (MAX_RANDOM_VALUE / 100))

リーフページのhigh keyについて

リーフページには，そのページで管理する最大のキーが登録されている(high keyと呼ばれる)。high keyはページ内のアイテムの最大の値または，それよりも大きい値が登録されている。
OffsetにP_HIKEYを指定すると，high keyにアクセスできる。

    itemid = PageGetItemId(origpage, P_HIKEY);
    itemsz = ItemIdGetLength(itemid);
    item = (BTItem) PageGetItem(origpage, itemid);