TL
データベース

LSM-Tree とログ構造化ストレージ

書き込みが詰まる DB の裏側にある LSM-Tree。メモリ上の追記とディスクへの一括書き出しで書き込みを速くする原理と、B+Tree との増幅トレードオフが分かります。

応用LSM-TreeストレージエンジンSSTableコンパクションB+Tree最終更新: 2026-06-21
TL;DR要点だけ先に
  • 1.LSM-Tree は更新をメモリ上の MemTable に追記で受け、満杯になったら SSTable としてディスクへシーケンシャルに書き出す。ランダム書き込みを順次書き込みに変えるのが速さの正体。
  • 2.読み取りは MemTable→新しい SSTable→古い SSTable の順に探すため複数ファイルを横断する。コンパクションで SSTable を統合し、読み取り増幅とディスク使用量を抑える。
  • 3.B+Tree が読み取りに強く更新を in-place で行うため書き込みがランダムになりがちなのに対し、LSM-Tree は書き込みに強くシーケンシャル化する代わりに読み取り増幅と空間増幅が大きい。RUM の三すくみを意識して選ぶ。

なぜ「ログ構造化」なのか

HDD でも SSD でも、ストレージは シーケンシャル（順次）書き込みがランダム書き込みより圧倒的に速いという性質を持ちます。ディスクのあちこちに散らばった位置を更新するより、末尾にひたすら追記するほうが効率が良いということです。LSM-Tree（Log-Structured Merge-Tree） は、この性質を最大限に活かすために生まれたストレージ構造です。RocksDB・LevelDB・Cassandra・ScyllaDB・HBase など、書き込みの多いシステムの内部で広く使われています。

考え方の核心はシンプルです。「更新箇所を直接書き換えない（in-place update をしない）」。代わりに、すべての変更を新しい記録として 追記 していき、古い記録は後でまとめて整理する。この「追記中心 + 後追いの整理」が、ログ構造化ストレージの本質です。

4つの構成要素

LSM-Tree は次の4つの部品が連携して動きます。

部品置き場所役割
WAL（先行書き込みログ）ディスククラッシュ復旧のための更新ログ。落ちても MemTable を再構築できる
MemTableメモリ直近の更新を保持するソート済み構造。書き込みはまずここへ入る
SSTableディスクMemTable をソート済みのまま書き出した不変（immutable）ファイル
コンパクションバックグラウンド複数の SSTable を統合し、重複・削除済みデータを掃除する処理

書き込みの流れ

  1. WAL に追記: まず更新内容を WAL（Write-Ahead Log）へシーケンシャルに書く。これは永続性のための保険で、メモリ上の MemTable が消えても WAL から再生できる。考え方はトランザクションの永続性（Durability）と同じです。
  2. MemTable へ反映: 次にメモリ上の MemTable（赤黒木やスキップリストなど、キー順を保てる構造）へ書く。ここまで来たら書き込み完了を返せます。ディスクへのランダム書き込みを待たないので速い。
  3. フラッシュ: MemTable が一定サイズに達したら immutable に切り替え、内容をソート済みのまま SSTable としてディスクへ一括書き出し（シーケンシャル）。書き出しが済めば対応する WAL は破棄できます。
書き込み: WAL(追記) → MemTable(メモリ, ソート済み)
                          │ 満杯
                          ▼
                  フラッシュ（シーケンシャル書き出し）
                          ▼
            SSTable_3  SSTable_2  SSTable_1  ...（新→旧, 各々ソート済み・不変）
SSTable は「不変」が肝

SSTable（Sorted String Table）は一度書いたら書き換えません。更新も削除も「新しい記録の追記」で表現します。たとえばキー K を消すときは、消す代わりに「K は削除済み」という目印（トゥームストーン, tombstone）を新しい SSTable に書きます。不変だからこそ、読み取り中のファイルにロックが要らず、バックアップやキャッシュも単純になります。

読み取りはなぜ複雑になるか

更新を追記で表現する代償は 読み取り に出ます。あるキーの最新値は、どの SSTable に入っているか分かりません。そこで 新しいものから順に 探します。

  1. まず MemTable（最新）を見る。
  2. なければ新しい SSTable から古い SSTable へ順にたどる。
  3. 最初に見つかった記録が最新値（トゥームストーンなら「削除済み」と判断）。

このままでは存在しないキーの検索で全 SSTable を読みかねません。これを避ける仕組みが2つあります。

  • ブルームフィルタ: 各 SSTable に「このキーは含まれない」を高速判定する確率的フィルタを持たせる。「含まれない」は確実（偽陰性なし）なので、無駄なファイル読み取りをほぼ排除できる。「含まれる」判定には誤検知（偽陽性）がありうるが、その場合だけ実際に読む。
  • スパースインデックス: SSTable はキー順なので、一定間隔のキーとファイル内オフセットの対応表を持てば、目的キー付近へ直接ジャンプできる。
範囲検索はマージで処理する

各 SSTable がキー順にソートされているため、複数 SSTable と MemTable を同時に走査する k-way マージで範囲スキャンを処理できます。同じキーが複数ファイルにあれば最も新しいものを採用します。これはインデックスの B-tree が単一の木で範囲検索を完結できるのと対照的で、LSM では「複数のソート済み列をマージする」点が特徴です。

コンパクション：散らばった記録を畳む

SSTable は増え続けるため、放置すると（1）読むファイルが増えて読み取りが遅くなり、（2）古い値やトゥームストーンが残ってディスクを食います。これを解決するのが コンパクションです。複数の SSTable を読み込み、キーでマージし、各キーの最新値だけを残した新しい SSTable を書き出します。古い記録・上書きされた値・回収済みのトゥームストーンはここで捨てられます。

代表的な戦略は2つです。

