LSM tree and sorted string tables

In short: An LSM tree collects writes in memory first and writes them to disk in bundles and sorted. That makes writing very fast; reading takes more work.

In more detail: New data lands in a memtable (sorted in RAM) and in the write-ahead log. When the memtable is full it is saved as an immutable sorted file (SSTable). In the background compaction merges many small files into larger ones and removes outdated values.

In Depth

• Reading: First memtable, then SSTables from new to old. Bloom filters save unnecessary disk accesses.
• Deleting: Written as a marker (tombstone) and removed during compaction.
• Compaction: Trade-off between write, read and space amplification.
• Strategies: Size-tiered (cheap writes) and leveled (cheap reads).
• Use: RocksDB, LevelDB, Cassandra, HBase.
• Counterpart: B-tree, better for reads and range queries with less write amplification for small updates.

See also: B-tree and B+ tree, Write-ahead log and recovery