- 最近、Alex PetrovのDatabase Internalsを読みながら、DBMSストレージエンジンの実装方法、特にB-Treeデータ構造の最適化に関する内容に触れた
- 大学でB-Treeを学んだときは、単に「より良いBST」くらいに理解していて、実際になぜ使われるのかが腑に落ちなかった
- ディスクI/Oを考慮して大規模データを保存し高速に検索するために、B-Tree構造が適している
- この記事では、B-Treeがなぜ必要なのか、どのように動作するのか、そして実装上どのような最適化が可能なのかを紹介する
- 1つのノードに多くのキーを集めてディスクアクセス回数を減らす方式などが主な特徴である
ディスクによって生じる制約
- データ全体がメモリに収まらない状況を想定する
- ディスクは1回にページ単位で読み書きする特性がある
- ディスクアクセスはメモリアクセスに比べて非常に遅い
- したがってデータ構造はページ中心でデータを配置し、最小限のディスクアクセスでできるだけ多くのキー比較を行う必要がある
- BSTをそのままディスクに保存するとノードが散在するため、検索回数に応じてディスクアクセス回数も増える問題が生じる
- B-Treeはノードに複数のキーを集め、1回ディスクを読んだだけで複数のキーを比較できるようにする
スロットページ
- ディスクにデータを配置するときは「ページ」単位で管理する
- 各ページにはヘッダー、可変長データを格納するセル、セル位置情報を保存するオフセットポインタ配列がある
- スロットページ構造には、キーサイズが可変でも再配置の負担なく整列順序を維持できる利点がある
- キー削除や挿入時には、実データを動かすよりポインタだけを並べ替えるほうがはるかに効率的である
- たとえばSQLiteは、このようなページ構造内にfree listを置き、削除されたセル領域を再利用する方式を採用している
B-Tree検索
- B-Tree検索アルゴリズムは単純である:
- ルートノードから開始する
- 現在のノードの区切りキー（Separator Key）を見て、検索キーがありそうな子ノードを探す
- ツリーを再帰的に探索する
- 検索キーを含むリーフノードが見つかれば完了し、なければ存在しないと判断する
- 内部ノードには実データの代わりに区切りキーだけがあってもよく、実データはリーフノードにのみ格納されるのが一般的である
- 二分探索でノード内のキーを効率よく見つけるため、各ノード内のキーは整列された状態を維持する
区切りキー（Separator Key）の短縮
- 内部ノードの区切りキーは、実際のキー全体ではなく、範囲を区切れる程度で十分である
- たとえば0xAAAAAAと0xBBBBBBの間を区切るために、必ずしも0xBBBBBB全体を保存する必要はなく、より短いプレフィックスで区別できる
- キー長が大きいデータベースでは、このような短縮が大きなストレージ節約につながる
- 区切りキーの短縮以外にも、prefixやsuffixを効率よく削減する戦略がある
- リーフノードのほうがはるかに多いため、プレフィックス圧縮のほうが性能により大きく寄与するという見方もある
オーバーフローページ
- あるノードがあまりに多くのキーを持ち、1ページに収まりきらない場合は、オーバーフローページを活用する
- オーバーフローページにキー全体をそのまま移すのではなく、ノードには短いプレフィックスだけを残し、残りを分離して保存する
- こうすることで、キーの存在確認や範囲検索の際には、まずノード内のプレフィックスだけを確認し、本当に必要な場合にのみオーバーフローページを読むことになる
- ページを追加で割り当てても、全体の検索コストを下げる方法である
兄弟ポインタ
- ノード同士で左・右の兄弟ノードへのポインタを保存しておく実装方式がある
- これにより範囲検索時には、あるリーフノードから直接兄弟ノードへ移動しながら連続したキーを高速に探索できる
- 兄弟ポインタがない場合、再び親ノードまで上がってから下りる処理を繰り返す必要があり、I/Oコストが増加する
- 兄弟ノード間のキー範囲は互いに重ならないため、右の兄弟ポインタへ移動すれば「次のキー範囲」であることが保証される
B-Treeの派生形
- B⁺-Tree以外にもさまざまな派生データ構造が存在する
- WiredTigerのような「Lazy B-Tree」やLazy-Adaptive Treeは、書き込み操作をバッファリングして性能を高める方式を用いる
- FD-TreeはSSDの特性に合わせて設計された構造で、ブロック単位の書き込みのような物理的制約を考慮している
- Bw-Tree（Buzzword Tree）は、高い並行性とメモリ上でのツリーアクセスに最適化されたデータ構造である
結論
- 抽象的な「B⁺-Tree」の概念と、実装である「SQLiteのDBフォーマット」の間には、多くの最適化と実装上の細かな違いが存在する
- 最適化はBig-O計算量を変えないが、実環境ではデータベースの性能と使い勝手に大きく影響する
- ここで紹介された内容以外にも、個々のストレージシステムごとに細かなチューニングが数多く必要になる
- 「少しだけ付加情報が必要だ」という表現の裏には、実装の複雑さとデバッグの難しさが隠れている
- B-Tree構造をより実際に近い形で描いた例として、Designing Data Intensive ApplicationsのB-Treeダイアグラムが印象的である
1件のコメント
Hacker Newsの意見
ページの構造はヘッダー、セル、オフセットポインタで構成されており、可変長データを保存できる利点がある
B-Treeに関するアニメーションを含む素晴らしい記事
数年前に Ibrahim Jaluta の研究を基に、同時復旧可能な B-link Tree を実装した
SQLite ディスクページエクスプローラーを作って、B-Tree への理解が深まった
B-link Tree、並行性、ロックに関する内容は抜けているが、これは必要以上の情報かもしれない
過去のコメント: Hacker News
素晴らしい記事で、細部の重要性をうまく説明している
Golang を使った B-Tree 実装に関する良い資料
この記事の熱烈なファンで、著者と似たような「曖昧な理解」を持っていた