LSM-tree
Log-Structured Merge tree — the data structure behind modern write-heavy databases. Writes land in RAM first (memtable), get flushed to immutable sorted files (SSTables) on disk, and are compacted in the background.
O'Neil et al. (1996). Beats B-trees on writes: sequential I/O instead of random, no in-place updates. Loses a bit on reads (has to check multiple levels) — compensated with bloom filters per SSTable.
Underpins LevelDB, RocksDB, Cassandra, ScyllaDB, HBase, BigTable, DynamoDB, MongoDB WiredTiger, FoundationDB. Tuning knobs: tiered vs leveled compaction, write/read/space amplification.