Log-Structured Merge Tree
LSMツリーは書き込みをインメモリテーブルに追記し、満杯になると不変な SSTable へフラッシュする。複数レベルのコンパクションが書き込みスループットと読み込み増幅のバランスを取る。
目的
書き込み中心のストレージエンジンの中核データ構造を理解する。LevelDB/RocksDB/Cassandra で使用されている。
メカニズム
書き込みは MemTable（メモリ上のスキップリスト）に入り、満杯になると L0 SSTable にフラッシュされる。読み取りは全 SSTable と MemTable をマージする。コンパクションは隣接レベルを統合して読み込み増幅を抑える。LSM の逐次書き込みは、読み込み・空間増幅と引き換えにスループットを最適化する。
ユースケース
- 書き込み中心のストレージ設計
- SSTableの最適化
- LSMコンパクション