B-Treeインデックス。btinsert()。ページの分割が必要な場合

DB PostgreSQL

前回の続き。_bt_insertonpg() から呼び出される次の3つの関数を中心にインデックス追加時のページ分割の処理を見てみた。

  • _bt_findsplitloc() : どのタプル以降を新しく作成する右側のページに移動するかを決める
    • pageがright mostのときはFILLFACTORに応じて計算（FILLFACTORのデフォルトはLEAFが90、それ以外が70）。right mostでなければ大体半分になるように計算。
  • _bt_split() : ページを分割する
    • 一時的なページ（左ページ用）と新規のページ（右ページ用）を作成する。
    • high keyを設定する。
    • _bt_findsplitloc()で求めたオフセットを元に分割前のオリジナルのページからタプルを順に振り分けていく。この分割を引き起こした新規タプルについてもこのときに追加してしまう。
    • 振り分け終わったら一時的なページをオリジナルのページに書き戻す。
    • オリジナルと新規のページをダーティにマーク。
    • WALのログを書く。
  • _bt_insert_parent() : 親からのリンクを張る
    • 分割元がルートのページだった場合
      • _bt_newroot()を呼び出す。_bt_newroot()ではルートのページを新規作成しメタページを更新、それから分割元ページと新規ページをルートに関連付ける（P_HIKEY に左のページ、 P_FIRSTKEYに右のページ）。ルートは最初の子供（分割元の左のページ）のキーはマイナスの値として関連付けてる。そして、ルートとメタのページをダーティにしWALのログを書く。
    • 分割元がルート以外のページだった場合
      • 新規に作成したページの先頭ItemIdを指し示すタプルを作成する。
      • 以前_bt_search()を呼び出して得たスタック（親から子をたどったときのスタック）を使って親のバッファを取得。
      • _bt_insertonpg()を呼び出し、親のバッファに新しいタプルを追加するように依頼。_bt_insertonpg()の実行は再帰呼び出しとなる。つまり、呼び出し先でさらにページ分割が発生することがありうる。

地道な処理だ。