btree index (7)

_bt_findsplitloc

btree indexのページを分割するとき，どの位置で左右に分割するかを決める。
先頭のアイテムから順にサイズを取得し，そのアイテムを左のページに追加した場合の左右の空き領域を計算する。次に_bt_checksplitlocを実行して左右の空き領域を比較し，ベストな分割位置を計算する。計算途中の情報は，FindSplitData構造体を使って，ベストな分割位置を保存している。
また，左右の空き領域の差がpage sizeの1/16になったら，そこで十分にいい位置だと判断して，計算をやめている。(goodenough変数でチェックしている)

_bt_checksplitloc

左右の空き領域の差を比較して，ベストな分割位置を求める。
一番右のページを分割する場合は，右の空き領域が左のページの2倍になるように計算する。(シーケンスなど増えつづけるデータの場合，右のページに追加されるため) それ以外の場合，左右の空き領域が同じになるように計算する。

_bt_split

ページを分割する。
origpageからleftpage, rightpageにアイテムを振り分ける。leftpageは，最後にorigpageに書き戻すため，PageGetTempPageで一時的な領域を確保する。rightpageは_bt_getbufで新しいページを作成する。

(1)leftpage, rightpageのBTPageOpaqueデータを設定する
(2)origpageが一番右のページではないとき，右のページにorigpageのhigh keyを設定する
(3)左のページのhigh keyを設定する
左のページのhigh keyは右のページの最初のアイテムのキーを使う。
(4)origpageのアイテムを左右のページに振り分ける
(5)一番右のページではないときは，origpageの右のページ(spage)の左へのリンクがrightpageになるので，書き換える
(6)Transaction logを記録
(7)leftpageをorigpageに書き戻す