btree index (6)

PostgreSQL

meta page

btree indexの先頭ページにはmeta pageというデータがおかれ，rootノードの位置などを記録する。(btreeではrootページが分割されるときrootページが移動するので，その位置をmeta pageで管理している)

typedef struct BTMetaPageData
{
    uint32      btm_magic;      /* should contain BTREE_MAGIC */
    uint32      btm_version;    /* should contain BTREE_VERSION */
    BlockNumber btm_root;       /* current root location */
    uint32      btm_level;      /* tree level of the root page */
    BlockNumber btm_fastroot;   /* current "fast" root location */
    uint32      btm_fastlevel;  /* tree level of the "fast" root page */
} BTMetaPageData;

btm_magic, btm_versionには，nbtree.hで定義されているBTREE_MAGIC, BTREE_VERSIONが設定される。
btm_root, btm_levelは，rootページの位置とページの高さ(リーフページを0として，親になるほど大きくなる)が設定される。

btm_fastroot, btm_fastlevelにはfast rootページの位置と高さが設定される。PostgreSQLのbtree indexはデータが削除されていったときに，各levelの一番右のページは削除されないため，treeの高さが低くなることがない。大きくなったindexのデータを多量に削除したとき，treeが痩せ細った状態になり，rootからあるlevelのノードまではアイテムが1つしかない状態になる可能性がある。この場合，最初に分岐が始まるノードから検索を開始すればよいので，これをfast rootとしてmeta pageに保存している。_bt_searchなどから_bt_getrootでrootページを取得するときは，このfast rootが返される。データが再度登録されていきfast rootが分割されるときには，fast rootの位置は再調整される。

btree indexの先頭ページはページの先頭にPageHeaderData(24byte)に続いて，このBTMetaPageData(24byte)があり，ページの末尾にBTPageOpaqueData(16byte)がある。これ以外は使用されない領域であり，0で埋まっている。(少しもったいないような気がする)

ページ分割の処理(概要)

_bt_insertonpgでページの空き容量が足りない場合，ページを分割する。ページの分割は以下の順序で実行される。

(1)_bt_findsplitloc/_bt_checksplitlocでページを分割する位置を決める
分割後の左右のページが大体同じになるように位置を計算している。
ただし一番右のページを分割する場合は，右側のページの空き容量が多くなるようにしている。(タイムスタンプやシーケンス番号など，増加していくデータが登録される場合，右のページばかりにデータが追加されていくため)

(2)_bt_splitで分割する
新しいページを作成し，左右のページにアイテムを振り分ける。
既存のページが左のページになり，新しいページが右のページになる。

(3)_bt_insert_parentで親ページに新しいページを登録する
rootページの分割のときは，新しいrootページを作成しそこに左右のページを登録する。meta pageも修正する。
root以外の分割のときは，親ページに対して_bt_insertonpgを再帰的に実行して新しいページのアイテムを登録する。親ページも分割が必要な場合，再帰コールにより処理が繰り返される。
(分割が必要なくなるまで，_bt_insertonpg -> _bt_insert_parent -> _bt_insertonpg...と実行される)