LSM-tree
Log-Structured Merge-tree — datastrukturen bakom moderna write-heavy databaser. Skrivningar landar först i RAM (memtable), flushas till oföränderliga sorterade filer (SSTables) på disk, och kompakteras i bakgrunden.
O'Neil et al. (1996). Vinner mot B-tree på skrivningar: sekventiell I/O istället för random, ingen in-place-uppdatering. Förlorar lite på läsningar (måste kolla flera nivåer) — kompenseras med bloom filters per SSTable.
Underbygger LevelDB, RocksDB, Cassandra, ScyllaDB, HBase, BigTable, DynamoDB, MongoDB WiredTiger, FoundationDB. Trade-off-knapparna: tiered vs leveled compaction, write/read/space amplification.