LSM Tree

LSM trees are a write-optimized data structure used by databases like Cassandra, RocksDB, and LevelDB. Writes are batched in memory (memtable) and flushed to immutable sorted files (SSTables) on disk; reads merge data across levels.

LSM trees provide high write throughput at the cost of read amplification and periodic compaction overhead. They are well-suited for time-series and high-ingest workloads.