B+Tree vs LSM-Tree 比較図
読み・書き・空間の3つの増幅で、B+Tree と LSM-Tree の得手不得手が一枚で腑に落ちます。どちらをいつ選ぶか、採用DBの理由まで原理から掴めます。
- 1.B+Tree は更新を「その場で書き換え」、LSM-Tree は「追記してから後でまとめる」設計。この違いが全特性の源。
- 2.B+Tree は読み込み増幅が小さく更新DB向き、LSM-Tree は書き込み増幅を小さくでき大量書き込み・SSD向き。空間増幅は逆。
- 3.B+Tree は PostgreSQL/MySQL(InnoDB)、LSM-Tree は RocksDB/Cassandra/LevelDB が代表。読み書き比で選ぶ。
2つのストレージ構造を分ける一点
ディスク常駐のデータベースで「キーと値をどう並べて保存するか」を担うのが ストレージエンジン です。代表格が B+Tree と LSM-Tree（Log-Structured Merge-Tree） で、両者の全特性は次の一点から導けます。
- B+Tree: データを置くべき場所を探し、その場（in-place）で書き換える。木は常にソート済みで保たれる。
- LSM-Tree: 更新を 末尾に追記（append） するだけで即完了し、ソートと整理は 後からバックグラウンドでまとめる。
「いますぐ整える」か「あとでまとめる」か。この設計思想の差が、後述する3つの増幅すべてを決めます。
3つの増幅という共通のものさし
ストレージエンジンの性能は 増幅（amplification） という指標で比較します。論理的な1回の操作が、物理的に何倍の仕事になるかの倍率です。
| 増幅の種類 | 意味 | 小さいほど良い理由 |
|---|---|---|
| 読み込み増幅 (Read) | 1件の読みで実際に走査する物理ブロック数 | クエリ1回あたりのI/Oが減る |
| 書き込み増幅 (Write) | 1件の書きで実際にディスクへ書く総バイト数の倍率 | SSD寿命とスループットに直結 |
| 空間増幅 (Space) | 論理データ量に対する実ディスク使用量の倍率 | ストレージコストが減る |
3つを同時に最小化することはできず、どれかを犠牲に何かを得るトレードオフになります。B+Tree と LSM-Tree は、この三角形のどの頂点を取るかが正反対です。
B+Tree の原理と増幅特性
B+Tree は、ソート済みの ページ（典型的に4〜16KB） をノードとする多分木です。葉ノードに実データ（または行ポインタ）が並び、リンクで連結されているため範囲スキャンが速い構造です。検索・更新の計算量は木の高さに比例し O(log N) です。これはインデックスが高速に絞り込める仕組みそのものです。
更新の流れ（in-place）:
1. ルートから葉まで O(log N) でページをたどる
2. 対象の葉ページをバッファプールへ読む
3. ページ内を書き換える（必要なら分割 split）
4. WAL に記録し、後でページ全体をディスクへ書き戻す
- 読み込み増幅: 小さい。木の高さ分のページ（多くは数段）を読むだけ。1キー1か所にしか無いので、読む場所が一意。
- 書き込み増幅: 大きめ。1バイト変えるだけでも ページ単位（数KB）丸ごと書き戻す。ページ分割や、クラッシュ耐性のための WAL（先行書き込みログ） で同じ更新を二重に書くため、増幅が積み上がる。
- 空間増幅: 小さい。ページに空きを残す（フィルファクタ）程度で、無駄が少ない。ただし更新の繰り返しでページが歯抜けになる 断片化 は起きうる。
LSM-Tree の原理と増幅特性
LSM-Tree は書き込みをメモリ上のソート済み構造（MemTable） にまず溜め、満杯になると SSTable（Sorted String Table） という不変（イミュータブル）ファイルとしてディスクへ一括フラッシュします。古い SSTable は コンパクション（compaction）で定期的にマージ・整理されます。
書き込みの流れ（append + 後追い整理）:
1. WAL に追記（クラッシュ耐性）
2. MemTable に挿入（メモリ上のソート構造）
3. 満杯になったら SSTable として一括フラッシュ（ランダムでなく順次書き込み）
4. バックグラウンドのコンパクションで複数SSTableをマージ
- 書き込み増幅: 制御可能で小さくできる。受け付け時は順次（シーケンシャル）書き込みのため高速。ただしコンパクションが同じデータを何度も書き直すので、戦略次第で増幅が変わる（後述）。
- 読み込み増幅: 大きめ。1キーが複数の SSTable に新旧バラバラに存在しうるため、新しい層から順に探す。古い値や削除マーカー（tombstone）も読み飛ばす必要がある。
- 空間増幅: 大きめ。削除は tombstone を追記するだけで即時には消えず、上書き前の古い値もコンパクションまで残る。
LSM-Tree の読み込み増幅は、補助構造で大きく緩和されます。ブルームフィルタ（その SSTable にキーが「無い」ことを高速判定し、無駄なディスクアクセスを省く）、各 SSTable 内のスパース索引、そしてブロックキャッシュです。実運用の LSM 系DBはこれらを前提に読み込み性能を確保しています。
コンパクション戦略が増幅を動かす
LSM-Tree の増幅は固定値ではなく、コンパクション戦略で読み・書き・空間のどれを優先するかを選べます。これが「LSM はチューニングで化ける」と言われる核心です。
| 戦略 | 仕組み | 得意 | 犠牲 |
|---|---|---|---|
| Leveled（レベル型） | 層ごとにキー範囲を重複なく整理 | 読み込み増幅・空間増幅が小さい | 書き込み増幅が大きい |
| Tiered / Size-Tiered | 同サイズのSSTableを溜めてまとめてマージ | 書き込み増幅が小さい | 読み込み・空間増幅が大きい |
RocksDB の Leveled、Cassandra の Size-Tiered などが代表で、ワークロードに合わせて選びます。一方 B+Tree にこの自由度はなく、特性はほぼ構造で固定されます。
一枚で対比する：増幅・適性・採用DB
ここまでを正面から並べたのが次の比較図です。
| 観点 | B+Tree | LSM-Tree |
|---|---|---|
| 更新方式 | in-place（その場書き換え） | append + コンパクション |
| 読み込み増幅 | 小さい（場所が一意） | 大きめ（複数SSTableを探索） |
| 書き込み増幅 | 大きめ（ページ単位・WAL二重書き） | 戦略次第で小さくできる |
| 空間増幅 | 小さい（断片化はありうる） | 大きめ（古い値・tombstone残存） |
| ランダム書き込み | 苦手（ランダムI/O） | 得意（順次書き込みに変換） |
| 範囲スキャン | 得意（葉のリンクをたどる） | 可だが複数SSTableのマージが要る |
| 向くワークロード | 読み多め・更新の多いOLTP | 書き込み多め・追記中心・時系列/ログ |
| 代表的な採用DB | PostgreSQL, MySQL(InnoDB), SQLite, Oracle | RocksDB, LevelDB, Cassandra, ScyllaDB, HBase |
採用DBの傾向は原理どおりです。汎用 RDBMS は読み書き混在の更新ワークロードが中心なので、読み込み増幅と空間効率に優れた B+Tree を採用します。一方、大量書き込みや時系列・ログを捌く分散DB（RDB と NoSQL の NoSQL 系に多い）は、ランダム書き込みを順次書き込みへ変える LSM-Tree が適します。
どちらを選ぶか：判断の指針
読み込みが多く・データを頻繁に上書きするなら B+Tree。書き込みが多く・追記中心・SSDの書き込み回数（寿命）を抑えたいなら LSM-Tree が基本線です。LSM はメモリへの一時バッファに依存するため、クラッシュ耐性は WAL が支えています。どちらも WAL を使う点は共通です。
LSM-Tree で大量削除や頻繁な上書きをすると、tombstone と古い値が溜まり、コンパクションが追いつかないと読み込みレイテンシが悪化し空間も膨らみます。特に「削除→範囲スキャン」は大量の tombstone を読み飛ばすため遅くなりがちで、設計時に削除パターンを見積もることが重要です。
最後に全体像を一言で。B+Tree は「整えてから書く」ことで読みを最適化し、LSM-Tree は「書いてから整える」ことで書きを最適化する——この対称性さえ掴めば、増幅・適性・採用DBはすべて一本の線で説明できます。データを複数ノードへ分散する設計（レプリケーションとシャーディング）と組み合わせて、ワークロードに最適なエンジンを選んでください。
データベース Article
B+Tree vs LSM-Tree 比較図を実務で読む
TL;DRは入口です。実際に選ぶ・使う段階では、何を解決するか、何と比較するか、導入後にどこで詰まるかまで見る必要があります。
解決すること
B+Tree
比較で見る軸
難易度: advanced / カテゴリ: データベース / タグ数: 5
導入後に効く点
B+Tree は読み込み増幅が小さく更新DB向き、LSM-Tree は書き込み増幅を小さくでき大量書き込み・SSD向き。空間増幅は逆。
先に潰すリスク
用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。
- 難易度
- advanced
- カテゴリ
- データベース
- タグ数
- 5
判断チェックリスト
- 自社の用途が「B+Tree / LSM-Tree」に近いか確認する。
- 強みである「B+Tree は更新を「その場で書き換え」、LSM-Tree は「追記してから後でまとめる」設計。この違いが全特性の源。」が本当に評価軸になるか確認する。
- 注意点の「用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。」を運用で吸収できるか確認する。
- 公開値や仕様値は、対象プラン・対象機種・対象リージョンまで確認する。
- 既存システム、ID、ネットワーク、監視、バックアップとの接続方法を先に洗い出す。
- 小さく試してから、本番移行、権限設計、障害時手順、コスト監視を決める。