Log-Structured Merge trees optimize for writes:
Write path: Write to in-memory buffer (memtable)
When full, flush to disk as sorted file (SSTable)
Background compaction merges SSTables
Read path: Check memtable
Check SSTables from newest to oldest
Bloom filters skip SSTables without the key
Trade-offs:
- Writes: O() amortized (sequential I/O)
- Reads: O(log ) to O() (check multiple files)
- Space amplification from compaction
Used by: LevelDB, RocksDB, Cassandra, HBase