Databases & Storage · core
B-Tree
The balanced, disk-friendly tree behind most relational indexes.
Mental model
A B-tree is a wide, shallow tree sized to disk pages: each node holds many keys so the tree stays ~3-4 levels deep even for billions of rows. Reads are fast and in-place; writes do random page updates.
How to study B-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 CMU 15-445 — Tree indexes to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare B-Tree with LSM Tree, Secondary Indexes, Storage Engines. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete B-tree page split 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
PostgreSQL, MySQL/InnoDB, SQLite — the default index.
Common mistakes
- Confusing B-tree (in-place, read-optimized) with LSM (append, write-optimized)
- Ignoring page splits and write amplification
- Forgetting that B-trees keep keys sorted, enabling range scans
Learn from primary sources
Practice and explain it back
B-tree page split
Page holds 4 keys, insert 5th triggers split. After split how many keys in each page (order 5)?
Expected evidence: 2 keys in left, 2 in right, median promoted.
Open the interactive drill →Review prompts
- When would you choose an LSM tree over a B-tree?
- Why are B-tree nodes sized to disk pages?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.
Prerequisites
None assigned yet.