Log-Structured Merge Tree — writes fill the memtable, flush to SSTables, compaction merges levels, reads walk newest-first with bloom filters
| Operation | Cost | Note |
|---|---|---|
| put / delete | O(1) amortized | WAL append + memtable |
| flush | O(memtable), seq | one sequential write |
| get (leveled) | O(log_T n) | ≤1 SSTable/level |
| get miss (bloom) | ≈ O(1) exp. | skips SSTables |
| get (size-tiered) | O(T·log_T n) | overlapping runs |
| compaction | O(S) k-way merge | background, seq |
| write amp | ~L·T (leveled) | ~L (size-tiered) |
| space | O(live × SA) | obsolete + tombstones |