B+木と LSM ツリー

使い方

• 「B+木」ではキーを挿入・検索・範囲検索し、根から葉へたどる様子やノードの分割を 1 コマずつ見られます。1 つのノードに入るキーの数を小さくすると、分割がよく起きて木が高くなります。
• 「LSM ツリー」ではキーを書き込み・削除・検索し、メムテーブルからの書き出し（フラッシュ）とレベルをまとめ直す様子（コンパクション）を見られます。
• 「比べる」では、同じキーの列を両方に入れたときの書き込みと読み込みの手間を比べます。
• 再生や ◀ ▶ でコマを動かします。キーボードの ← → でも動かせます（入力欄にフォーカスがないとき）。

B+木

ディスクは 1 バイトずつではなくページ（数 KB）単位で読み書きするので、データベースのインデックスは 1 つのノードに多くのキーを詰めた、背の低い木にします。B+木では、データはすべて葉に置き、内部ノードは道案内の区切りだけを持ちます。ノードがあふれたら 2 つに分け、区切りのキーを親に渡します。根が分かれたときだけ木が高くなるので、どの葉も同じ深さに保たれます。葉どうしを横につないでおくことで、範囲検索は最初の葉まで降りたあと横にたどるだけで済みます。

LSM ツリー

LSM ツリー（Log-Structured Merge-Tree）は、書き込みをまずメモリ（メムテーブル）にため、いっぱいになったら並べ替えた SSTable としてディスクにまとめて書き出します。SSTable は書き換えず、更新や削除も「新しい版」や「削除の印（トゥームストーン）」を追記するだけです。古い版はコンパクションでまとめ直すときに捨てます。検索は新しい場所から順に探し、最初に見つけた版が答えです。ないキーの検索で全部の SSTable を読まずに済むよう、SSTable ごとにブルームフィルタ（「確実にない」か「あるかも」を答える小さなビット列）を持たせます。

このアプリは、L1 以降を各レベル 1 つの SSTable にまとめるレベル方式（LevelDB・RocksDB の既定）を簡単にしたものです。実際のシステムでは、SSTable をキーの範囲ごとに小さなファイルに分けて一部だけをまとめ直したり、障害に備えて書き込みを先にログ（WAL）へ書いたりします。