What is a B+ Tree and Why Do Databases Use It?
Learn what a B+ tree is, why leaves are linked, and why databases use it for indexing — with a full interview-ready explanation.
Expected Interview Answer
A B+ tree is a self-balancing, multi-way search tree where all actual data (or record pointers) lives only in the leaf nodes, internal nodes hold only routing keys, and leaves are linked together in a chain, making it the standard on-disk index structure for databases and file systems.
Because each node can hold many keys (not just two like a binary tree), a B+ tree stays extremely shallow even with millions of records, which minimizes the number of disk or SSD page reads needed to find a value — each node is sized to match a disk block. Internal nodes act purely as a routing map to guide the search down to the correct leaf; the actual data only lives at the leaf level, unlike a B-tree where data can live in internal nodes too. The linked list connecting leaves left-to-right is what makes range queries (e.g. WHERE age BETWEEN 20 AND 30) fast, since once you reach the first matching leaf you just walk the chain instead of re-searching the tree. This combination of shallow height, disk-block-aligned nodes, and linked leaves is exactly why MySQL InnoDB, PostgreSQL, and most filesystems use B+ trees for their primary indexes.
- Very shallow tree minimizes disk I/O per lookup
- Linked leaves make range queries fast
- Node size matches disk/page size for efficient reads
- All data lives in leaves, simplifying range scans
AI Mentor Explanation
A B+ tree is like a stadium's multi-level directory system: the top-level signboard doesn't seat anyone, it just routes you toward a stand; the stand-level signboard routes you further to a specific block; only the seat-row level actually has your seat. Each signboard lists many options at once, not just two, so you reach your seat in only a few glances even in a stadium with a hundred thousand seats. All the seat rows are also connected by a walkway running along the back, so if you're looking for every seat in your price range, you just walk that connecting corridor instead of climbing back up to the signboards each time. This is exactly how a B+ tree keeps lookups shallow and range queries — like scanning ticket price bands — fast.
Step-by-Step Explanation
Step 1
Internal nodes route only
Each internal node holds many keys and child pointers, acting purely as a signpost — it stores no actual data.
Step 2
Leaves hold all the data
Every record or record pointer lives only at the leaf level, all leaves at the same depth for guaranteed O(log n) access.
Step 3
Leaves are linked
Leaf nodes form a linked list left to right, so once a search reaches the starting leaf, range scans just walk the chain.
Step 4
Node size matches disk pages
Each node is sized to one disk/SSD block, so each tree level traversed costs exactly one I/O — this is why the tree fans out wide instead of staying binary.
What Interviewer Expects
- Explain internal nodes are routing-only, data lives in leaves
- Explain why leaves are linked (fast range queries)
- Connect node size to disk page size and I/O minimization
- Compare briefly to a B-tree (which stores data in internal nodes too)
Common Mistakes
- Confusing a B+ tree with a binary search tree (it is multi-way, not binary)
- Forgetting leaves are linked, missing why range queries are fast
- Claiming a B-tree and B+ tree are identical
- Not connecting node fan-out to minimizing disk I/O
Best Answer (HR Friendly)
“A B+ tree is the data structure most databases use to index data on disk. It stays very shallow even with millions of rows because each node can point to many children at once, and all the actual data sits in the bottom leaf level, which are linked together so range queries like 'find everything between these two dates' are fast.”
Code Example
class BPlusLeaf:
def __init__(self, order):
self.order = order
self.keys = []
self.values = []
self.next_leaf = None # linked-list pointer for range scans
def range_scan(self, start_key, end_key):
result = []
leaf = self
while leaf:
for k, v in zip(leaf.keys, leaf.values):
if start_key <= k <= end_key:
result.append((k, v))
if k > end_key:
return result
leaf = leaf.next_leaf # walk the chain, no re-searching the tree
return resultFollow-up Questions
- How does a B+ tree differ from a plain B-tree?
- Why do databases size B+ tree nodes to match disk page size?
- How does a B+ tree handle node splits and merges on insert/delete?
- Why is a B+ tree preferred over a hash index for range queries?
MCQ Practice
1. Where does actual data live in a B+ tree?
B+ tree internal nodes hold only routing keys; all actual data or record pointers live in the leaf nodes.
2. Why are B+ tree leaf nodes linked together?
The linked leaf chain lets range scans move sequentially once the starting leaf is found, avoiding repeated tree traversal.
3. Why are B+ tree nodes typically sized to match a disk page?
Aligning node size with disk block size means each level traversed during search corresponds to one I/O operation, minimizing disk reads.
Flash Cards
Where does actual data live in a B+ tree? — Only in the leaf nodes; internal nodes hold routing keys only.
Why are B+ tree leaves linked in a chain? — To make range queries fast — walk the chain instead of re-searching the tree.
Why is a B+ tree node sized to match a disk page? — So each level traversed costs exactly one disk/SSD I/O operation.
Name two systems that use B+ trees as their primary index. — MySQL InnoDB and PostgreSQL (also most filesystems).