LSM trees

A log-structured merge tree, or LSM tree, is a storage design that makes writes fast by never updating data in place on disk. New writes go into a sorted table in memory (plus a log for crash safety). When that fills up, it’s written to disk in one go as an immutable sorted file. Over time, background compaction merges these files into larger ones and throws away overwritten or deleted values. Reads may need to check several files, so each file keeps an index and usually a Bloom filter to skip files that can’t contain the key. The trade is cheap writes for more expensive reads, and it underpins RocksDB, Cassandra and many other write-heavy databases.