# 概要 - 主にデータベースのストレージエンジンで使われる[[Index]] - [[B+ Tree]]などはin-place updateを行うため、ランダムI/Oが発生する。LSM Treeはout-place updateを行い、書き込みがシーケンシャルになるため、書き込み性能が向上する - out-place updateなので、読み込み性能は低い - メモリに溜まってきたらディスクにマージしていく...（何層も階層化されている） - Leveling Merge Policy: レベル$L$のコンポーネント数は、レベル$L-1$のコンポーネント数のT倍となる - Tiering Merge Policy: 各レベルは$T$個のコンポーネントを持つ - memtableには[[Skip List]]、ディスク上では[[B+ Tree]], [[SSTable]]が広く使われる # 最適化 - クエリに[[Bloom Filter]]を使う。各コンポーネントに要素が含まれるかどうかをBloom filterで判定してクエリを高速化する。 - Partitioning: SSTableを特定のキー範囲ごと分割する。 - SSDはRandom Accessが得意なので、キーとバリューを分離するアーキテクチャが流行っている（LSM Treeにはkeyとロケーションだけを書く） # 並行性制御 - 並行での読み書きと、並行flush, 並行マージのサポートが求められている - [[Lock]], [[Multiversion Concurrency Controll]]が使われる # 参考 - いろんな亜種のサーベイ論文: [LSM-based storage techniques: a survey](https://arxiv.org/abs/1812.07527) - https://dasshshsd.hatenablog.com/entry/2019/12/04/000000 - [https://kumagi.hatenablog.com/entry/end-of-freezing-lsm-tree](https://kumagi.hatenablog.com/entry/end-of-freezing-lsm-tree) - - [https://github.com/facebook/rocksdb/wiki/Leveled-Compaction](https://github.com/facebook/rocksdb/wiki/Leveled-Compaction)