Write and Run

it's a simple way, but the only way.

B+Treeのページレイアウトと可変長タプル

これは 自作DBMS Advent Calendar 2020 - Adventar 1日目の記事です。

初日からギリギリで大丈夫なんですかねぇ(主催者)。

先日こういう記事を書きました。

Rustで古典的なDisk-Oriented DBMSを実装した話 - Write and Run

その中で、

このあたりで固定長のページをノードとした B+Tree に、可変長のデータを入れようとすると途端に実装が面倒になることに気が付きます。 と書いたのですが、具体的にどう面倒になるのかについてはなにも説明しませんでした。 今回は固定長のページに可変長のタプルを入れるとなにがどう面倒なのかという話を解説します。

テーブルヒープにおける可変長タプル

まず、B+Tree ではなく単純なテーブルヒープを考えます。 PostgreSQL のテーブルデータなどがそういう実装ですね。

これは CMU の例の講義で説明されています。

03 - Database Storage I (CMU Databases Systems / Fall 2019) - YouTube

可変長のタプルはページの末尾に詰め、そこの各タプルへのポインタをページの頭に詰めるという方法です。 Slotted pages などと呼ばれているデータ構造です。 ポインタは固定長なので、インデックスを用いて可変長のタプルへ O(1) でアクセスできるようになります。 こうすると1ページあたりに入るタプルの数はそこに入るタプルのサイズによってまちまちになりますが、テーブルヒープではこれは問題になりません。

B+Tree のリーフノードにおける可変長タプル

続いて、B+Tree のリーフノードに可変長のタプルを入れる事を考えます。 インメモリで実装される B+Tree ではノードあたりのタプル数を固定にすることが多いですが、前述のとおり固定長のページをリーフノードとする場合はタプル数を固定にできません。 B+Tree にはノード分割という操作があるため、この性質が厄介なことを引き起こします。 タプル数固定のノードの分割ではタプル数が1/2になるように分割すればよく、またタプル数を1/2にしたノードには1つは必ずタプルを追加できるため困ることはありません。 固定長ページ・要素数可変のノードの分割では、分割によって作られた新しいノードに含まれるタプルの合計サイズが元のノードのそれをちょうど超えるように分割し、新規に挿入するタプルは元のノードの方に追加します。

さて、ここで問題になるのは「分割後のノードの空き容量は挿入するタプルに対して十分か」ということです。 最悪の場合、せっかく分割したのに結局入らないということになりかねません。

これを解決する最も簡単な方法は、ノードに含められるキャパシティの半分のサイズをタプルのサイズの上限とすることです。 こうすることで、分割後のノードには必ずタプルを追加できるようになります。 InnoDB などもこのようになってますね。

二分探索と slotted pages

Slotted pages の問題点として、二分探索と相性が悪いという点があります。 値の比較をするためにポインタを辿らなければならないため、CPU のキャッシュをぜんぜん活かせません。 そのため、キーが固定長であればキーを連続して埋めたほうがよいのですが、私の書いた qp ではキーが固定長であるにも関わらずそのような最適化はしていません。 これは同じデータ構造を使いまわしてサボるためです。 (両方実装してベンチマークで比較とかしてみたいですね)

おわり

日付変更1時間前に書き始めたのであまりおもしろいことが書けませんでした。 まだアドベントカレンダーの枠はたくさんあまっているので、追加のトピックについては適当な日の枠を使って書いていこうかと思います。