LSM Trees: How to Explain Them in an Interview (2026)

LSM (Log‑Structured Merge) trees are a storage design that turns random writes into sequential ones. Instead of updating data in place, they keep a mutable in‑memory component (often called a memtable) and periodically flush it to disk as an immutable, sorted file (SSTable). Over time many SSTables accumulate, and a background process merges them – the compaction step – to keep read latency reasonable.

One‑Sentence Definition

A Log‑Structured Merge tree is a write‑optimized data structure that buffers updates in memory and periodically merges them into sorted on‑disk files.

How It Works

Write Path

1. Insert into Memtable – The incoming key/value is written to a lock‑free skip list (or similar) in RAM.
2. Write‑Ahead Log (WAL) – The same entry is appended to a sequential log on disk for durability.
3. Flush – When the memtable reaches a size threshold, it is frozen and written out as a sorted string table (SSTable).
4. SSTable Index – A small block index is stored alongside the file to allow range lookups.

Read Path

• A read first checks the memtable.
• If not found, it probes the most recent SSTable, then older ones, using the block index to skip irrelevant sections.
• Compaction reduces the number of SSTables a read must inspect.

Trade‑offs

Why the trade‑offs matter

• Write‑heavy workloads – LSM shines because each write touches only RAM and an append‑only log.
• Read‑heavy workloads – You need aggressive compaction to keep the number of SSTables low; otherwise reads become expensive.
• Range queries – Because data is stored sorted, range scans are efficient once the relevant files are identified.

Concrete Example: RocksDB

RocksDB, a widely used embeddable key‑value store, implements an LSM tree with multiple levels. New data lands in a memtable, is flushed to a Level‑0 SSTable, and then gradually merged down to higher levels. The default leveled compaction keeps each level roughly the same size, limiting the number of files a read must check to about one per level (typically 5‑7 levels). This design gives write throughput of hundreds of thousands of ops/sec while keeping read latency in the low‑single‑digit milliseconds range.

Typical Interview Questions

1. Explain the write path of an LSM tree. – Mention WAL, memtable, flush, SSTable.
2. What is compaction and why is it needed? – Describe merging SSTables to bound read amplification.
3. Compare LSM trees to B‑trees. – Focus on write amplification, read amplification, and space overhead.
4. How does the choice of compaction strategy affect performance? – Discuss size‑tiered vs. leveled, trade‑offs for write vs. read heavy workloads.
5. What happens to a delete operation? – Explain tombstones and their removal during compaction.
6. How would you tune an LSM‑based system for a workload that is 80 % reads? – Suggest larger memtables, aggressive compaction, and possibly a hybrid approach.

60‑Second Spoken Answer

"An LSM tree is a storage structure that makes writes cheap by buffering them in memory and then flushing them to disk as sorted files. When a write arrives, we append it to a write‑ahead log for durability and insert it into a memtable – typically a skip list. Once the memtable fills, we write it out as an immutable SSTable. Reads start at the memtable, then check the newest SSTable, and continue backward until they find the key. Because many SSTables can pile up, a background compaction merges them, keeping read latency low. The main trade‑off is that writes are fast but reads can suffer if compaction lags. In practice, systems like RocksDB use leveled compaction to keep the number of files per read small, balancing write throughput with acceptable read latency."

How to Practice This

1. Write the answer on paper – Keep it under 90 seconds, then time yourself.
2. Use Call Assistant to rehearse – Record yourself, let the tool surface follow‑up prompts, and refine the story until it flows naturally.
3. Create a mini‑project – Install RocksDB, insert a few keys, and observe the memtable flush and compaction logs. Explain each step out loud as if you were interviewing.

---

FAQ

• Q: When should I choose an LSM tree over a B‑tree? A: Opt for LSM when your workload is write‑heavy or you need high ingest rates. B‑trees are better for read‑dominant workloads with low latency requirements.
• Q: What is a tombstone in an LSM tree? A: A tombstone is a marker for a deleted key. It lives in the memtable and later SSTables until a compaction removes it.
• Q: How does size‑tiered compaction differ from leveled compaction? A: Size‑tiered merges files of similar size in batches, favoring write throughput. Leveled keeps each level a fixed size, reducing read amplification at the cost of more write work.
• Q: Can an LSM tree be used for relational data? A: It’s primarily a key‑value engine, but some relational systems layer an LSM store underneath to gain write performance, handling relational semantics at a higher layer.