B木とLSM木 — データベースの心臓

世のデータベースはほぼ全部、B木かLSM木のどちらかの上に建っています。「ディスクはページ単位でしか書けない」という物理から出発して、両者がなぜ正反対の設計になったのか、書込増幅とは何か、PostgreSQLとRocksDBで何が違うのかを、前提知識ゼロから実務のパラメータ名まで。

比喩: 棚に差し込むか、箱に積むか

図書館に新しい本が届いたとき、整理のやり方は2つあります。ひとつは、届くたびに正しい棚まで運び、既にある本を少しずつずらして所定の位置へ差し込む。もうひとつは、受付の箱にとりあえず積んでおいて、箱がいっぱいになったら棚とまとめて並べ直す。

前者は探すのが常に速い。棚がいつも整列しているからです。代わりに1冊受け取るたび、棚の前での作業が発生します。後者は受け取りが速い。積むだけですから。代わりに探すときは「棚」と「箱の中」の両方を見なければならず、ときどき大掛かりな並べ直しが走ります。

これがそのまま B木（B-tree） と LSM木（Log-Structured Merge-tree） の違いです。B木は1972年にBayerとMcCreightが発表し、以来ほとんどのデータベースが採用してきました。LSM木は1996年にO'Neilらが提案した、書き込みを追記に寄せる設計です。PostgreSQL・MySQL・SQLite・OracleはB木系、RocksDB・LevelDB・Cassandra・ScyllaDB・HBaseはLSM系。今のデータベースは、ほぼ全部このどちらかの上に建っています。

同じ「保存して探す」という仕事に、なぜ正反対の答えが2つ生き残っているのか。理由はコンピュータの中の物理にあります。

前提: ディスクは1バイトでは読めない

両者を分けている事実がひとつあります。永続化装置は「ページ」という塊の単位でしか読み書きできない、ということです。

1バイトだけ書き換えたいときでも、装置は数KBの塊を読み、その中の1バイトを直し、塊ごと書き戻します。PostgreSQLはこの塊を8KB、MySQLのInnoDBは既定で16KBとして扱います。SSDに至っては、内部的には「消去ブロック」というもっと大きな単位でしか消せません。

だからデータベースでは、計算量の勘定がメモリ上のアルゴリズムと変わります。比較の回数ではなく、何ページ触ったかが実行時間を決める。ふつうの二分探索木は理論上 $O(\log_2 N)$ ですが、1ノードにつき1ページ踏むなら10億件で30回のディスクアクセスです。ページ1枚がメモリの数百倍以上遅いことを思えば、実用になりません。

メモリの中でも同じ話が一段小さい規模で起きていることはキャッシュに優しいコードで扱いました。B木とLSM木は、その論理をディスクまで押し広げた答えです。

B木: 分岐を太らせて段数を減らす

B木の発想は単純です。1ノードを1ページまるごと使う大きさにして、そこに数百個のキーを詰め込む。二分木の「左か右か」ではなく、「この数百個の区切りのうちどこか」を1回のページ読み込みで決めてしまう。

$h$ は木の段数、$N$ はキーの数、$B$ は1ノードから下へ伸びる枝の数（分岐数、fanout）です。式(1)は要するに、段数は件数そのものではなく「$B$ を底とする対数」にしかならないと言っています。

その $B$ は、ページの大きさとキーの大きさで決まります。

$$B \approx \frac{P}{k + p}$$

$P$ はページのバイト数、$k$ はキー1個のバイト数、$p$ は子ページを指すポインタのバイト数。つまり「1ページに（キー＋ポインタ）が何組入るか」を数えているだけです。8KBのページに8バイトの整数キーを詰めれば $B$ は数百のオーダーになり、$N$ が10億でも段数は4〜5に収まります。二分木の30回が、これで片手に収まる。

対数がどれだけ穏やかに伸びるか、線形の伸びと並べて動かしてみてください。B木の段数は、この一番寝ている線に乗っています。

探し方も見ておきましょう。根ページを読み、キーの並びの中から目的の値が入る区間を選び、その子ページへ降りる。これを葉に着くまで繰り返すだけです。挿入で木が伸びるときも、下に伸びるのではなく根が上に増える。だからどの葉も根からの距離が等しく、B木は放っておいても均衡が保たれます。「たまたま偏った木ができて遅くなる」がないことが、素朴な二分探索木との実務上いちばん大きな違いです。

なお実際のDBが使うのは正確にはB木ではなく B+木 です。違いは2つ。実データ（またはその置き場所）を葉だけに置き、内部ノードは道しるべに徹すること。そして葉同士を横に連結しておくことです。前者は内部ノードにより多くのキーを詰められるので $B$ が大きくなり、後者のおかげで範囲検索は木を上り下りせず葉を横に辿るだけで済みます。