Log-Structured Merge Tree
An LSM tree appends writes to an in-memory table, flushing it to immutable SSTables when full, with multi-level compaction balancing write throughput against read amplification.
Purpose
To understand the core data structure of write-intensive storage engines, used in LevelDB/RocksDB/Cassandra.
Mechanism
Writes go to a MemTable (in-memory skip list); when full it is flushed to an L0 SSTable. Reads merge all SSTables + the MemTable. Compaction merges adjacent levels to reduce read amplification. LSM sequential writes optimize throughput at the cost of read and space amplification.
Use cases
- Write-intensive storage design
- SSTable optimization
- LSM Compaction