btree index (10)

PostgreSQL

_bt_buildadd

sortしてからbtree indexを作成するとき、pageにアイテムを登録する関数。
pageを作成中のleaf pageの構造は以下のようになる。テーブルのpage構造とほとんど同じだが、linp0とかlastの所に細工がしてある。

(nbtsort.cより)
 * A leaf page being built looks like:
 *
 * +----------------+---------------------------------+
 * | PageHeaderData | linp0 linp1 linp2 ...           |
 * +-----------+----+---------------------------------+
 * | ... linpN |                                      |
 * +-----------+--------------------------------------+
 * |     ^ last                                       |
 * |                                                  |
 * +-------------+------------------------------------+
 * |             | itemN ...                          |
 * +-------------+------------------+-----------------+
 * |          ... item3 item2 item1 | "special space" |
 * +--------------------------------+-----------------+

linp0はhigh keyを登録するために空けておき、linp1から順にItemIdを登録していき、item1から対応するBTItemを登録していく。pageの使用量がしきい値を超え、新しいアイテムが登録できなくなったら、次の処理を行う。

(1)_bt_blnewpageで新しいページ(npage)を割り当てる
(2)それまで使っていたページ(opage)の一番最後のアイテム(itemN)を、npageの先頭のアイテムとして登録する。(npageのlinp1, item1へ登録される)

        ii = PageGetItemId(opage, last_off);
        obti = (BTItem) PageGetItem(opage, ii);
        _bt_sortaddtup(npage, ItemIdGetLength(ii), obti, P_FIRSTKEY);

(3)linp0にlinpNの情報をコピーする。これでopageのhigh keyはitemNになる。

        hii = PageGetItemId(opage, P_HIKEY);
        *hii = *ii;

(4)linpNを未使用にする。linpNのLP_USEDフラグを外して、pageのpd_lowerをlinpNの前(図のlastの位置)へ戻すことにより実現している。

        ii->lp_flags &= ~LP_USED;
        ((PageHeader) opage)->pd_lower -= sizeof(ItemIdData);

(5)opage,npageの左右のリンクを設定する。
(6)_bt_blwritepageでopageをディスクに出力する。opageはこれ以降変更されない
(7)新しいBTItemを追加する

(2)-(4)の処理によって、opageのItemNはデータではなくhigh keyとして使われる。Index ItemとしてのItemNはnpageの先頭に登録されている。また、leaf pageが一番右のpageだった場合は、linp0はhigh keyではなく先頭のItemを指す必要がある。このため、index作成の最後のほうで、_bt_slideleftを実行し、linp1〜linpNを一つずつ前へずらしている。

_bt_pagestate

BTPageStateを作成する。BTPageStateはbtree indexの作成中の各レベルの情報を管理する。(各レベルにつき1つ作成される)

BTPageStateのbtps_fullで各pageが使用できる量を設定する。leaf pageは90%まで、non-leaf pageは70%まで利用できるように設定している。

    /* set "full" threshold based on level.  See notes at head of file. */
    if (level > 0)
        state->btps_full = (PageGetPageSize(state->btps_page) * 3) / 10;
    else
        state->btps_full = PageGetPageSize(state->btps_page) / 10;