btree index (8)

_bt_compare

scankeyとindex tupleを比較する。
index_getattrでindex tupleのデータを取得し,FunctionCall2で比較を実行する。

FunctionCall2には,異なるデータ型の比較をサポートするために,先頭の引数にindex tupleのデータを渡さなければいけないという制約があり,比較結果を逆にする必要がある。単純に正負を逆にしてしまうと, FunctionCall2がINT_MINの値を返したときにオーバーフローしてしまうので,以下のコードを使っている。

    result = (result < 0) ? 1 : -result;

_bt_binsrch

btree indexのページをバイナリサーチする。
リーフページかそうでないか,nextkeyがtrueかfalseかで結果が異なる。

leaf page, nextkey == false: key >= scankeyを満たす先頭の位置を返す
leaf page, nextkey == true: key > scankeyを満たす先頭の位置を返す
non-leaf page, nextkey == false: key < scankeyを満たす最後の位置を返す
non-leaf page, nextkey == true: key <= scankeyを満たす最後の位置を返す

_bt_walk_left

指定したページの左のページを取得する。
(1)_bt_relandgetbufで現在のページのロックを開放してから,左のページのRead lockを取得する。
(2)取得したページの右のページを調べて,元のページにたどり着くまで右のページにすすむ。たどり着けたら,そのページをleft pageとして返す。
右のページを4回チェックしても見つからなかったら,ページが削除されたかもしれないので,以降の処理を行う。
(3)元のページのRead lockを取得
(4)元のページが削除されていたら,削除されていないページが見つかるまで右のページに進んで,(1)からやり直す。
元のページが削除されてなければ,左のページが削除されたと判断し,無限ループにはまっていないかチェックしたあと,(1)からやり直す。

ページ分割のログレコード

ページを分割したときのログレコードは、以下の4つから構成される。

rdata[0]: xl_btree_split
rdata[1]: 左のページの情報
rdata[2]: 右のページの情報
rdata[3]: 元のページの右のページ

左右のページの情報は、データ部分(pd_upper以降)のみ出力する。分割直後の左右のページはItemIDリストの順番に並んでいるため、データ部にあるBTItemを順番に読んでいけばItemIDデータは復元できるため。
元のページの右のページは、左へのリンクを変更するため必要であればページ全体をログに出力する。