Databases & Storage · advanced
LSM Tree
Log-structured merge tree: write-optimized storage via sorted runs.
Mental model
An LSM tree turns random writes into sequential ones: buffer writes in an in-memory memtable, flush to immutable sorted files (SSTables), and merge them in the background. Writes are fast; reads may touch several files (bloom filters help).
How to study LSM Tree
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use RocksDB Wiki — LSM overview to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare LSM Tree with B-Tree, Compaction. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Build a memtable + SSTable flush and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Where it matters
RocksDB, Cassandra, LevelDB, ScyllaDB; the write-heavy storage engine.
Common mistakes
- Ignoring read amplification across SSTable levels
- No bloom filters, so every read scans every file
- Forgetting that deletes are tombstones, not removals
Learn from primary sources
Practice and explain it back
Build a memtable + SSTable flush
Implement an in-memory memtable that flushes to an immutable sorted file (SSTable). Support reads that merge memtable and SSTables; deletes as tombstones.
Expected evidence: Writes go to the memtable; reads see the latest value across files.
Open the interactive drill →Review prompts
- When would you choose an LSM tree over a B-tree?
- Why can reads be slow in an LSM tree, and what helps?
Build evidence
Toy LSM tree
A minimal LSM storage engine: memtable, SSTables, compaction.
- Writes buffered in a memtable and flushed to immutable sorted files
- Reads merge across files; deletes are tombstones
- A simple compaction pass