B+TreeとLSM-Treeのストレージ構造比較：読み書き増幅と設計トレードオフ
原論文とRocksDB資料に基づき、B-treeとLSM-Treeの変更反映、検索・マージのトレードオフ、負荷別の確認方法を比較します。
発行・訂正窓口：infostoa · 編集基準
この記事の個別の執筆者・専門査読者の情報は提供されていません。
B+TreeとLSM-Treeでは、索引の変更をストレージへ反映する方法が異なります。B-treeは原論文が比較対象とする従来型の索引構造で、LSM-Treeは変更をメモリ上の構成要素に集めた後、ディスク上の構成要素へ段階的に統合します。どちらかが常に高速というわけではありません。挿入・削除と検索の比率、検索結果をすぐ返す必要性、構成要素を移動するコストを合わせて判断します。
原論文が示すワークロード条件
Patrick O’Neil、Edward Cheng、Dieter Gawlick、Elizabeth O’Neilの論文は、急増する履歴テーブルへの索引付けを課題として取り上げています。要旨は、B-treeなど従来のディスク索引を挿入のたびに維持するI/Oコストを問題として示します。LSM-Treeは索引変更を遅延・集約し、メモリ構成要素から一つ以上のディスク構成要素へ順次伝える設計として説明されています。狙いは、挿入や削除が多い状況でディスク探索のコストを抑えることです。
これは書き込みが無コストになるという意味ではありません。LSM-Treeでは新しい索引項目をまず小さなメモリ常駐構成要素に入れ、その後、より大きなディスク構成要素へ移します。論文は検索時に各構成要素を調べること、マージ中も短いロック期間を除いて索引値を取得できることを述べています。一方、即時応答が必要な一部の索引検索ではI/O効率が低下し得るとも明記しています。「書き込みは常に高速」「読み取り遅延は発生しない」と単純化できません。
論文が適する条件として挙げるのは、取得検索より索引挿入が多いワークロードです。例は履歴テーブルやログファイルです。書き込みが多いという理由だけで、即時検索が中心のシステムも同じ条件に当てはまるとは限りません。製品の分類名ではなく、実際の操作比率と応答時間要件を確認します。
2つの構造と、資料から断定できないこと
論文の2構成要素モデルはLSMの変更経路を具体化します。履歴行の索引項目はメモリ常駐のC0構成要素に追加され、その後のrolling mergeでディスク常駐のC1構成要素へ移ります。検索はどちらの構成要素からも項目を見つけられます。著者らはマージをmerge sortに似た処理として説明し、各変更を最終的なディスク位置へ即時に書く代わりに配置を遅らせる設計を示します。これが論文で確認できる中核であり、現代の各エンジンのファイル構成や調整方法まで同一だとは限りません。
同論文は履歴索引の例でB-treeを従来型の比較対象にします。ランダムな口座キーと大規模な蓄積履歴索引を使う特定のベンチマーク条件についてI/Oコストを計算し、その結果をLSM方式の動機として示しています。この数値は現在の全B-tree実装、ストレージ装置、バッファプール、データ分布に普遍的に当てはまる測定値ではありません。また、参照した資料は全B-treeのページサイズ、固定の木の高さ、すべての更新でディスクページ全体を書き直す規則を裏付けていません。そうした説明には対象エンジンの資料が必要です。
製品名と構造を同一視しないことも重要です。今回確認した専門資料が説明するのはRocksDBのleveled compactionです。この資料はClickHouseや複数のデータベース製品をLSM-Treeとして分類する根拠にはなりません。特定製品を比較するときは、対象のテーブル型や索引エンジンについて製品自身の資料を確認してください。
RocksDB資料に見るcompactionの交換条件
RocksDBの「Leveled Compaction」ページは、LSM実装で読み取りと書き込みの負荷がどう交換されるかを示す具体例です。ページはL0ファイルが多すぎると多くのクエリの読み取り性能を損ねると説明しています。RocksDBはL0ファイルの一部をより大きなファイルへcompactionできます。この処理は追加のwrite amplificationを伴う一方で、L0のread amplificationを改善し得ると記載されています。同じ説明では、この追加コストとleveled compaction全体でしばしば生じる書き込み増幅も区別されています。
これはRocksDB固有の説明であり、あらゆるLSM-Treeの保証や固定コストではありません。実務上の要点は「compactionすれば必ず読み取りが速くなる」ではなく、読み取り時に参照するファイルを変えるために書き込みとバックグラウンドI/Oを使うことです。RocksDBの当該設定を検討する場合も、導入するバージョン、設定、負荷で効果を測ります。このページだけから別のデータベースや異なる負荷の遅延・書き込みコストは予測できません。
専門家の視点：製品ラベルではなく負荷を測る
原論文が示す「取得検索より索引挿入が多い」という適用条件を、検証可能な仮説として使えます。まず挿入、削除、点検索、範囲検索の割合と、それぞれに必要な応答時間を記録します。現在の処理が論文の高更新量の履歴テーブルに近いかを確認してください。即時検索が必要なら、書き込み率が高くても論文が述べるI/O効率低下の可能性を評価から外せません。
根拠資料には明確な範囲があります。LSM論文は1990年代のディスクコストモデルと特定の履歴テーブル例を分析しています。保存されたPDFには「To be published」と記されているため、このコピーから発行年は断定していません。RocksDB wikiは一つの実装におけるleveled compactionの説明です。両資料は設計の動機とRocksDBの具体的な交換条件を支えますが、現行製品の順位付けや最新ストレージでの性能予測は支えません。資料を仮説づくりに使い、実際に検討するエンジンと装置で確認してください。