btree index (2)

_bt_doinsert

btreeへBTItemを登録する。public interfaceのbtbuildやbtinsertから実行される。

(1)_bt_mkscankeyでインデックスのデータを比較するためのScanKeyを生成する
(2)_bt_searchでBTItemを登録する，先頭のリーフページを取得する
(3)Read lockを開放して，Write lockを取得する
(4)Read lock開放後，Write lockを取得する前にページが分割されたかもしれないので，_bt_moverightで正しいページに移動する
(5)unique indexの場合，_bt_check_uniqueでチェック
(6)_bt_insertonpgで登録する。

_bt_search

ScanKeyで指定したキーが登録されているべきリーフページを検索する。
_bt_searchではキーがあるとしたらこのページというところまで調べるが，ページ内にキーが存在するかどうかまでは調べない。

rootページから検索を開始し，_bt_binsrchで次の階層のページを探しながら，リーフページまで進んでいく。次の階層へ進むたびに現在のページの情報をstack_inへ登録していく。
stackはリンクリストで表現されており，リーフページにたどりついたときに，リーフページからrootまでのページの情報(ブロックIDなど)が登録されている。
_bt_searchはこのstackを戻り値として返す。また，bufPにはリーフページが設定されている。

Indexのデータ登録でページが満杯だったときはページを分割し，親ページに新しいページを登録する必要があり，さらにこの親のページが満杯だったら親の親のページを更新する必要があるため，rootまでたぐっていけるようになっている。

Indexの検索(_bt_first)ではstackの情報は不要で，_bt_search実行直後にstackを開放している。

    /*
     * Use the manufactured scan key to descend the tree and position
     * ourselves on the target leaf page.
     */
    stack = _bt_search(rel, keysCount, scankeys, nextkey, &buf, BT_READ);

    /* don't need to keep the stack around... */
    _bt_freestack(stack);

_bt_searchをコピーして、stackを作成しないバージョンを作ったほうがいいのかもしれない。