B-Treeインデックス。btbuild()。インデックスのページを書き出すまで

DB PostgreSQL

インデックスの構築のときに呼ばれるbtbuild()について前回のつづき。_bt_leafbuild()から。

  • _bt_leafbuild()
    • BTWriteStateを作成する。BTWriteStateはどれだけページを割り当てたかとか何番目のページまで書き込んだかを管理する。
    • tuplesort_performsort()を呼び出しタプルのソートを実行する。
    • _bt_load()を呼び出す。
  • _bt_load()
    • ユニークインデックスの場合は重複を除くような処理をしているよう。
    • 初めての処理ならばBTPageStateを作成。BTPageStateは対象にしているページについての情報をもつ。ページにタプルが追加されるたびに更新されていく。
    • ソートされたタプルを1つずつ取り出してそのタプルを_bt_buildadd()に渡す。
    • すべてのタプルを取り出したら_bt_uppershutdown()を呼んで最後の処理。
    • それから同期処理（fsyncを呼び出すような処理）。WALやCHECKPOINTとの関係がコメントにあるけど読み取れず。共有バッファに書いているわけじゃないから明示的な同期が必要とかそういうことかな？
  • _bt_buildadd()
    • ページにタプルが入るスペースがあるときは_bt_sortaddtup()を呼び出してタプルを追加。
    • ページにスペースがないときは、同じ階層に新しくページを作って、新しいページには古いページの最後のタプルをコピーし、自分のhigh keyが自分の最後のタプルをさすように調整。そして古いページと親とのリンクをはる。それから古いページと新しいページの相互を関連付ける。その後で、_bt_blwritepage()を呼び出し古いページをディスクに書く。新しいページには今回追加すべきタプルを追加。
  • _bt_uppershutdown
    • _bt_load()から_bt_buildadd()の呼び出しが終了した時点ではこんな状態（○は書き出されていないページ。●は書き出されたページ。 ／と＼は親から子へのリンク。＝は兄弟間のリンク）。
    ○      … ROOT PAGE
   ／
  ●＝○    … INTERNAL PAGE
 ／＼／
●＝●＝○  … LEAF PAGE
    • _bt_uppershutdown()が呼び出されると、right mostのページがLEAFの方向から書き出されて、ルートを指すメタページも作成され書き出される。
    ●      … META PAGE
    ｜
    ●      … ROOT PAGE
   ／＼
  ●＝●    … INTERNAL PAGE
 ／＼／＼
●＝●＝●  … LEAF PAGE
    • メタページは一番最初のブロックに作成される。
    • right mostのページしか扱わない。rigth mostのページはhigh keyがいらないということでそこをつぶす処理が入っている。

今後の課題

  • high keyの必要性がよくわかっていない。high keyのところは隣同士のページで同じキーが存在することになる？

追記
high keyはページの中でもっとも大きな値（を指す）。インデックスツリーの同じ階層のページで右のページに移動するかどうかの判断に使われる。scan keyがhigh keyより大きければ右のページへ移動となる。関数でいうと_bt_moveright()。