What is a Log-Structured Merge (LSM) Tree?
Learn what an LSM-tree is, how memtables and SSTables work, why writes are fast, and how compaction bounds reads and space.
Expected Interview Answer
A log-structured merge (LSM) tree is a write-optimized storage data structure that buffers writes in an in-memory sorted table and periodically flushes them as immutable sorted files on disk, then merges those files together in the background so writes are always sequential and fast, at the cost of reads sometimes needing to check multiple files.
Writes first go to an in-memory structure called a memtable (often a skip list or balanced tree, backed by a write-ahead log for durability), which keeps keys sorted and lets writes complete with a fast in-memory insert plus a sequential log append rather than a random disk write. When the memtable fills up, it is flushed to disk as an immutable, sorted string table (SSTable). Over time many SSTables accumulate, so a background compaction process merges them, discarding obsolete overwritten values and deletion tombstones, and keeping the number of files a given key could be scattered across bounded. Reads must check the memtable and potentially multiple SSTables (mitigated by bloom filters and sparse indexes), which is why LSM-trees trade some read amplification and space amplification for excellent, sequential write throughput — the opposite trade-off profile from a B-tree. Real systems built on this design include RocksDB, LevelDB, Cassandra, and HBase.
- Converts random writes into sequential disk I/O, giving very high write throughput
- Immutable SSTables simplify concurrency, crash recovery, and backups
- Compaction bounds file count and reclaims space from overwritten/deleted data
- Well suited for write-heavy workloads like logging, time-series, and event ingestion
AI Mentor Explanation
An LSM-tree is like a scorer who jots every ball down instantly on a quick scratch pad (the memtable) instead of stopping to update the master scorebook after every delivery, which would be far too slow. Once the scratch pad fills up for an over, it is copied out as a neat, sorted sheet (an SSTable) and a fresh scratch pad starts. Periodically, several sorted sheets from past overs are merged together into a bigger, cleaner sheet, discarding any corrections that got overwritten. Looking up a batter’s current score means checking the scratch pad plus a few recent sheets — fast to record, but a lookup may need a few checks.
Step-by-Step Explanation
Step 1
Write to the memtable and WAL
A write is appended to a durable write-ahead log and inserted into an in-memory sorted structure, both fast sequential/O(log n) operations.
Step 2
Flush to an immutable SSTable
When the memtable reaches a size threshold, it is written to disk as a sorted, immutable file, and a fresh memtable takes over writes.
Step 3
Reads check memtable then SSTables
A lookup checks the memtable first, then relevant SSTables (pruned via bloom filters and sparse indexes) from newest to oldest.
Step 4
Background compaction merges files
Compaction merges SSTables, discarding obsolete overwritten values and expired tombstones, bounding file count and reclaiming space.
What Interviewer Expects
- Explains the memtable + WAL + immutable SSTable pipeline
- Explains why writes are sequential and fast (append-only, no in-place random writes)
- Describes compaction and its role in bounding read/space amplification
- Names real systems: RocksDB, LevelDB, Cassandra, HBase, and contrasts with B-tree read/write trade-offs
Common Mistakes
- Describing an LSM-tree as if it were a literal balanced tree data structure on disk
- Forgetting the write-ahead log and thus missing how durability is guaranteed before a memtable flush
- Not mentioning compaction, or assuming SSTables are ever mutated in place
- Failing to name the write-vs-read trade-off compared to B-trees
Best Answer (HR Friendly)
“An LSM-tree is a way databases store data that makes writes very fast by buffering them in memory first and writing to disk in big, sequential chunks instead of scattered updates. In the background, it periodically cleans up and merges those chunks so lookups stay reasonably fast, which is why it is popular for write-heavy systems like logging and time-series data.”
Code Example
class LSMTree:
def __init__(self, memtable_limit=1000):
self.memtable = {} # sorted structure in a real engine (e.g. skip list)
self.wal = [] # write-ahead log for durability
self.sstables = [] # newest-first list of immutable on-disk tables
self.memtable_limit = memtable_limit
def put(self, key, value):
self.wal.append((key, value)) # durable, sequential append
self.memtable[key] = value # fast in-memory insert
if len(self.memtable) >= self.memtable_limit:
self._flush()
def _flush(self):
sorted_items = sorted(self.memtable.items())
self.sstables.insert(0, SSTable(sorted_items)) # newest first
self.memtable.clear()
self.wal.clear()
def get(self, key):
if key in self.memtable:
return self.memtable[key]
for sstable in self.sstables: # newest to oldest
if sstable.bloom_filter.might_contain(key):
value = sstable.lookup(key)
if value is not None:
return value
return NoneFollow-up Questions
- Why does an LSM-tree convert random writes into sequential I/O, and why does that matter on both SSDs and HDDs?
- How does size-tiered compaction differ from leveled compaction in terms of amplification trade-offs?
- What role does the write-ahead log play if the process crashes before a memtable flush?
- How do bloom filters and sparse indexes work together to speed up SSTable lookups?
MCQ Practice
1. Where does a write first land in an LSM-tree before ever touching an SSTable?
Writes go into the in-memory memtable and a durable write-ahead log first; SSTables are only created when the memtable is flushed.
2. What is the primary purpose of compaction in an LSM-tree?
Compaction merges immutable SSTables together, removing stale versions and tombstones, which controls read and space amplification.
3. Which of these databases/engines is built on the LSM-tree design?
RocksDB (and LevelDB, Cassandra, HBase) are classic LSM-tree based storage engines; InnoDB and typical Postgres heap storage are B-tree based.
Flash Cards
What is an LSM-tree? — A write-optimized structure that buffers writes in memory (memtable) and flushes sorted immutable files (SSTables) merged by background compaction.
Why are LSM-tree writes fast? — Writes are sequential appends to a log and an in-memory structure, never random in-place disk writes.
What is a memtable? — The in-memory sorted buffer that holds recent writes before they are flushed to disk as an SSTable.
Name two real LSM-tree based systems. — RocksDB and Cassandra (also LevelDB and HBase).