自作RDBMS: B-Index

B-Tree

ほとんど全てのRDBにおいての標準的なIndexの実装であり続けている.
非リレーショナルなDBでも利用されている.

• SSTableと同様に、B-TreeはKey-ValueのPairをKeyでSortされた状態で保持
  • そのため、Key-ValueのLookupや範囲に対するQueryを効率よく処理できる
• B-Treeは、databaseを固定サイズのBlockあるいはPageに分割する
  • このBlockのサイズは4KB程度
  • 1つのPageが1度に読み書きされる
    • この設計は下位層のハードウェアとの関係性が密になるが、diskもまた固定サイズのblockを並べることによる
  • LSM-Treeで利用されているlog-structured Indexは、databaseを通常数MB以上の可変サイズのセグメントに分割し、常にセグメントをsquentialに書き込む

B-Treeの構造について

各PageはAddressあるいは場所によって識別できるため、あるページから他のページを参照できる(disk上の話)

• Lookup
  1. 1つのPageがB-Treeのルートとなる
     • このIndex中でLookupしたい場合、出発点(Root)となる
  2. 251というkeyを探しているため、200<=key<300のrefを追う
  3. さらに、250<=key<270のrefを追う
  4. 最終的に個別のkeyが格納されているPage(leaf page)にたどり着く
     • leaf pageにはそれぞれのkeyに対する値が含まれているか、もしくはあたいがあるPageへの参照が含まれている

1Page内の子ページへの参照数は**分岐係数(Branching Factor)**と呼ばれる.(図の場合、分岐係数=6となる)

• Update

  1. 対象keyを含むleaf pageを参照
  2. 参照したpage内の値を更新してpageをdiskに書き込む

• Insert

  1. 対象keyをを含む範囲を持つleaf pageを参照
  2. 以下の分岐に分かれる
     • 参照したPageに十分なspaceがある場合
       1. そのPageに追加して、diskに書き込む
     • 参照pageに新しいkeyを受け入れるだけのspaceが存在しない場合
       1. そのPageを半分だけ埋まった2つのPageに分割
       2. 親Pageを配下にできた新しい2つのKeyの範囲に合わせて更新

B-Tree Algorithm

• n個のKeyを持つB-Treeの深さは常に、O(log n)になる
  • Treeはバランスが保たれることを保証されるアルゴリズムであるため
• Page Size 4KB で深さが 4レベルであり、分岐係数が500のTreeは最大256TBを保存できる

ビッグオー記法（Big O notation)

• O(1): 定数時間.入力データのサイズに関係なく、アルゴリズムの実行時間は一定
• O(n): 線形時間.入力データのサイズに比例して、アルゴリズムの実行時間が増加する
• O(n^2 ): 二次時間.入力データのサイズの二乗に比例して、アルゴリズムの実行時間が増加する
• O(logn): 対数時間.入力データのサイズの対数に比例して、アルゴリズムの実行時間が増加する
  • バイナリサーチ（二分探索）など
  • 対数的な成長は、線形的な成長O(n) や二次的な成長 O(n^2) などの他の複雑さの指標と比べて非常に効率的

B-Tree安全性&Performanceについて

B-Tree 耐久性の保証

• データの永続性
  • トランザクションがコミットされた後、そのトランザクションによって行われた変更は永続的に保存され、システムの障害やクラッシュが発生しても失われることはない
• 回復能力
  • システムが障害やクラッシュから回復した場合、データベースは最後にコミットされた状態に復元される必要がある
    • Write-Ahead Log（WAL(redo logとも呼ばれる)）のメカニズムを使用して実現
    • これらのログには、トランザクションの変更内容が記録されていて、障害の後にデータベースを正しい状態に復元するために使用
• データの整合性
  • トランザクションが完了すると、データベースは一貫した状態になる
  • つまり、部分的に完了したトランザクションや中断されたトランザクションによる変更は、データベースに反映されない
• ハードウェア障害の対応
  • ディスク障害やその他のハードウェアの問題が発生した場合でも、耐久性はデータの安全性を保証
    • 冗長性、バックアップ、レプリケーションなどの技術を使用して実現される

Performance

• Key全体ではなく、短縮したKeyを保存することによってPage内の領域を節約
• leaf pageがdisk上でsequantialになるように試みる実装がされている
  • 理由は、一般的にdisk上でpageがどこに配置されるかはわからない
    • そのため、keyの範囲の近くのPageが、disk上でも近くにあるかはわからない(->範囲scanのqueryに対してIO処理に時間がかかる傾向がある)
  • Treeが大きくなるに従って、この順序を保つことは困難になる傾向がある
• Treeに追加のポインタを配置
  • leaf pageの左右に隣接するpageのrefを持たせることで、keyの範囲scan時に、親Pageの参照を不要にできる