Advanced · Module 20 · Lesson 4 of 5
B-trees and pages
A B-tree stores hundreds of keys per node, sized to fit one disk page or a few cache lines, so a tree of billions of keys is only three or four levels tall. Nodes split as they fill, and the tree grows at the root, keeping every leaf at the same depth.
By the end you can
- Explain why storage layers count page reads, not comparisons, and how wide nodes reduce them
- Insert into a B-tree, splitting full nodes and growing at the root
- Describe B+ trees, their linked leaves and range scans, and why databases use them
Builds on Red-black trees, Caches: why neighbors are fast.
01 · A question first
A database table holds a billion rows, and a lookup by id returns in well under a millisecond, even though reading from disk takes far longer than a comparison. A balanced binary tree over a billion keys has thirty levels, each potentially a separate disk read. How does a database find a row with three or four?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Counting the right thing
- Wide nodes
- Insertion: split and push up
- B+ trees and range scans
- Not only for disks
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem