B-Trees and B+ Trees
B-Trees are self-balancing search trees that store multiple keys per node, minimizing disk I/O for massive database indexes.
Built for the Disk, Not the CPU
A balanced binary search tree of a million keys is about 20 levels deep, and 20 comparisons in memory is nothing. But if each node lives on disk, those 20 levels become 20 disk reads — and that changes the problem entirely.
The numbers are stark. A memory access takes roughly 100 nanoseconds; a random read from a spinning disk takes about 10 milliseconds, some 100,000 times slower. Even an SSD is around 100 microseconds, still a thousandfold gap. When data lives on storage, the number of block reads is the only cost that matters and comparison counts are irrelevant.
Storage devices also cannot read a single byte. They transfer a whole block — typically 4 KB to 16 KB — so reading one key from a node costs exactly the same as reading five hundred. A binary tree node holding one key wastes almost the entire transfer.
A B-tree is the structure that takes this seriously. Rather than two children per node, each node holds many keys and many children, sized so that one node fills one disk block. Since each read now brings back hundreds of keys, far fewer reads are needed to reach any record.
The result is a tree that is wide and shallow. Where the binary tree needed 20 levels for a million keys, a B-tree with 100 keys per node needs 3 — because 100³ is already a million. The branching factor turns the logarithm's base from 2 into hundreds, and that is the whole design.
- A disk read is ~100,000× slower than a memory access
- Storage transfers whole blocks, so a one-key node wastes the read
- Each node is sized to fill one block, holding hundreds of keys
- Millions of keys fit in 3 or 4 levels instead of 20
The Structure and Its Rules
A B-tree of order m — a term used inconsistently across textbooks, so it is worth defining — has each node holding at most m − 1 keys and m children. The keys within a node are kept sorted, and the children are interleaved between them: everything in the first child is smaller than the first key, everything in the second child lies between the first and second key, and so on.
Some texts define the order as the minimum degree t instead, where a node holds between t − 1 and 2t − 1 keys. Both conventions appear in exam questions, so state which you are using.
The invariants are four. Every node except the root holds at least ⌈m/2⌉ − 1 keys, which is the rule preventing nodes from becoming sparsely occupied and the tree from deepening unnecessarily. A non-leaf node with k keys has exactly k + 1 children. Keys within every node are sorted. And — the property that gives the balance guarantee — all leaves are at the same depth.
That last rule is stronger than what AVL or red-black trees promise. A B-tree is not approximately balanced; it is perfectly balanced, with every root-to-leaf path exactly the same length.
How it achieves this is the interesting part. The tree does not grow at the leaves, as a binary search tree does. It grows at the root: the height increases only when the root itself splits, and that single event lengthens every path simultaneously. This is why perfect balance is maintained without any rotations at all.
Search descends from the root, and at each node performs a binary search among the sorted keys to find either the key itself or the child interval to follow. The work is O(log_m n) block reads with O(log₂ m) in-memory comparisons per node — and only the block reads matter.
- A node holds up to m−1 sorted keys and m children
- Non-root nodes must stay at least half full
- All leaves are at the same depth — perfectly balanced
- The tree grows upward at the root, never downward at the leaves
Splitting and Merging
Insertion always begins at a leaf. Descend to the leaf where the key belongs and insert it in sorted position. If the leaf still has room, the operation is finished.
If the leaf is full, it splits. The node's keys are divided in two, and the median key moves up into the parent to act as the separator between the two halves. The left half stays, the right half becomes a new sibling, and the parent gains one key and one child.
That promotion may overflow the parent, which then splits too, promoting its own median — and this can cascade all the way to the root. When the root splits, a new root is created holding a single key, and the height of the tree increases by one. This is the only way a B-tree ever gets taller, and it is why every leaf stays at the same depth.
A practical variant, proactive splitting, splits any full node encountered on the way down rather than on the way back up. This guarantees the parent always has room and avoids the cascade entirely, at the cost of some unnecessary splits.
Deletion is the harder direction and mirrors the same logic. Removing a key may drop a node below the minimum occupancy of ⌈m/2⌉ − 1, an underflow. The repair is to look at an adjacent sibling: if it has a spare key, borrow one, rotating it through the parent so the separator stays correct. If both siblings are at minimum, merge the node with a sibling and pull the separating key down from the parent.
That merge removes a key from the parent, which may itself underflow, cascading upward. If the merge propagates to the root and leaves it empty, the root is discarded and the tree's height decreases by one — the exact inverse of the growth mechanism.
Deleting a key from an internal node follows the same principle as a BST: replace it with its inorder predecessor or successor, which lives in a leaf, then delete that key from the leaf where the borrow-or-merge machinery applies.
- A full node splits and pushes its median key to the parent
- Splits cascade upward; a root split is the only way height grows
- Underflow borrows from a sibling, or merges and pulls the separator down
- A merge cascading to an empty root reduces the height by one
Terms, operations, and practical uses
Database Foundations
- Disk BlocksData on hard drives is read in fixed-size blocks (e.g., 4KB). B-Trees align node sizes with block sizes to maximize read efficiency.
- High Branching FactorInstead of 2 children, a B-Tree node can have hundreds of children, keeping the tree exceptionally shallow.
- Multi-Key NodesA single node stores multiple sorted keys, allowing binary search within the node itself after it is loaded into memory.
Tree Mechanics
- Node SplittingWhen an insertion overflows a node's maximum capacity, it splits in half and promotes the median key to its parent.
- Bottom-Up GrowthUnlike BSTs which grow downward, B-Trees grow upward. A new root is only created when the current root splits.
- Underflow and MergingDuring deletion, if a node's key count drops below the minimum, it borrows from a sibling or merges with it.
The B+ Variant
- Data at LeavesInternal nodes only store routing keys; the actual database records (or pointers to them) exist strictly in the leaf nodes.
- Linked LeavesLeaf nodes maintain pointers to their adjacent siblings, forming a linked list across the bottom of the tree.
- Sequential ScansBecause leaves are linked, fulfilling queries like
SELECT * WHERE age > 20is lightning fast without re-traversing the tree.
Search a multi-key B-tree node
class BTreeNode:
def __init__(self, leaf=False):
self.keys = []
self.children = []
self.leaf = leaf
class BTree:
def search(self, k, node):
i = 0
while i < len(node.keys) and k > node.keys[i]:
i += 1
if i < len(node.keys) and k == node.keys[i]:
return node
elif node.leaf:
return None
else:
return self.search(k, node.children[i])
root = BTreeNode(leaf=True)
root.keys = [10, 20, 30]
found = BTree().search(20, root)
print('Found Key' if found else 'Missing')#include <iostream>
#include <vector>
using namespace std;
struct BTreeNode {
vector<int> keys;
vector<BTreeNode*> children;
bool leaf;
};
BTreeNode* search(BTreeNode* node, int k) {
int i = 0;
while (i < node->keys.size() && k > node->keys[i]) i++;
if (i < node->keys.size() && k == node->keys[i]) return node;
if (node->leaf) return nullptr;
return search(node->children[i], k);
}
int main() {
BTreeNode* root = new BTreeNode();
root->leaf = true;
root->keys = {10, 20, 30};
cout << (search(root, 20) ? "Found Key" : "Missing") << '\n';
}import java.util.*;
public class Main {
static class BTreeNode {
List<Integer> keys = new ArrayList<>();
List<BTreeNode> children = new ArrayList<>();
boolean leaf;
}
static BTreeNode search(BTreeNode node, int k) {
int i = 0;
while (i < node.keys.size() && k > node.keys.get(i)) i++;
if (i < node.keys.size() && k == node.keys.get(i)) return node;
if (node.leaf) return null;
return search(node.children.get(i), k);
}
public static void main(String[] args) {
BTreeNode root = new BTreeNode();
root.leaf = true;
root.keys = new ArrayList<>(Arrays.asList(10, 20, 30));
System.out.println(search(root, 20) != null ? "Found Key" : "Missing");
}
}Step through it
Running on search for the displayed key
Read all 11 Steps
- Order 3 A B-tree node holds up to 2 keys and 3 children. Nodes stay wide and shallow so each disk read returns many keys.
- Insert 20 20 joins the same node. Keys stay sorted inside the node.
- Insert 5 Adding 5 would make three keys in one node, which overflows an order-3 node.
- Split The median key 10 moves up to become a new root; 5 and 20 become separate children.
- Growth is upward A B-tree never grows by extending a branch downward — it grows only when the root splits. That is why every leaf stays at the same depth.
- Insert 30 30 > 10 so it belongs in the right child, which has room.
- Insert 40 40 also goes right, filling that node to its two-key limit.
- Overflow again Inserting 40 pushes the right node to three keys. Split it: 30 rises into the parent.
- Why so wide Each node maps to one disk page. A node holding hundreds of keys means a tree of a billion rows is only three or four levels deep.
- B+ variant In a B+ tree only leaves hold records and the leaves are chained left to right, so a range scan walks the chain instead of re-descending.
- Why databases use it Height stays tiny, every leaf is equidistant, and splits are rare and local. This is the structure behind most SQL indexes.
B+ Trees and Why Databases Use Them
Almost every real database index is a B+ tree rather than a plain B-tree, and the distinction is worth knowing precisely because it is a standard exam question.
In a B-tree, records are stored in every node, internal ones included. In a B+ tree, internal nodes hold only keys used for routing, and all actual data lives in the leaves. Every key also appears in a leaf, so an internal key is purely a signpost and may be duplicated below.
Two consequences follow, and both favour the B+ tree for indexing.
First, because internal nodes carry no payload, they fit more keys per block — often several times more. Higher branching means a shallower tree, which means fewer disk reads per lookup. This alone is usually decisive.
Second, the leaves are linked together in a sorted chain. A range query — 'every order between two dates' — descends once to find the first matching leaf, then simply follows the leaf links sequentially. In a plain B-tree the same query requires repeatedly traversing back up and down through internal nodes. Since range scans are the bulk of database work, this is a large practical advantage.
A third, smaller benefit: every search in a B+ tree travels the full depth to a leaf, so query times are uniform. In a B-tree a lucky key found at the root returns immediately, which sounds better but makes performance harder to predict.
This is why B+ trees back the indexes in PostgreSQL, MySQL's InnoDB, Oracle and SQL Server, and the metadata in filesystems including NTFS, HFS+, ext4 and Btrfs. In practice a B+ tree index of three or four levels covers hundreds of millions of rows, and because the upper levels stay cached in memory, a lookup typically costs one actual disk read.
The alternative worth naming is the LSM tree, used by Cassandra, RocksDB and LevelDB, which buffers writes in memory and merges them in sorted batches. It trades slower reads for much faster writes — the right choice for write-heavy workloads where a B+ tree's in-place updates become the bottleneck.
| B-tree | B+ tree | |
|---|---|---|
| Data location | Every node | Leaves only |
| Internal nodes | Keys plus records | Keys only — higher fanout |
| Leaves linked? | No | Yes, a sorted chain |
| Range scans | Repeated traversal | Follow the leaf links |
| Search cost | Varies by depth found | Always full depth — uniform |
| Used by | Some filesystems | Database indexes |
- B+ trees keep data only in leaves, so internal nodes hold more keys
- Linked leaves make range scans a sequential walk
- Used by PostgreSQL, InnoDB, NTFS and ext4
- LSM trees are the write-optimised alternative