Every CREATE INDEX you've ever run in Postgres, MySQL, or SQL Server built a B-tree — and despite the name, it has almost nothing in common with the binary search tree in Binary Search Tree Visualizer. A BST is optimized to minimize comparisons. A B-tree is optimized to minimize disk reads — a completely different bottleneck, and it produces a structure that barely looks like a tree at all next to a BST: wide instead of deep, with hundreds of keys per node instead of one.
The bottleneck a BST doesn't account for
A balanced binary search tree holding a million rows has a height around log₂(1,000,000) ≈ 20 — about 20 comparisons to find any row, each one potentially following a pointer to a completely different, effectively random location in memory. That's fine when the whole structure lives in RAM. It falls apart the moment the data lives on disk, because each of those 20 pointer-chases can mean a separate, random disk read — and a random disk read costs orders of magnitude more time than an in-memory comparison, whether that disk is spinning or solid-state. Twenty of those per lookup is the exact problem a B-tree exists to avoid.
The fix is blunt and effective: instead of one key per node, pack in hundreds — as many as fit in a single disk page (commonly 4–16 KB) — so each disk read buys you hundreds of branching choices instead of two. With a branching factor of 200, that same million rows needs a height of only log₂₀₀(1,000,000) ≈ 3. Same data, roughly 3 disk reads instead of 20 — the entire reason B-trees exist.
The exact definition
A B-tree is defined by a single number, its minimum degree t (t ≥ 2), and every structural rule follows from it:
- Every node holds between
t − 1and2t − 1keys, sorted — except the root, which is allowed as few as 1. - A non-leaf node with
kkeys has exactlyk + 1children — one more child than keys, since each key sits between two child pointers, and every key in the subtree to its left is smaller, every key to its right is larger. This is the same ordering invariant a BST has, just with many keys per node instead of one. - Every leaf sits at exactly the same depth. This is the property that actually matters, and it's not something checked and corrected after the fact — it's a structural guarantee of how insertion works, covered next.
Insertion: how it stays balanced without ever rebalancing
An AVL or red-black tree stays balanced by detecting an imbalance after an insert and fixing it with rotations. A B-tree never needs that separate correction step, because of how a node overflow is handled:
- Insert the new key into the correct leaf's sorted list of keys.
- If that leaf now holds
2tkeys — one too many — split it at the median key into two nodes, and push that median key up into the parent as a new separator. - If the parent now overflows too, split it the same way, recursively, potentially all the way up to the root.
- If the root itself splits, a brand-new root is created holding just that one surviving median key, with the two split halves as its only two children.
That last step is the entire mechanism: a B-tree only ever grows taller by splitting the root and adding a new one above it — which means growth always happens at the top, evenly, never from an individual leaf pushing downward the way an unbalanced BST degrades. Every leaf staying at the same depth isn't a rule the tree has to enforce separately; it can't be violated by how insertion is defined. Compare this directly against Binary Search Tree Visualizer: insert 1 through 10 in order there and the tree degrades to a height of 9, because a plain BST has no mechanism at all — corrective or structural — stopping that.
B-tree vs. B+ tree — the variant that actually runs your database
Almost no production database uses a literal B-tree. They use a B+ tree, a variant with one specific change: internal nodes hold only keys, used purely to route a search toward the right leaf — every actual value lives in a leaf, and only in a leaf. Two consequences fall out of that one change:
- Internal nodes, freed from also storing data, pack in even more keys per page — increasing the branching factor further and shrinking the tree's height for the same dataset.
- Leaves are additionally linked together in a doubly-linked list. A range query —
WHERE price BETWEEN 10 AND 50— finds the first matching leaf once, the normal B-tree-style descent, and then simply walks the linked list of leaves instead of re-descending the tree for every row in range.
Both PostgreSQL's btree index type and MySQL InnoDB's indexes are genuinely B+ trees under that shared name — Postgres links its leaf pages exactly this way (documented as the Lehman & Yao B-tree algorithm, chosen specifically to allow concurrent access during a split), and InnoDB's documentation describes the same leaf-linking directly. InnoDB adds one more wrinkle worth knowing: its clustered index (built on the primary key) stores full row data in its leaves, but a secondary index's leaves store only the primary key value — matching a secondary index still costs a second lookup into the clustered index to get the actual row, a detail sometimes called a bookmark lookup.
Deletion, briefly
Deletion is insertion's mirror image: removing a key can leave a node under the t − 1 minimum, and the fix is either borrowing a key from an adjacent sibling that has one to spare (rotating a key through the parent, the reverse of a split's push-up), or, if no sibling has one to spare, merging two nodes and pulling the separating key down from the parent — the reverse of a split. Merging can itself underflow the parent, cascading upward exactly like a split can, all the way to shrinking the root by one level if necessary.
B-tree vs. binary search tree, side by side
| Binary search tree | B-tree | |
|---|---|---|
| Keys per node | Exactly 1 | t − 1 to 2t − 1 (often hundreds) |
| Children per node | At most 2 | t to 2t |
| Self-balancing? | Not on its own — needs AVL/red-black rotations, or nothing at all | Yes — structurally guaranteed by how insert/split works |
| Optimized for | In-memory comparisons | Minimizing disk/page reads |
| Height for 1M keys | ~20 if balanced, up to 1,000,000 if degenerate | ~3 with a realistic branching factor |
Try it yourself
Binary Search Tree Visualizer shows the exact degenerate-height problem B-trees are structurally immune to — insert values in sorted order and watch the height climb unchecked. SQL Index Advisor puts the concept to work directly: its column-ordering recommendations exist specifically because of the B-tree limitations covered above — a standard B-tree index can satisfy any number of leading equality conditions efficiently, but only one range condition, and only if it comes last.
FAQ
What does the "B" in B-tree actually stand for?
Nobody knows for certain — Bayer and McCreight, who invented it in 1970 while working at Boeing, never definitively said. Candidates people have proposed include Boeing, balanced, broad, bushy, and Bayer himself; McCreight has since suggested Boeing was at least part of the reason, but the ambiguity was reportedly deliberate from the start.
If B-trees are so much shallower, why does anything still use a binary search tree?
Because the problem B-trees solve — minimizing disk reads — doesn't apply to data that already lives entirely in memory. A pure in-memory ordered map (C++'s std::map, Java's TreeMap) reaches every node through a cache-resident pointer instead of a disk seek, so the per-node overhead of a wide B-tree node buys nothing there — a simpler, leaner structure like a red-black tree wins instead.
Is "order" the same as "minimum degree"?
They describe the same idea but aren't interchangeable numbers — different textbooks define a B-tree of "order m" slightly differently (sometimes m children max, sometimes m keys max), which is exactly why this post uses CLRS's minimum-degree-t definition throughout instead — it avoids that ambiguity by defining everything in terms of one consistent bound.