How Does an LSM Tree Store Data? Explainer
A log-structured merge tree, or LSM tree, is a storage design that turns many small database updates into larger sequential writes. Updating a traditional disk index in place can force the drive to visit many separate locations. An LSM-based engine first records the change in a write-ahead log for recovery and inserts the key and value into an in-memory sorted structure called a memtable. The application can receive an acknowledgment after the durability requirement is met without waiting for the main on-disk index to be reorganized for every individual write.
When the memtable reaches a limit, the engine freezes it and flushes its sorted contents to an immutable on-disk file, often called an SST file or sorted-string table. New writes continue in a fresh memtable. Each SST file contains keys in order and usually includes an index plus checksums. Because the flush is written as a sequential run, storage devices can handle it efficiently. Deleting or replacing a key does not immediately change every older file. A deletion is represented by a tombstone, and a newer value simply takes precedence over older versions during lookup.
Reads must check more than one place. The engine looks in the active memtable, any immutable memtables waiting to flush, and the relevant SST files from newest to oldest until it finds the latest version or a tombstone. File indexes narrow the search, while Bloom filters can quickly show that a file definitely does not contain a requested key. Recently used blocks may stay in a cache. These techniques keep point lookups practical, but an LSM tree usually has more read amplification than a structure that maintains one in-place search tree.
Background compaction keeps the growing collection of files under control. It selects sorted runs, merges them, discards overwritten values and obsolete tombstones when safe, and writes new SST files. Leveled compaction keeps a limited number of nonoverlapping runs in progressively larger levels, which helps reads and space use but can rewrite data many times. Tiered or universal compaction waits and merges similarly sized runs, often reducing write amplification at the cost of more files to search and more temporary space. Real engines tune level sizes, file sizes, triggers, concurrency, and throttling around their workload and storage hardware.
The design therefore moves cost rather than removing it. Fast ingestion can create a compaction backlog, and heavy compaction may compete with foreground reads and writes for bandwidth and CPU. Tombstones may remain until they reach all relevant older data, so deleting a key does not instantly recover space. Databases using LSM trees monitor write stalls, read amplification, write amplification, space amplification, cache efficiency, and compaction debt. When tuned well, the approach is a strong fit for key-value stores, event streams, time-series data, and other workloads that receive sustained writes: it batches disorder in memory, writes sorted runs efficiently, and restores a searchable structure through controlled merging.
An LSM tree buffers updates in memory, flushes sorted immutable files, and merges those files through compaction. Key terms include write-ahead log, memtable, SST file, level, compaction, tombstone, Bloom filter, write amplification, read amplification, and space amplification.
The engine records the update in a recovery log and places it in the memtable. A full memtable is flushed as a sorted SST file. A newer value overrides older versions, while a deletion creates a tombstone that remains until compaction can safely discard the older value.
Without compaction, every flush would add another file for reads to search and obsolete versions would consume space indefinitely. Compaction merges sorted runs, removes superseded data, and organizes files for efficient lookup. The tradeoff is extra background I/O and potential write amplification.
Explore more "Explainers"
Discover additional explainers across politics, science, business, technology, and other fields. Each explainer breaks down a complex idea into clear, everyday language—helping you better understand how major concepts, systems, and debates shape the world around us.
