Databases · interactive
LSM trees: fast writes, merged later
B-trees update pages in place. Log-structured merge trees never do: writes land in memory, get flushed as sorted immutable files, and background compaction merges those files. Writes become cheap appends; reads may check several places.
—
Memory
memtable (sorted, max 3)
Disk · L0 (newest first)
none
Disk · L1
none
Empty. Writes go to an in-memory table (the memtable), kept sorted.
Write to memory (and the log)
Each write is added to a sorted in-memory table and appended to a log for crash safety. No random disk I/O.
Great for write-heavy workloads.
Flush to an immutable SSTable
The memtable is written out as a sorted file, never modified again. Updates and deletes are new entries that shadow old ones.
Deletes are tombstones.
Read newest to oldest
Check the memtable, then each file until the key turns up. Bloom filters skip files that definitely don't have it.
Read amplification.
Compaction merges files
Merging sorted files keeps the newest value per key and drops the rest, so reads stay fast and space is reclaimed. It costs extra disk writes.
RocksDB, Cassandra, LevelDB.
In production
Tools and technologies
Most write-heavy databases are built on LSM trees.
Not tied to one language — use these names when you search docs or design a system.