# LSMツリー ## 定義 LSMツリー（Log-Structured Merge-Tree）は、書き込みをメモリ上のデータ構造（メムテーブル）にバッファリングし、閾値に達した時点でソート済みファイル（SSTable）としてディスクに逐次書き込みする永続化手法である。複数の SSTable はバックグラウンドのコンパクション処理でマージされる。すべてのディスク書き込みが逐次的であるため、ランダム書き込みが生じる B-Tree ベースの手法と比較して高い書き込みスループットを達成する。Bigtable と Cassandra がこのパイプラインを採用し、大規模分散ストレージの標準的な永続化アーキテクチャとなった（Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]、[[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]]）。 ## 横断的知見 - Cassandra と Bigtable はともにコミットログ → メムテーブル → SSTable → コンパクションの同一パイプラインを採用しているが、実装上の差異がある。Bigtable は GFS 上に SSTable を格納し GFS のレプリケーションに耐久性を依存するのに対し、Cassandra はローカルファイルシステム上に SSTable を配置しアプリケーション層でレプリケーションを管理する。この違いにより、Cassandra は GFS のような分散ファイルシステムへの依存を排除し、独立したデプロイを可能にした（Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]、[[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]]）。 - Cassandra はコミットログ用に専用ディスクを確保し、コミットログの書き込みスループットを最大化する設計を採用している。128 MB 超でコミットログをローリングし、ビットベクタで各カラムファミリの永続化状態を追跡してパージする仕組みは、Bigtable の論文には記述されておらず、Cassandra 固有の運用上の改良である（Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]）。 - **LSM ツリーの長期運用課題は、コンパクションそのものをユーザー提供経路から切り離す方向へ進む**: 2006 年 Bigtable 論文はマイナー/マージ/メジャーコンパクションをタブレットサーバの基本機構として説明した。2026 年論文では、ファイル構築をタブレットサーバ外のジョブへ外部化し、タブレットサーバの CPU/RAM をユーザーリクエストへ残す設計へ移っている。LSM ツリーの書き込み効率はコンパクションの後払いコストを伴うため、大規模運用では「どのコンパクション戦略か」だけでなく「どの資源階層で実行するか」が重要になる。(Source: [[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]], [[@2026__SIGMOD Companion__Twenty Years of Bigtable]]) - **LSM ツリーの「階層（レベル）」は設計上の必須要素ではなく、フラット等価パート構造でも書き込み効率・継続的マージは成立する**: ClickHouse の MergeTree* は全パートを等価に扱いレベル管理を持たない。これによりレベルをまたいだマージが可能になるが、トゥームストーンによる更新・削除が使えないため、マージ戦略（置換マージ・集計マージ・TTL マージ）で代替する。WAL も使わず INSERT を直接ディスクに書き込み、ペイロード別マージ戦略を組み合わせることで OLAP 向け高スループットを実現する。（Source: [[@2024__PVLDB__ClickHouse - Lightning Fast Analytics for Everyone]]） - **LSM ツリーは集計型やマテリアライズドビューの整合性メタデータを載せる基盤にもなる**: Bigtable のカウンタ/CRDT 実装は、各 LSM 層に subtotal と未解決操作を持つ changelog を保存し、コンパクション時に changelog を統合・トリミングする。これは LSM ツリーが単なる永続化構造ではなく、非同期レプリケーション下での集計整合性を維持するメタデータ構造にもなることを示す。(Source: [[@2026__SIGMOD Companion__Twenty Years of Bigtable]]) - **コンパクション方針は WA/RA の静的トレードオフから平均クエリスループットの資源投資問題へ移る**: EcoTune は、現代 SSD ではフラッシュ用資源を予約すれば書き込みレイテンシはコンパクション方針に大きく左右されず、残り CPU/I/O をコンパクションとクエリへどう配分するかが中心だと示す。Leveling は瞬時 RA では有利でも、図1で CPU の 62% 超をコンパクションに使い、Lazy Leveling の 64% のクエリスループットに落ちた。これは既存の「コンパクション頻度のトレードオフ」問いに対し、平均性能とタイミングを目的関数に入れる回答である。(Source: [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]]) - **現代 SSD 環境では、LSM ツリー優位の前提も B-Tree 優位の前提も再測定が必要になる**: EcoTune は LSM ツリーのコンパクションを平均クエリスループットへの資源投資問題として再定式化した。一方、B-Trees Are Back は、B-Tree が可変長レコード・4 KiB page・inline storage・適応 leaf layout を保つと、純インメモリ索引に近い lookup 性能と強い scan / paging 性能を両立できると示す。したがって、storage engine の選択は「LSM = write、B-Tree = read」という古典的二分法ではなく、background work、space efficiency、range scan、SSD read 確率を同じモデルで見る必要がある。(Source: [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]], [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]]) - **LSM ツリーの write-ahead log と SSTable(あるいは WiredTiger の log/sst ストリーム)は、コンパクション戦略だけでなく物理的な配置(SSD のゾーン・ストリームへの分離)によっても性能を改善できる**: [[Valet]] は RocksDB の WAL と SST、および WiredTiger の log と sst をそれぞれ別々のデバイスストリーム(SSD のゾーンまたは書き込みバッファ)に隔離することで、f2fs 実装に対し RocksDB の fill/overwrite で2倍超、WiredTiger(LSM モード)のマルチスレッド書き込みで3倍のスループット改善を得た。これは、LSM ツリーの性能最適化がコンパクションポリシー(ソフトウェア層)だけでなく、下層デバイスへのデータ配置(ハードウェア/インターフェース層)にも及ぶことを示す、これまでのこの concept の知見に対する新しい軸である。(Source: [[@2025__SoCC__Valet - Efficient Data Placement on Modern SSDs]]) - **書き込み amplification を抑えるために値をツリー外へ追い出す設計は、KVS レイヤーだけでなくストレージノード内部の物理配置設計にも現れる**: WiscKey がキーバリューストア一般の設計として value を分離するのに対し、ShardStore は S3 のストレージノードという文脈で shard データ(value 相当)を LSM ツリー外の「エクステント」という append-only 物理領域へ配置し、LSM ツリー自体は shard 識別子からチャンクへのポインタのみを保持する。これにより、LSM ツリーの役割は「値の永続化」から「物理配置へのインデックス」へと純化される。さらに ShardStore は、この物理配置の crash-consistent な順序制御を soft updates 由来の宣言的な `Dependency` 型で扱っており、LSM ツリーと crash consistency protocol を独立した関心事として分離する設計判断は、Bigtable/Cassandra が GFS/ローカル FS のレプリケーション機構へ整合性を委ねるのと対照的である。(Source: [[@2021__SOSP__Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3]], [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]], [[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]]) - **write-once-read-many なワークロードは、LSM ツリーのメムテーブル+SSTable+コンパクションという三段構成そのものを不要にし、確定済み不変セグメントへの単純な追記だけで済ませられる**: Bigtable/Cassandra の LSM ツリーは、可変ストア(メムテーブル)への書き込みと不変ストア(SSTable)へのマージを継続的に繰り返すコンパクション処理を前提とし、この処理はディスク I/O 上の大きなコストになる(→本概念の「外部コンパクション」「資源投資問題」に関する既存知見)。Honeycomb Retriever([[@2026__OReilly__Observability Engineering 2E - Chapter 13 Efficient Data Storage with Retriever]])はこのコストそのものを設計から排除する: Bigtable のようにレコードを既存の不変レイヤー群へ上書き挿入するのではなく、現在アクティブなセグメントの末尾にのみ追記し、1時間・250,000レコード・1GBのいずれかの閾値で確定させた後は二度と書き換えない。オブザーバビリティのようにレコードが本質的に write-once(一度書かれたイベントは更新されない)であり、かつ新規データを常に末尾へ追記できる場合、LSM ツリーが解決する「ランダム書き込みの逐次化」問題自体が発生しないため、コンパクションという後払いコストを完全に回避できる。これは LSM ツリーが前提とする「更新可能なキーバリューストア」という性質が、append-only なイベントストリーム(トレース・ログ)には最初から不要であることを示す、ワークロード特性による設計分岐の具体例である。(Source: [[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]], [[@2026__OReilly__Observability Engineering 2E - Chapter 13 Efficient Data Storage with Retriever]]) - **ClickHouseの「フラット等価パート構造・WALレス・INSERT直書き」という設計は、2つの独立した一次資料(学術論文と書籍の実務章)によって一致して確認され、さらに書籍側はその採用理由をオブザーバビリティのワークロード特性から説明する**: 既存知見(本概念54行目)はPVLDB論文からClickHouseのレベルレス・WALレス設計を報告していたが、[[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]]はこれを「1 INSERT = 1パート」「パートは書き込み後不変・バックグラウンドマージで既定150GBまで統合」という具体的な数値とともに再確認する。さらに同章は、なぜこの設計が許容されるかを明示する: オブザーバビリティデータは本質的にwrite-once(追記されるだけで滅多に変更されない)であり、この性質がClickHouseの「不変パート・高速挿入パス」設計と整合すると述べる。これはRetriever(第13章)がwrite-once性を根拠にコンパクションそのものを排除したのと同じ観察を、コンパクションを維持するMergeTreeの文脈で独立に導いたものであり、「オブザーバビリティ=write-once」という前提が、コンパクションを残す設計(ClickHouse)と完全に排除する設計(Retriever)という異なる帰結を導きうることを示す。(Source: [[@2024__PVLDB__ClickHouse - Lightning Fast Analytics for Everyone]], [[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]], [[@2026__OReilly__Observability Engineering 2E - Chapter 13 Efficient Data Storage with Retriever]]) - **教科書的な size-tiered / leveled という二分法は、実装固有の「資源投資問題」としての再定式化(EcoTune)の前段にある一般化された経験則として位置づけられる**: DDIA 第4章は size-tiered compaction(新しく小さい SSTable を古く大きい SSTable へ逐次マージし高い書き込みスループットを得るが一時的に多くのディスク空間を要する)と leveled compaction(SSTable サイズを固定し L0, L1, ... のレベルへ段階的にマージしディスク効率と読み取り性能を優先する)という2戦略を、「書き込み多・読み取り少なら size-tiered、読み取り中心なら leveled」という経験則として提示する。これは EcoTune([[LSMツリーコンパクション]])が Leveling(RocksDB既定)と Lazy Leveling を比較し、瞬時の読み取りアンプリフィケーションでは Leveling が有利でも平均クエリスループットではコンパクションのCPU占有により Lazy Leveling の64%まで落ち込むと示した知見の、教科書レベルでの一般化された前段に相当する。DDIA の経験則は「どちらを選ぶか」という静的な二択を示すのに対し、EcoTune はさらに踏み込み「同じ Leveling 系戦略の中でも平均スループットを目的関数として動的に資源配分すべきだ」と主張しており、教科書的知識と最新研究の間に一段の抽象度の差があることを示す好例である。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] "Compaction strategies", [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]]) - **RocksDB の backpressure(メムテーブル満杯時の読み書き一時停止)は、DDIA が LSM ストレージエンジン一般の設計原理として明示する挙動であり、Valet・cache_ext が扱う RocksDB 固有のI/O最適化(SSDへのデータ配置、ページキャッシュのadmission filter)とは異なるレイヤーの問題である**: 既存知見([[RocksDB]] エンティティ)は RocksDB を Leveling既定方針・ホスト誘導SSD配置・ページキャッシュ観測の3つの文脈でしか記述していなかったが、DDIA 第4章はこれに加え、書き込みが速すぎてコンパクションが追いつかない際に RocksDB が読み書きを一時停止してディスクへの書き出しを待つ backpressure 機構を、LSM ストレージエンジン全般に共通するレイテンシスパイク対策として一般化して説明する。これは物理層(SSDへのデータ配置)・観測層(ページキャッシュのヒット率)とは異なる、スループット制御という第3のレイヤーでの LSM ツリー最適化軸を示す。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] "Read performance", [[@2025__SoCC__Valet - Efficient Data Placement on Modern SSDs]]) - **RUM 予想は、既存知見が個別に論じてきた LSM ツリーコンパクション最適化(WA/RA トレードオフの資源投資問題化)を、Read/Update/Memory という 3 軸の一般理論として位置づける教科書的な枠組みを与える**: 詳説 データベース第7章は、読み取り・更新(≒書き込み)・メモリ(≒利用領域)の3オーバーヘッドのうち2つを削減すると必然的に3つ目が悪化するという RUM 予想[ATHANASSOULIS16]を紹介し、B-Tree を読み取り最適化、LSM ツリーを書き込み最適化と位置づける。この3軸モデルは、EcoTune([[LSMツリーコンパクション]])が示す「読み取りアンプリフィケーション最小化(R軸)は平均クエリスループット最大化と一致しない」という知見のうち、EcoTune が扱わなかった M 軸(利用領域)を明示的に含む、より広いコストモデルである。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]] §7.2.1, [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]]) - **教科書(詳説 データベース第7章)は、既存知見が ShardStore との対比で参照していた WiscKey の value 分離設計を、Bitcask との系譜の中で体系的に説明する**: 既存知見(本概念上記)は WiscKey を「キーバリューストア一般での value 分離」の代表例として ShardStore(S3 の extent への shard 配置)と対比していたが、詳説 データベース第7章はこの設計の起源を明確にする。[[Bitcask]] は memtable を持たず全キーを keydir(インメモリ HashMap)に保持してディスクへ直接ログ書き込みする順序付けられない LSM ストレージだが、全キーをメモリ保持しなければならず範囲クエリを一切サポートしないという2つの問題を持つ。[[WiscKey]] はキーをソート済み LSM ツリーに残しつつ値だけを vLog(順序なし追記ファイル)に分離することでこの2問題を解決する。これにより、ShardStore の「LSM ツリーを物理配置へのポインタのみに純化する」設計([[@2021__SOSP__Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3]])は、KVS 一般の系譜としては Bitcask→WiscKey という順序付けなし LSM ストレージの発展の先にある応用として位置づけ直せる。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]] §7.4, [[@2021__SOSP__Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3]]) - **FDツリーはLSMツリーの着想を明示的に継承しつつ、可変メムテーブルを持たない点で異なる具体化を取る**: [[@2021__OReillyJapan__詳説 データベース - Chapter 6 Bツリーの亜種]] §6.4は、FDツリーの設計をLSMツリーに「少し似ている」と明記した上で、具体的な違いを示す。LSMツリーはミュータブルなメムテーブル→イミュータブルなSSTable→コンパクションという三段構成を取るのに対し、FDツリーはミュータブルな小さなヘッドBツリー(メムテーブルに相当)から、kを因数として段階的にサイズが増加する複数のイミュータブルな対数的配列へ内容を伝播させ、レベル間の検索コストをフラクショナルカスケーディング(上位レベルの要素を下位レベルへのブリッジとして間引いて引き上げる技法)という専用機構で削減する。このブリッジ機構は、本概念が既存知見で扱ってきたLSMツリー実装(Bigtable・Cassandra・RocksDB・ClickHouse)のいずれにも見られない、FDツリー固有の最適化である。一方、レベル間でデータを段階的にマージ・伝播させる基本構造そのもの(FDツリーの「対数的な配列」の作成・マージ)は、DDIA第4章が示すleveled compaction(SSTableサイズを固定しL0, L1, ...へ段階的にマージする方式)と同型であり、B-Tree系の亜種とLSM系のコンパクション戦略が独立に同じ「対数的レベル構造」という解に収束していることが分かる。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 6 Bツリーの亜種]] §6.4, [[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]], [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] "Compaction strategies") - [出典] LSM-treeを最初に定義した原論文(O'Neil, Cheng, Gawlick, O'Neil 1996, Acta Informatica)が本wikiに欠けていたため追加する。原論文は本概念で既に集約されているBigtable/Cassandra以降の実装(メムテーブル→SSTable→コンパクション)とは異なり、メモリ常駐C0成分とディスク常駐C1(以上)成分の間を明示的なrolling merge(マージソートに似た逐次的なマージ処理)で連携させる設計として提示している。C0のデータ構造は(2-3)木やAVL木などSSTable化を前提としない任意の平衡木でよいとされ、後続実装のSSTable方式(イミュータブルなソート済みファイル)への具体化は原論文には含まれない。M(バッチマージパラメータ)・COSTπ/COSTP比という2つの定量指標で、B-treeに対する最大2桁のディスクアーム削減効果を数式で導出している点が、後続の実装論文にはあまり見られない特徴である。(Source: [[@1996__Acta Informatica__The Log-Structured Merge-Tree (LSM-Tree)]]) ## 未解決の問い - EcoTune は平均スループットを最適化するが、クエリ到着率やレイテンシ SLO を直接目的関数に入れたコンパクション制御はどう設計されるべきか。 - メムテーブルのフラッシュ閾値と top level 容量は、EcoTune の $S=M/K$ 方針と、実運用のメモリ/SSD 比・多テナント制約の間でどう決めるべきか。 - 外部コンパクションはタブレットサーバの資源競合を減らすが、ファイル構築ジョブのオートスケール、失敗時リトライ、SSTable 導入前検証を含めた全体 TCO はどのように評価されるべきか。 - CRDT の changelog のように LSM 層へ意味的メタデータを載せる設計は、他のデータ型やセカンダリインデックスにも一般化できるか。 - LSM ツリーの block-level optimization と B-Tree の node-level optimization を、同一 key distribution・同一 memory/SSD 比・同一 range scan mix で比較する benchmark はどのように設計すべきか。 - ClickHouse の MergeTree* は WAL を使わず INSERT をディスクに直書きし電源断時の若干のデータ損失を許容する。第14章はこれをオブザーバビリティデータのwrite-once性で正当化するが、具体的にどの程度のデータ損失リスク(未フラッシュパートの秒数・行数換算)を許容しているかは定量化されておらず、この設計がOLAPユースケース一般(オブザーバビリティ以外)でどこまで成立するかも未検討である。 - ShardStore の「LSM ツリーと crash consistency を分離し、後者を宣言的な Dependency グラフで扱う」設計は、他の LSM ベースストレージシステム(RocksDB・WiredTiger 等)の crash consistency 実装(WAL ベース)と比べてどのような性能・保守性のトレードオフを持つか。 - FDツリーのフラクショナルカスケーディングによるレベル間ブリッジは、LSMツリー(Bigtable/Cassandra/RocksDB系)のレベル間検索(Bloom filterによるSSTableの絞り込みなど)と比べて、どちらが読み取りレイテンシを小さくできるか。同一key distribution・同一レベル数での定量比較はあるか。 - Honeycomb Retriever はコンパクションを完全に回避するが、その代償としてバックフィルデータ(遅延到着イベント)が混入すると1セグメントのタイムスタンプ範囲が不必要に広がり、クエリ時のプルーニング効率が下がるという弱点を抱える(→ [[Zonemap]])。LSM ツリーのコンパクションが担っていた「データを整理して読み取り効率を保つ」役割を、append-only 設計はどこまで手放してよいのか、事後的な再編成(post facto rewriting)を導入するコストとの損益分岐点はどこにあるか。 ## 関連 - ソース: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]] / [[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]] / [[@2026__SIGMOD Companion__Twenty Years of Bigtable]] / [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]] / [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]] / [[@2024__PVLDB__ClickHouse - Lightning Fast Analytics for Everyone]] / [[@2025__SoCC__Valet - Efficient Data Placement on Modern SSDs]] / [[@2021__SOSP__Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3]] / [[@2026__OReilly__Observability Engineering 2E - Chapter 13 Efficient Data Storage with Retriever]] / [[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]] / [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 6 Bツリーの亜種]] / [[@1996__Acta Informatica__The Log-Structured Merge-Tree (LSM-Tree)]] - 概念: [[結果整合性]] / [[一貫性ハッシュ法]] / [[LSMツリーコンパクション]] / [[B-Tree]] / [[列指向OLAPデータベース]] / [[ホスト誘導データ配置]] / [[軽量形式手法]] / [[データパーティショニング]] / [[転置インデックス]] - エンティティ: [[Apache Cassandra]] / [[EcoTune]] / [[RocksDB]] / [[ClickHouse]] / [[Valet]] / [[ShardStore]] / [[Retriever]] / [[Honeycomb.io]] / [[Lucene]] / [[Bitcask]] / [[WiscKey]] ## 出典 - [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]（§5.6 Local Persistence、§5.7 Implementation Details——コミットログ、メムテーブル、SSTable、コンパクション） - [[@2006__OSDI__Bigtable - A Distributed Storage System for Structured Data]]（SSTable、コンパクション） - [[@2026__SIGMOD Companion__Twenty Years of Bigtable]]（外部コンパクション、カウンタ/CRDT、SSTable 導入前検証） - [[@2025__SIGMOD__Rethinking The Compaction Policies in LSM-trees]]（§3 コンパクションの資源投資観、§4 EcoTune、§5 RocksDB 評価） - [[@2025__SIGMOD__B-Trees Are Back - Engineering Fast and Pageable Node Layouts]]（§8 LSM-Trees、B-Tree 最適化の LSM block への転用可能性） - [[@2021__SOSP__Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3]]（§2.1 Design Overview——エクステント外への shard データ配置、§2.2 Crash Consistency——Dependency 型） - [[@2026__OReilly__Observability Engineering 2E - Chapter 13 Efficient Data Storage with Retriever]]（コンパクションを回避する追記専用・時間ウィンドウ・セグメント設計） - [[@2026__OReilly__Observability Engineering 2E - Chapter 14 Efficient Data Storage with ClickHouse]]（MergeTreeの1挿入1パート・不変パート・既定150GBマージ上限の再確認とwrite-once性による正当化） - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 4 Storage and Retrieval]]（SSTable/メムテーブル/Bloom filter/tombstoneの教科書的定義、size-tiered/leveled compactionの経験則、RocksDBのbackpressure） - [[@2021__OReillyJapan__詳説 データベース - Chapter 7 ログ構造化ストレージ]]（§7.2.1 RUM予想、§7.4 Bitcask/WiscKeyによる順序付けされないLSMストレージ） - [[@2021__OReillyJapan__詳説 データベース - Chapter 6 Bツリーの亜種]]（§6.4 FDツリー——フラクショナルカスケーディングと対数的な配列によるLSMツリー着想の異なる具体化） - [[@1996__Acta Informatica__The Log-Structured Merge-Tree (LSM-Tree)]](LSM-treeを最初に定義した原論文。rolling merge・多成分の最適サイズ比・並行性制御・回復を数式付きで提示)