LSMTrees

A log-structured merge-tree (LSM-tree) is a data structure and storage architecture designed to optimize write-heavy workloads by buffering writes in memory and writing them to disk in large, sequential batches. It supports efficient range queries and updates, and is widely used in modern NoSQL databases.

In an LSM-tree, incoming writes first go to an in-memory structure called a memtable, and are also logged to a write-ahead log to provide durability. When the memtable fills, it is flushed to disk as an immutable sorted file called an SSTable (sorted string table). The on-disk SSTables are organized into levels, forming a hierarchical structure. New SSTables are created at the top level and gradually merged into lower levels through a process known as compaction.

Compaction is central to LSM-tree maintenance. It merges overlapping key ranges from smaller SSTables and rewrites them into larger SSTables at the next level, removing deleted or superseded entries along the way. There are two common compaction strategies: leveled and tiered. Leveled design maintains non-overlapping ranges within each level to bound read amplification, while tiered design allows more overlapping SSTables per level, often increasing write throughput at the expense of read efficiency. Each SSTable typically carries an in-memory index and a Bloom filter to speed up lookups and skip unnecessary disk reads.

Read operations consult the memtable first and, if not found, search SSTables across levels, often using Bloom filters to avoid disk access. Writes are sequential and append-only, contributing to high write throughput but potentially higher read amplification and compaction overhead.

LSM-trees underpin several well-known databases, including LevelDB and RocksDB, and are used by Cassandra and HBase. They offer strong write performance and good performance for certain read patterns, with trade-offs in read amplification and maintenance complexity. The original concept was introduced by O’Neil, Cheng, and Seltzer in 1996.