操作して学ぶ
B-Tree vs LSM-Tree 書き込み対決
同じキー列を2つのストレージエンジンに挿入して、書き込みの挙動を並べて見ます。B-Tree はその場で書き換え（ランダムI/O＋ページ分割）、LSM-Tree はメモリに溜めて追記し、後でまとめて整理（コンパクション）します。
同じランダムキー列を両方に挿入します。
B-Tree （RDBの索引）
- ディスク書き込み 0（挿入0 ＋ 分割0）
- パターン ランダムI/O（その場で該当ページを書き換え）
- 読み取り O(log n) 単一パスで速い
LSM-Tree （RocksDB/Cassandra）
memtable
満杯でフラッシュ
L0
—
- フラッシュ 0 ／ コンパクション 0
- 総ディスク書き込み 0 エントリ（書き込み増幅 —倍）
- パターン シーケンシャルI/O（追記のみ・分割なし）
B-Treeはその場更新で書き込みバイトは少ないが、ディスク上の飛んだ位置を書き換えるランダムI/O。 LSM-Treeは全て追記（シーケンシャル）なので個々の書き込みが速い代わりに、コンパクションで同じデータを何度も書き直す書き込み増幅が起きる。 だからLSMは書き込み多めのワークロードやSSDに向き、読み取りは複数レベルを見るためブルームフィルタで補います。すべてブラウザ内で計算。
どちらを選ぶか
- B-Tree（PostgreSQL・MySQL/InnoDB）：読み取りが単一パスで速く、更新がその場。汎用OLTPの既定。書き込みはランダムI/O。
- LSM-Tree（RocksDB・Cassandra・LevelDB）：書き込みが全て追記で速く、SSDにも優しい。代償はコンパクションの書き込み増幅と、複数レベルを見る読み取りコスト（ブルームフィルタで軽減）。
- 書き込み多め・時系列・ログならLSM、読み書きバランス・強い整合の更新ならB-Treeが定石。