ストレージエンジンの系統樹

二大系統という見取り図

データベースの「ストレージエンジン」とは、行やキーバリューを実際にディスクへ配置し、読み書きする最下層のコンポーネントです。一見すると InnoDB・RocksDB・WiredTiger・LevelDB・Bw-tree と無関係な固有名詞が並んでいるように見えますが、内部の更新方式で見ると B+Tree 系と LSM 系という二つの系統にきれいに分かれます。

分岐の根は、更新をどう扱うかという一点です。

• B+Tree 系: 対象ページを探して その場で書き換える（in-place update）。ソート済みの木をたどるので読み取りが安定して速い。
• LSM 系: 更新を 追記して、後でまとめて畳む（out-of-place update）。ランダム書き込みをシーケンシャル化するので書き込みに強い。

この対立軸そのものは B+Tree インデックスの内部構造 と LSM-Tree とログ構造化ストレージ で詳説しています。本稿はその上に立ち、どのエンジンがどの系統から、いつ、なぜ分岐したかを系統樹として整理します。

系統樹の全体像（年代と系統）

主要エンジンを発祥年とともに二本の幹に振り分けて並べると、分岐の構図がはっきり見えます。

B+Tree 系の幹：InnoDB と WiredTiger

B+Tree 系の起源は 1970 年代の B-Tree 理論で、データを葉に集約した B+Tree が索引の標準になりました。理論の詳細は B+Tree インデックスの内部構造 に譲り、ここでは実装系統の分岐を見ます。

InnoDB（MySQL の既定エンジン）

InnoDB の最大の特徴は クラスタ化インデックスです。表データそのものが主キーの B+Tree の葉に格納され、行が主キー順に物理配置されます。これにより主キー範囲検索は葉リンクをたどる順次読みになりますが、副次インデックスは「主キー値」を指すため、二段階の探索（副次索引 → 主キー索引）が必要になります。

InnoDB は B+Tree に MVCC（多版型同時実行制御） を組み合わせ、更新時に旧版を Undo ログへ退避します。in-place 更新でも読み取りが版を見られるのはこのためです。

WiredTiger（MongoDB の既定エンジン）

WiredTiger は系統樹の中で特異な存在で、B+Tree と LSM の両方をエンジン内に実装しています。テーブル作成時に type=btree か type=lsm を選べる設計で、MongoDB の既定は B+Tree 構成です。

LSM 系の幹：LevelDB から RocksDB へ

LSM 系の理論的起点は O'Neil らの 1996 年の論文ですが、実用上の系統樹の根は **LevelDB（2011, Google）**です。Bigtable で培われた SSTable + コンパクションの考え方を、単体の組み込みライブラリとして結晶化させました。構造の基礎（MemTable・SSTable・WAL・コンパクション）は LSM-Tree とログ構造化ストレージ で扱っています。

LevelDB → RocksDB の分岐

RocksDB（2012, Facebook）は LevelDB の **フォーク（直接の派生）**です。HDD 時代に設計された LevelDB を、SSD と高並列・大容量のサーバー環境向けに作り直したものです。主な変更点を整理します。

RocksDB は単体の DB ではなく ストレージエンジンのライブラリとして設計されたため、MySQL（MyRocks）・CockroachDB・TiDB・Kafka Streams など多数のシステムが内部に組み込み、LSM 系の事実上の標準実装になりました。系統樹で言えば、LevelDB が根、RocksDB が太い幹、その先に各 DB の採用が枝として広がる形です。

LSM 系の系統（簡略）
  LSM-Tree 理論(1996)
        │
  Bigtable / SSTable の実装(2000s)
        │
     LevelDB(2011, Google)
        │ フォーク
     RocksDB(2012, Facebook)
        ├─ MyRocks（MySQL のエンジン差し替え）
        ├─ CockroachDB / TiDB（分散 DB の下層）
        └─ Kafka Streams ほか

橋渡しの枝：Bw-tree

Bw-tree（2013, Microsoft Research）は、系統樹上で B+Tree 系と LSM 系を橋渡しする位置にあります。論理的には B+Tree（多分木・ソート済み・範囲検索可）でありながら、更新方式は LSM 的な追記を採るためです。

核心は二点です。

1. デルタ更新（out-of-place）: ページを直接書き換えず、「この更新を適用せよ」という小さな デルタレコードを追記し、デルタ連鎖の先頭をページとして見せる。一定数たまったら統合（コンソリデーション）する。発想は LSM のコンパクションに近い。
2. マッピングテーブルによる Latch-Free: ページを物理アドレスでなく 論理ページ ID で参照し、ID から実体への対応表を **CAS（Compare-And-Swap）**で原子的に差し替える。これによりロック（ラッチ）なしで更新でき、マルチコアでスケールする。

通常の B+Tree:  ページを探す → その場で書き換える（要ラッチ）
Bw-tree     :  ページを探す → デルタを先頭に追記し、
               マッピングテーブルのポインタを CAS で差し替え（ラッチ不要）
               Δ(挿入) → Δ(削除) → ... → ベースページ

つまり Bw-tree は「B+Tree の論理構造」に「LSM 的な追記更新」と「Latch-Free 並行制御」を載せたハイブリッドです。SQL Server の Hekaton（インメモリ OLTP）で採用され、ロック競合を避けたい高並列ワークロードに向きます。

系統を貫く一本の軸：増幅トレードオフ

なぜ系統が二つに分かれたのか。最終的には 書き込み増幅・読み取り増幅・空間増幅のトレードオフ（RUM）に行き着きます。in-place 更新は読み取りを安定させる代わりに書き込みがランダムになり、out-of-place 更新は書き込みをシーケンシャル化する代わりに読み取りと空間で増幅を払う、という非対称性です。

この軸の選び方は、トランザクション処理が読み取り主体か書き込み主体かに依存し、RDB と NoSQL の使い分け の判断にも直結します。どの系統でも更新の永続性は ライトアヘッドログ（WAL） が支えており、WAL は系統を問わず共通の土台である点も押さえておきましょう。

まとめ