A B-tree is a self-balancing tree built around one goal: minimize the number of nodes visited between the root and the data being sought, when each node visit might cost a disk or SSD read. Unlike a binary search tree, which allows at most two children per node, a B-tree node can hold many keys and many children at once — which is exactly what keeps it shallow.
What changed in 2026
- B+ trees remain the dominant index structure in mainstream relational databases, and nothing on the horizon looks likely to displace them for general-purpose disk-backed indexing.
- NVMe and faster SSDs have narrowed, but not eliminated, the gap that makes minimizing reads worthwhile — random reads still cost far more than sequential ones.
- In-memory databases increasingly favor other structures (hash tables, skip lists) for pure in-memory workloads, while B-trees stay the default the moment data needs to live on disk.
Why not just use a binary tree
A binary tree holding one million rows needs roughly 20 levels, since log2(1,000,000) is about 20 — and on disk-backed storage, each level can mean a separate read. A B-tree with a branching factor around 200 needs only about 3 levels for the same one million rows, since log200(1,000,000) is about 3. Fewer levels means fewer reads, and reads are the dominant cost for anything not fully cached in memory. A balanced binary tree — even a self-balancing red-black tree or AVL tree — still has exactly two children per node, so no amount of balancing escapes this problem.
How a B-tree node works
A B-tree of order m allows each node up to m - 1 keys and m children. Keys inside a node stay sorted, and the child pointers between them lead to subtrees whose values fall in the corresponding range. The root can hold fewer keys, but every leaf sits at the same depth — a structural guarantee, no separate rebalancing logic needed.
Splitting a node on overflow
When an insert would push a node past m - 1 keys, the node splits into two at its median key, which moves up into the parent. If the parent overflows too, it splits as well, and the process can propagate to the root — how the tree grows in height, always from the root down, keeping every leaf at the same depth.
insert(node, key):
if node is a leaf:
insert key into node in sorted position
if node now has too many keys:
split node, push median key up to parent
else:
child = find_child_for(node, key)
insert(child, key)
if child was split:
insert the median key from child into node
if node now has too many keys:
split node, push median key up to parent
B-tree vs B+ tree vs balanced binary trees
| Property |
Binary search tree (AVL / red-black) |
B-tree / B+ tree |
| Children per node |
2 |
Many (order m) |
| Height for 1 million records |
About 20 levels |
About 3 levels, at order 200 |
| Rebalancing mechanism |
Rotations |
Node splits and merges |
| Optimized for |
In-memory access |
Disk / SSD block reads |
| Typical real-world use |
In-memory ordered containers |
Database indexes, filesystems |
Most production databases actually use a B+ tree: all data lives in the leaf nodes, internal nodes hold only navigation keys, and the leaves are linked together in order. That link is what makes a range query fast — walk the leaf chain instead of re-descending the tree for every value.
Common pitfalls
Assuming a database B-tree index is the pure textbook structure. Most production databases use a B+ tree variant, which changes where the data actually lives.
Picking node size arbitrarily instead of matching the storage page size. The entire benefit of a B-tree comes from one node fitting in one disk or memory page.
Assuming any B-tree index speeds up range queries the same way. The real range-query win comes from the linked leaves in a B+ tree, not from the tree shape alone.
Over-indexing a write-heavy table. Every index adds insert and update overhead, since the tree, and any node splits it triggers, must stay in sync on every write.
FAQ
Is a B-tree the same as a binary search tree?
No — despite the similar name, a B-tree node can have many children, not just two, which is exactly what keeps it shallow for disk-backed data.
What does the order of a B-tree mean?
The maximum number of children a node can have. A node with order m holds at most m - 1 keys and m children.
Why do databases prefer B+ trees over plain B-trees?
B+ trees keep all data in leaf nodes and link the leaves together, which makes range scans fast and keeps internal nodes small enough to stay cached in memory.
Could a database use a red-black tree instead?
Technically yes for a purely in-memory structure, and some in-memory databases do. For anything on disk or SSD, the higher fan-out of a B-tree means far fewer read operations per lookup.
Where to go next