LSM Tree

A log-structured merge tree collects writes in memory and flushes sorted immutable files. In RocksDB, the in-memory structure is a memtable and the files are SSTables. WAL and synchronization settings determine which acknowledged writes can survive a failure; an in-memory update alone is not durable.

A read may need to consult the memtable and candidate files to find the newest visible value. Key ranges and Bloom filters can avoid unnecessary file searches. A negative Bloom-filter result can rule out membership; a positive result still requires checking because false positives are possible.

Compaction merges files, removes obsolete versions when safe, and reorganizes future reads. It also rewrites data, creating write amplification and using CPU and I/O. Deletes usually leave tombstones until older values can safely be discarded. Long-lived snapshots or retention requirements can delay removal. LSM designs trade read, write, and space costs; they are not universally faster than B-trees, and row-versus-column layout is a separate choice.

Reference: Official documentation. See the worked examples in Relational Database Internals.