Storage Engines — How B-tree & LSM-tree Work
The layer beneath “SQL vs NoSQL”
Below the data model sits the storage engine — how bytes hit disk. Two designs: the B-tree (read-optimised, update-in-place) and the LSM-tree (write-optimised, append-only).
How a B-tree works
A node is a sorted box of keys with child pointers between them. To find a key you descend, following the gap it falls into — O(log n). Trace a search for 23:
Key insight: each node is one disk page (~hundreds of keys), so each level = one page read; a shallow wide tree finds any row in ~4 reads. Inserting: drop the key in the right leaf; if the leaf overflows its page it splits, pushing its middle key up (possibly splitting the parent — that's how the tree grows and stays balanced).
insert 1,2 → [1|2]; insert 3 → overflow → split, push 2 up: [2]
/ \
[1] [3]
Cost: write amplification (rewrite whole pages + WAL), random I/O. Used by Postgres, MySQL/InnoDB.
How an LSM-tree works
Writes go to an in-memory memtable (instant, sequential), flushed to immutable sorted SSTable files; a background compaction merges them and drops superseded keys.
write → [memtable in RAM] --flush--> [SSTable][SSTable] --compaction--> [merged SSTable]
Reads check newest→oldest; each SSTable carries a Bloom filter to skip files that definitely lack the key (read amplification, mitigated). Cheap sequential writes; pays in read + compaction cost. Used by Cassandra, RocksDB, ScyllaDB.
| B-tree | LSM-tree | |
|---|---|---|
| Writes | In-place, random | Sequential append — fast |
| Reads | One tree walk | Several SSTables (Bloom-filtered) |
| Pays in | Write amplification | Read amp + compaction |
| Best for | Read/scan-heavy, transactions | Write/ingest-heavy |
Takeaways
- B-tree: shallow wide tree of disk-page nodes; search in ~log n reads; splits to stay balanced.
- LSM: buffer in RAM → immutable SSTables → compact; reads lean on Bloom filters.
- Read-heavy → B-tree; write-heavy → LSM.
Re-authored from-scratch; diagram hand-authored (SVG) for this guide.
🤖 Don't fully get this? Learn it with Claude
Stuck on Storage Engines — How B-tree & LSM-tree Work? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Build the mental picture, not memorization.
I just read a lesson on **Storage Engines — How B-tree & LSM-tree Work** (System Design) and want to truly understand it. Explain Storage Engines — How B-tree & LSM-tree Work from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Socratic — adapts to where you're stuck.
Teach me **Storage Engines — How B-tree & LSM-tree Work** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Active recall exposes what you missed.
Quiz me on **Storage Engines — How B-tree & LSM-tree Work** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Intuition + hook + flashcards for long-term memory.
Help me remember **Storage Engines — How B-tree & LSM-tree Work** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.