データベース選定や運用判断のうえで、その DBMS が「どのストレージエンジンを使っているか」は性能特性を大きく左右します。同じ「キーバリュー的な書き込み」でも、PostgreSQL（B-tree）と Cassandra（LSM tree）では書き込みパスもレイテンシ特性も大きく異なります。
本記事では『データ指向アプリケーションデザイン』（以下 DDIA）第3章「ストレージと抽出」をベースに、B-tree と LSM tree の構造を書き込みパス・読み取りパス・ストレージ効率の観点から比較し、テックリード／アーキテクトとして DBMS を選ぶ際の判断軸を整理します。
検索クエリ視点での B-tree 内部構造（リーフノード・双方向連結リスト・対数スケーラビリティ）は別記事『なぜインデックスは速いのか？B-treeの内部構造を図解する』で扱っています。本記事はその続編として、書き込みパスとコンパクションに焦点を当てます。
ストレージエンジンの2系統
DDIA によると、現代のストレージエンジンは大きく2系統に分かれます。両者の最大の違いは、ディスク上のデータを「その場で書き換える」のか、「新しい場所に書いて古いものを後で掃除する」のかという点です。
- B-tree 系
- ディスク上のデータをその場で書き換えるタイプ
- この方式をインプレース更新（in-place update、同じディスク位置を上書きするという意味）と呼ぶ
- PostgreSQL、MySQL InnoDB、SQL Server、Oracle など、ほぼすべてのリレーショナルデータベースが採用する標準的な構造
- LSM tree 系
- 新しい場所に追記し、古いデータは後でまとめて掃除するタイプ
- この掃除をコンパクションと呼ぶ
- LevelDB、RocksDB、Cassandra、HBase など、書き込みヘビーな分散データベース・組み込み KVS で多く採用される
この設計の違いが、書き込み・読み取り・ストレージ効率のトレードオフを決めます。詳細は次節以降で見ていきます。
B-tree 系の書き込み構造
ページ指向のインプレース更新
B-tree はディスクを固定サイズのページ（通常 4KB 程度）に分割し、各ページが他のページへの参照（ポインタ）を持ちます。書き込みは対象ページを読み込み、メモリ上で更新したあと、同じディスク位置に上書きします（これがインプレース更新です）。
ページが満杯になった場合は、ページを2つに分割して親ノードを更新します。複数ページにまたがる更新は B-tree の不変条件（balanced であること）を保つために必要ですが、その途中でクラッシュが起きるとインデックスが壊れる危険があります。
WAL（Write-Ahead Log）の役割
クラッシュからの整合性回復のために、B-tree は WAL（Write-Ahead Log、redo ログ） を使います。実際のページを書き換える前に、変更内容を WAL に追記しておき、クラッシュ後はリカバリ時に WAL を再生してページを正しい状態に戻します。
つまり B-tree の書き込みは、
- WAL にログを追記（シーケンシャル書き込み）
- 対象ページをインプレースで上書き（ランダム書き込み）
の少なくとも 2 回ディスクに書く構造になります。これが B-tree の書き込み増幅の主な原因です。並行アクセス時はラッチ（軽量ロック）でページを保護します。
LSM tree 系の書き込み構造
LSM tree（Log-Structured Merge-Tree）は Patrick O’Neil らが 1996年に発表した構造で、memtable・SSTable・コンパクションの3要素で成り立ちます。書き込みは memtable に入り、SSTable としてディスクへ書き出され、コンパクションで整理される、という流れです。読み取り経路は3要素の上で構成されるため、要素を順に見たあとで最後にまとめます。
memtable: 書き込みの受け口
書き込みはまず memtable と呼ばれるインメモリのソート済み構造（red-black ツリーや AVL ツリーなど）に格納されます。同時にディスク上のコミットログにも追記しておき、クラッシュ時のロストを防ぎます。
memtable が一定サイズに達したら、その内容をまるごとディスクに書き出します。書き出した先のファイルが次の SSTable です。
SSTable: ディスク上のソート済みファイル
memtable から書き出された SSTable（Sorted String Table）は、Bigtable 論文に由来する構造で、キーでソート済み・イミュータブル（一度書いたら変更しない）なファイルです。
flowchart TD
Write(["書き込み"]) --> Mem["memtable<br/>（メモリ）"]
Mem -- "サイズ閾値超過" --> SST["SSTable<br/>（ディスク、追記のみ）"]
ディスクへの書き込みは常に「新規ファイルへの追記」なので、ランダム書き込みは発生しません。これが LSM tree の書き込み高速性の源泉です。
コンパクション: 古い SSTable の整理
書き込みを続けると SSTable がどんどん増えていきます。古い SSTable と新しい SSTable には同じキーの新旧バージョンが混在しうるため、定期的にコンパクション（複数の SSTable をマージし、不要なエントリを捨てて新しい SSTable を生成する処理）が必要になります。
コンパクション戦略には主に2つあります。
- size-tiered: 同じくらいのサイズの SSTable をまとめてマージする（HBase が採用）
- leveled: SSTable を階層に分け、小さなファイルを上の階層、大きなファイルを下の階層に置く（LevelDB / RocksDB が採用）
コンパクションはバックグラウンドで動きますが、ディスク帯域を消費するため、コンパクション中はテイルレイテンシ（一部のリクエストの応答遅延）が大きくなりがちです。
読み取り経路と Bloom filter
3要素を踏まえると、読み取り経路は memtable → 新しい SSTable → 古い SSTable の順に探していき、最初に見つかった値を返す形になります。複数の SSTable をまたぐ可能性があるため、B-tree より読み取りパスが複雑になります。
存在しないキーの検索は、すべての SSTable を見にいくことになるため特に不利です。これを軽減するために Bloom filter（「キーが存在しない」ことを高確率で判定できる確率的データ構造）を各 SSTable に持たせ、無駄なディスクアクセスを削ります。
書き込み・読み取り・ストレージ特性の比較
書き込み増幅
書き込み増幅とは、論理的な1回の書き込みに対してディスクに何回書かれるかの指標です。
- B-tree
- 対象ページの上書きと WAL への追記で、最低でも2回ディスクに書く
- ページ分割が起きるとさらに増える
- LSM tree
- SSTable への初回フラッシュは1回
- その後コンパクションのたびに同じデータが書き直されるため、コンパクション戦略によって増幅率が大きく変わる
DDIA はどちらが有利かを定量的には断定せず、「LSM はシーケンシャル書き込みでディスク帯域を効率良く使え、B-tree よりも書き込み増幅が小さい設計が可能」と整理しています。実際の倍率は実装やワークロード、コンパクション戦略に大きく依存します。
読み取りコスト
- B-tree
- 木の深さ分のページ I/O だけで対象に到達できる
- 深さは数百単位の分岐係数で決まる。DDIA は「分岐係数が数百なら3〜4レベル、256TB に達するまでこの深さに収まる」と述べている
- LSM tree
- 複数の SSTable をまたぐ可能性があり、最悪ケースでは memtable と複数の SSTable をすべて確認することになる
- Bloom filter で軽減はできるが、読み取りレイテンシの予測しやすさは B-tree が勝る
ストレージ効率（圧縮・断片化）
- B-tree
- ページに空きスペースが残る、ページ分割で半分埋まりのページが生まれるなど、フラグメンテーションが起こりやすい
- LSM tree
- コンパクション後の SSTable は隙間なく詰めて書けるためフラグメンテーションが少なく、ブロック単位で圧縮もかけやすい
- DDIA は「圧縮率が高くフラグメンテーションも少ない」と整理している
採用 DBMS の例
- B-tree 系
- PostgreSQL、MySQL InnoDB、SQL Server、Oracle、SQLite
- リレーショナルデータベースのデファクトスタンダード
- LSM tree 系
- LevelDB、RocksDB、Cassandra、HBase、ScyllaDB
- 書き込みヘビーなワークロードや時系列・KVS で採用が多い
- Lucene 経由で Elasticsearch / Solr の全文検索インデックスも LSM 的な構造を取る
LSM tree 系の各プロダクト（Cassandra・DynamoDB・HBase 等）の機能・整合性・落とし穴の個別整理は『主要NoSQLプロダクトリファレンス: Redis・Cassandra・DynamoDB・MongoDB・Neo4j を中心に』で扱っています。書き込みヘビーな時系列やログ集約などユースケース起点でどのプロダクトが第一候補になるかは『ユースケース別NoSQL選定ガイド: 「こういうときはどのNoSQL？」を逆引きする』を参照してください。
設計判断のヒント
DBMS 選定で「B-tree か LSM か」は通常、製品選定の結果として決まります（PostgreSQL を選べば B-tree、Cassandra を選べば LSM）。逆に言えば、製品を選ぶ段階でどちらの特性が必要かを判断軸にできます。
- 書き込みヘビーで圧縮効率が重要な場合
- LSM 系を選ぶ
- 用途例: ログ・時系列・イベントストリーム・大量センサデータ
- 読み取りレイテンシの安定が重要な場合
- B-tree 系を選ぶ
- 用途例: OLTP 業務アプリ、ユーザー向けレスポンスが秒単位で問われる API
- トランザクション・複雑なクエリが必要な場合
- B-tree 系を選ぶ
- 強整合性のトランザクションやキー範囲ロックを使う処理は B-tree 系 RDBMS の方が実装が成熟している
- コンパクションのスパイクを許容できるか
- LSM はバックグラウンドのコンパクションでテイルレイテンシが揺れる
- p99 / p999 を厳しく問われる SLO ではここを評価する
- 運用ノウハウの蓄積
- チームが慣れている系統を選ぶことも重要な判断軸
まとめ
- ストレージエンジンは大きく B-tree 系（インプレース更新）と LSM tree 系（追記専用）に分かれる
- B-tree は WAL + ページ上書きで耐障害性を確保。読み取りが安定するが、書き込み増幅は WAL 起因で発生する
- LSM tree は memtable + SSTable + コンパクションという3要素で構成。書き込みは高速だが、読み取りは複数 SSTable をまたぐ可能性があり Bloom filter で補う。コンパクションでテイルレイテンシが揺れる
- DBMS 選定はワークロード特性（書き込み比率・レイテンシ要件・圧縮効率・運用習熟度）で決まる
両者の違いを表にまとめます。
| 観点 | B-tree | LSM tree |
|---|---|---|
| 書き込み方式 | インプレース更新（同じ位置を上書き） | 追記のみ（新しい場所に書く） |
| 書き込みのディスクパターン | ランダム書き込み中心 | シーケンシャル書き込み中心 |
| 耐障害性 | WAL（Write-Ahead Log） | コミットログ + memtable |
| 書き込み増幅の主因 | WAL + ページ上書き | コンパクションによる再書き込み |
| 読み取り経路 | ツリーをたどってページに到達 | memtable → 複数の SSTable を順に検索 |
| 読み取りレイテンシの予測しやすさ | 安定 | コンパクション中はばらつく |
| ストレージのフラグメンテーション | 起こりやすい | 起こりにくい |
| 圧縮効率 | 低め | 高め |
| バックグラウンド処理 | 比較的少ない | コンパクションが必須 |
| トランザクションのロック実装 | キー範囲ロックを実装しやすい | 複雑になりやすい |