戦略仕組み得意代償
Leveled（レベル化）L0,L1,L2... と階層化し、各レベル内はキー範囲が重複しないよう保つ読み取り増幅・空間増幅が小さい書き込み増幅が大きい
Size-Tiered（サイズ階層）同程度のサイズの SSTable が一定数たまったらまとめて統合書き込み増幅が小さい読み取り増幅・空間増幅が大きい

Leveled では、L0 を除く各レベルでキー範囲が重ならないため、特定キーは各レベルで高々1ファイルしか見ずに済み、読み取りが安定します。一方で上のレベルへ押し上げる際に既存ファイルと何度も書き直すため、同じデータが繰り返し書かれます。Size-Tiered は逆に、まとめ書きが少なく書き込みに優しい代わりに、同じキーの古い版が複数階層に残りやすく、読み取りとディスク使用量が膨らみます。

3つの「増幅」と RUM トレードオフ

LSM-Tree と B-tree 系（B+Tree）の違いは、3種類の **増幅（amplification）**で整理できます。

  • 書き込み増幅（Write Amplification）: 1バイトの論理更新に対し、実際にディスクへ書かれるバイト数。コンパクションで何度も書き直すほど増える。
  • 読み取り増幅（Read Amplification）: 1回の論理読み取りで実際に読むデータ量・ファイル数。SSTable が多いほど増える。
  • 空間増幅（Space Amplification）: 論理データ量に対する実ディスク使用量。古い版やトゥームストーンが残るほど増える。

これらは同時には最小化できない **RUM 仮説（Read-Update-Memory の三すくみ）**として知られます。どれかを良くすると別のどれかが悪化する関係です。

観点LSM-TreeB+Tree
書き込み方式メモリ追記 + シーケンシャル書き出し対象ページを探して in-place 更新
書き込み増幅コンパクション戦略次第（中〜大）ページ単位の書き戻し・分割で中
読み取り（点）複数 SSTable 横断（フィルタで緩和）木を根から葉へ1経路で安定して速い
空間増幅古い版・トゥームストーンで増えやすい断片化（内部の空き）で増える程度
得意ワークロード書き込み主体・ログ・時系列読み取り主体・更新が局所的な OLTP

ざっくり言えば、B+Tree は読み取りに強く更新を直接書き換える代わりに書き込みがランダムになりがち、LSM-Tree は書き込みをシーケンシャルに均す代わりに読み取りと空間で増幅を払うという非対称な関係です。これは RDB と NoSQL の選択軸とも重なり、書き込みスループットを重視する系のエンジンが LSM を採る理由になっています。

削除は「すぐ消える」わけではない

LSM ではトゥームストーンを書いてもデータはすぐ消えません。実体は、それより古い SSTable がコンパクションで統合されるまで残ります。さらに、削除直後はトゥームストーン自体がファイルを増やすため、大量削除の直後はかえって読み取りが重くなることがあります。時系列データの大量 DELETE 後にスキャンが遅くなる現象はこれが原因で、TTL とコンパクションの設計が運用の勘所になります。

試験・面接で問われる要点

「LSM がなぜ書き込みに速いか」は ランダム書き込みをシーケンシャル書き込みに変換するからと即答できるように。WAL=永続性の保険、MemTable=メモリ上のソート済みバッファ、SSTable=不変のソート済みファイル、コンパクション=統合とゴミ掃除、という対応関係と、書き込み・読み取り・空間の3増幅トレードオフがセットで問われます。

まとめ

まとめ

LSM-Tree は、更新を WAL + MemTable で受けて SSTable へシーケンシャルに書き出し、増え続ける SSTable を コンパクションで畳む構造です。狙いは ランダム書き込みの順次化で、書き込みスループットに強い反面、読み取りは複数ファイルを横断するため ブルームフィルタとコンパクションで増幅を抑えます。B+Tree との違いは **書き込み・読み取り・空間の増幅トレードオフ（RUM）**に集約され、書き込み主体なら LSM、読み取り主体の局所更新なら B+Tree が向きます。大規模化の文脈ではレプリケーションとシャーディングと組み合わせて使われることも押さえておきましょう。

データベース Article

LSM-Tree とログ構造化ストレージを実務で読む

TL;DRは入口です。実際に選ぶ・使う段階では、何を解決するか、何と比較するか、導入後にどこで詰まるかまで見る必要があります。

解決すること

LSM-Tree

比較で見る軸

難易度: advanced / カテゴリ: データベース / タグ数: 5

導入後に効く点

読み取りは MemTable→新しい SSTable→古い SSTable の順に探すため複数ファイルを横断する。コンパクションで SSTable を統合し、読み取り増幅とディスク使用量を抑える。

先に潰すリスク

用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。

数字・仕様の読み方
難易度
advanced
カテゴリ
データベース
タグ数
5

判断チェックリスト

  • 自社の用途が「LSM-Tree / ストレージエンジン」に近いか確認する。
  • 強みである「LSM-Tree は更新をメモリ上の MemTable に追記で受け、満杯になったら SSTable としてディスクへシーケンシャルに書き出す。ランダム書き込みを順次書き込みに変えるのが速さの正体。」が本当に評価軸になるか確認する。
  • 注意点の「用語だけ覚えても、設計・実装・運用でどこに効くかを確認しないと判断を誤る。」を運用で吸収できるか確認する。
  • 公開値や仕様値は、対象プラン・対象機種・対象リージョンまで確認する。
  • 既存システム、ID、ネットワーク、監視、バックアップとの接続方法を先に洗い出す。
  • 小さく試してから、本番移行、権限設計、障害時手順、コスト監視を決める。

次に確認する観点

LSM-TreeストレージエンジンSSTableコンパクションB+TreeLSM-TreeストレージエンジンSSTable
参考: 公式情報