B+ Tree
The balanced, disk-page-based structure Postgres, InnoDB, and SQLite use to keep both lookups and range scans fast.
Overview
A B+ Tree is the balanced, disk-page-based tree structure that most traditional relational engines — Postgres, MySQL/InnoDB, SQLite, Oracle — use to store table and index data on disk, organized specifically to make both single-row lookups and range scans fast with a small, predictable number of disk reads.
Why It Exists
A plain binary search tree gets too deep for disk-backed storage — every level down is a separate disk read, and disk reads are exactly the expensive step covered back in the storage latency ladder. B+ Trees exist to keep the tree extremely wide and shallow, so even a table with millions of rows can be reached in only 3-4 levels, and they store real data only in leaf nodes, linked together in order, so a range scan can walk sequentially instead of re-traversing the tree for every row.
Real World Example
Looking up a user by `id` in a Postgres table with an index on `id`: the engine starts at the root page, reads that page's keys to decide which child page to follow, repeats that two or three more times, and lands on a leaf page holding the actual row. That's 3-4 disk reads total — even with a million rows — because each internal page can hold hundreds of keys, keeping the tree's fan-out high and its depth low.
Example Data
Why fan-out keeps a B+ Tree shallow — depth needed to reach 1,000,000 rows
| Fan-out per page | Tree depth needed |
|---|---|
| 2 (like a binary tree) | ~20 levels |
| 300 (a typical B+ Tree page) | ~4 levels |
How a B+ Tree Is Structured
Root, Internal Nodes, and Leaf Nodes
The root and internal nodes hold only keys and pointers to child pages, used purely for navigation. Leaf nodes hold the actual data (or a pointer to the row) — a plain B-Tree, by contrast, stores data in internal nodes too, which is the real distinction between the two.
High Fan-Out Keeps It Shallow
Each page can hold hundreds of keys, so the tree branches wide instead of deep. A million-row table needs only about 3-4 levels, meaning a lookup costs only 3-4 disk reads regardless of how large the table grows.
Leaf Nodes Are Linked for Range Scans
Every leaf node points to the next one in sorted order. A range query (`WHERE id BETWEEN 100 AND 200`) finds the starting leaf once, then walks forward along that linked list — no need to re-traverse the tree from the root for each row.
In-Place Updates
An update modifies the existing page directly. If a page fills up, it splits into two, which costs extra I/O and can fragment the tree slightly over time — the direct trade-off the next chapter's LSM Tree design makes differently.
Diagram
High fan-out keeps the tree shallow — a lookup walks root to leaf in a handful of steps
Root page
keys only, points to internal pages
Internal pages
keys only, point to leaf pages
Leaf pages
actual row data, linked in sorted order
Common Mistakes
Assuming a B+ Tree index always makes a range query fast
Why: A range covering a large fraction of the table can actually be slower via the index than a full sequential scan, since jumping between many scattered leaf pages can cost more than one sequential read of the whole table.
Fix: Check the actual query plan (EXPLAIN) and let the planner decide — don't assume an index is always the faster path for every range size.
Confusing a plain B-Tree with a B+ Tree
Why: A B-Tree stores data in internal nodes as well as leaves; a B+ Tree stores data only in leaves, with internal nodes used purely for navigation — this is exactly what makes linking leaf nodes for sequential range scans work cleanly.
Fix: Know that most real 'B-Tree indexes' in relational databases are actually B+ Trees — check your specific engine's documentation rather than assuming.
Assuming in-place updates in a B+ Tree are free
Why: A page that fills up has to split, which costs extra I/O and can fragment the tree over time — this isn't free, it's a specific trade-off B+ Trees make in exchange for simple, predictable reads.
Fix: Understand this trade-off explicitly before comparing a B+ Tree engine against an append-only alternative like an LSM Tree for a write-heavy workload.
Interview Questions
Why do disk-based databases use a B+ Tree instead of a plain binary search tree?
A binary search tree gets too deep for a table with millions of rows, and every level down means a separate, expensive disk read. A B+ Tree keeps very high fan-out per page, so the tree stays shallow — a few levels reach any row, even in a huge table.
What's the actual difference between a B-Tree and a B+ Tree?
A B-Tree stores data in both internal and leaf nodes. A B+ Tree stores data only in leaf nodes, with internal nodes holding just keys for navigation — and its leaf nodes are linked together in sorted order, which is what makes range scans efficient without re-traversing the tree.
A range query scanning 40% of a large indexed table performs worse using the index than a full table scan would. Why?
At that selectivity, the query has to jump between a large number of leaf pages that may not be physically adjacent on disk, which can cost more total I/O than reading the entire table sequentially in physical order. The query planner's cost-based decision to prefer a sequential scan past a certain selectivity threshold is exactly this trade-off — it isn't a bug, it's the correct call once an index stops being selective enough to pay for itself.
Production Best Practices
Do
✓Trust the query planner's choice between an index scan and a sequential scan — verify with EXPLAIN rather than forcing one.
✓Keep indexed columns' values reasonably sized — very large indexed values reduce a page's effective fan-out.
✓Understand page splits as a real write-time cost when evaluating B+ Tree write performance.
Don't
✗Don't assume an index is always faster than a full scan for every query shape.
✗Don't confuse a B-Tree's structure with a B+ Tree's — they store data differently.
✗Don't treat in-place updates as a free operation — page splits have a real I/O cost.
Comparison
| Typical Depth (1M rows) | Disk Reads per Lookup | Optimized For | |
|---|---|---|---|
| Balanced Binary Tree (in-memory) | ~20 levels | N/A — no disk involved | In-memory lookups |
| B+ Tree (disk-based) | ~4 levels | 3-4 | Point lookups and range scans on disk |