btree index (5)

PostgreSQL

_bt_moveright

例えば，更新トランザクション(UPD-Tr)と検索トランザクション(SEL-Tr)が，以下のように並行動作した場合，

 UPD-Tr: 親ノードP0を検索し，リーフページP1のポインタを取得
 SEL-Tr: 親ノードP0を検索し，リーフページP1のポインタを取得
 UPD-Tr: ページP1のWrite lockを取得
 UPD-Tr: ページP1の空き容量が足りない場合、P1を分割して更新
 UPD-Tr: ページP1のWrite lockを開放
 SEL-Tr: ページP1のRead lockを取得

SEL-TrがページP1のRead lockを取得する前にページが分割されたので，ページP1に検索すべきデータが存在しないかもしれない。そのため，Read lockを取得したあと正しい位置まで右に移動する必要がある。

現在のページに目的のデータが存在するかどうかは，検索キーとページのhigh keyを比較してチェックする。もし検索キーのほうが大きい場合，ページが分割されたので右に移動する。

    while (!P_RIGHTMOST(opaque) &&
           (P_IGNORE(opaque) ||
            _bt_compare(rel, keysz, scankey, page, P_HIKEY) >= cmpval))
    {
        /* step right one page */
        BlockNumber rblkno = opaque->btpo_next;

IndexTupleの構造

IndexTupleの構造はitup.hで定義されている。

typedef struct IndexTupleData
{
    ItemPointerData t_tid;      /* reference TID to heap tuple */

    /* ---------------
     * t_info is layed out in the following fashion:
     *
     * 15th (high) bit: has nulls (NULLデータがある)
     * 14th bit: has var-width attributes (可変長データがある)
     * 13th bit: unused (未使用)
     * 12-0 bit: size of tuple (IndexTupleのサイズ)
     * ---------------
     */
    unsigned short t_info;      /* various info about tuple */

} IndexTupleData;               /* MORE DATA FOLLOWS AT END OF STRUCT */
typedef IndexTupleData *IndexTuple;

t_tidにテーブルのタプルへのリファレンス情報が設定される。t_infoにはIndexTupleのサイズなどの情報が設定される。
t_infoの後にデータが続く。IndexTupleのデータにNULLがある場合，まずNULLビットマップ(IndexAttributeBitMapData)が続き，その後にTupleのデータが続く。IndexTupeにNULLが無い場合はNULLビットマップはない。

NULLビットマップは，Heap Tuple(テーブルのタプル)のNULLビットマップと異なり，固定長になっている。

typedef struct IndexAttributeBitMapData
{
    bits8       bits[(INDEX_MAX_KEYS + 8 - 1) / 8];
} IndexAttributeBitMapData;
typedef IndexAttributeBitMapData *IndexAttributeBitMap;

デフォルトではINDEX_MAX_KEYS = 32なので，IndexAttributeBitMapDataは4byteになる。
Tupleのデータ構造は，HeapTupleと同じ。データを作成する処理も同じ内部APIを使用している。

BTPageOpaque

btree indexの各ページが保持するデータ。

typedef struct BTPageOpaqueData
{
    BlockNumber btpo_prev;      /* left sibling, or P_NONE if leftmost */
    BlockNumber btpo_next;      /* right sibling, or P_NONE if rightmost */
    union
    {
        uint32      level;      /* tree level --- zero for leaf pages */
        TransactionId xact;     /* next transaction ID, if deleted */
    }           btpo;
    uint16      btpo_flags;     /* flag bits, see below */
} BTPageOpaqueData;

typedef BTPageOpaqueData *BTPageOpaque;

btpo_prev/btpo_nextで左右のページへのリンクを持つ。これらはindex scanで左右に移動するときに使われる。また，右のページへのリンクは，別のトランザクションがページを分割したときに，正しいページを探すときにも使われる。(この処理は_bt_moverightで実行される)

levelにはツリーの高さの位置が設定される。リーフページは0でrootに向かって増えていく。xaxtはページが削除されたときのnext transaction IDが設定される。btpo_flagsにはページの状態を表すフラグが設定される。以下のフラグがある。

 BTP_LEAF: リーフページ
 BTP_ROOT: ルートページ
 BTP_DELETED: ツリーから削除されたページ
 BTP_META: metaページ
 BTP_HALF_DEAD: 空ページだがツリーには存在する

BTPageOpaqueデータはページの末尾に存在し，そのポインタを取得するには，PageGetSpecialPointerを使う。

    BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);

メモ：もしlevelがリーフページまでの距離を正確に表しているなら、_bt_searchでstackのメモリ割り当てをまとめて実行でき、palloc/pfreeの実行回数を減らせる。

PageInit

ページを初期化する。

(1)ページ全体を0で初期化する
(2)ページの先頭からPageHeaderの領域を確保する(pd_lowerを設定)
(3)ページの末尾からSpecialDataの領域を確保する(pd_upper, pd_specialを設定)
SpecialDataは使用するオブジェクトにより異なり，btree indexの場合はBTPageOpaqueDataになる。
(4)ページのサイズ，バージョンを設定する