How does a database index find one row among billions in three or four disk reads? A B-tree packs many sorted keys into each node and, when a node overflows, splits it in half and floats its median key up to the parent. The tree grows upward, never sideways — so every leaf stays the same depth and the tree stays shallow.
O(log n) search/insert · balanced · disk-friendly
many keys / node
Each node holds several sorted keys — here up to 3 — mapping to a disk page.
insert at a leaf
Every new key slots into a leaf, keeping the node's keys sorted.
split on overflow
A 4th key overflows: split in two, promote the median to the parent.
grow at the root
If the root splits, a new root appears — the whole tree deepens evenly.
btree.js — insert, overflow, split, promote
Ready
Insert keys one at a time into a B-tree with at most 3 keys per node. Press Step: each key drops into the correct leaf. When a leaf holds a 4th key it splits — the middle key rises to the parent, and if the root itself splits, the tree gains a level.
–
inserting
1
height
0
splits
How it works
A binary search tree makes one comparison per level and can grow tall and skinny. A B-tree does the opposite: it makes many comparisons per node and stays short. The magic that keeps it balanced is that the tree only ever grows at the top — splits push work upward, never leaving one branch longer than another.
1
Descend to a leaf
Follow the routing keys down: at each node, go into the child between the two keys that bracket your new key. Insertion always lands in a leaf.
2
Insert in sorted order
Slot the key into the leaf so the node's keys stay sorted. If the node now has ≤ 3 keys, you're done.
3
Overflow → split
A 4th key overflows. Split the node: left keeps the smaller keys, right takes the larger, and the median is promoted into the parent as a new routing key.
✓
Cascade or grow
The promotion may overflow the parent, splitting again up the chain. If the root splits, a fresh root holds the lone median — every leaf just got one level deeper, together.
Search
O(log n)
Insert / delete
O(log n)
Height (n keys)
O(log_t n)
Node = page
1 disk read
The code
# MAX = 2t-1 keys per node; insert returns a promotion or Nonedef insert(node, key):
if node.leaf:
sorted_put(node.keys, key)
else:
i = child_index(node, key)
up = insert(node.child[i], key)
if up: # child split — absorb its median
node.keys.insert(i, up.median)
node.child.insert(i + 1, up.right)
if len(node.keys) > MAX:
return split(node) # overflow → promote median upreturn None
def split(node):
mid = len(node.keys) // 2
right = Node(keys=node.keys[mid+1:], child=node.child[mid+1:])
median = node.keys[mid]
node.keys, node.child = node.keys[:mid], node.child[:mid+1]
return Promotion(median, right)
Because splits only ever add a node beside an existing one and push a single key upward, every leaf stays at the identical depth — that's the invariant that guarantees O(log n). Real databases tune the node size so one node fills one disk or memory page (often thousands of keys), which is why a B-tree over a billion rows is only three or four levels tall. The B+ tree variant keeps all values in linked leaves for fast range scans.
Quick check
1. When a node overflows, what happens to its median key?
Right — the median moves up to the parent, splitting the node into a left half (smaller keys) and a right half (larger keys). That upward promotion is what keeps the tree balanced.
2. Why does a B-tree stay balanced — all leaves at equal depth?
Right — insertions land in leaves and overflow propagates upward. The only way height increases is a root split, which deepens every leaf by one at once. No single branch can get ahead.
FAQ
What is a B-tree?
A balanced search tree with many sorted keys per node and many children, giving O(log n) search/insert/delete while staying only a few levels deep.
How does it stay balanced?
Inserts go into leaves; overflowing nodes split and promote their median upward. Height grows only when the root splits, so all leaves stay at equal depth.
Why do databases love B-trees?
A node maps to a disk/SSD page holding many keys, so even a billion-key index is 3–4 levels tall — a lookup is 3–4 page reads.
B-tree vs B+ tree?
A B+ tree keeps all values in linked leaves and uses internal nodes only for routing, which makes range scans fast. Most DB indexes use B+ trees.
SOLVE IT YOURSELF
Solve it: build a B-tree
A binary tree asks one question per node. On disk, one node is one page read — so you want fat nodes that answer many questions per read. A B-tree of minimum degree 3 holds a thousand keys in six levels. Python or TypeScript.
YOUR TASK
Implement BTree (minimum degree t=3) with insert(key), search(key), keys() and height(). Every non-root node must hold between t-1 and 2t-1 keys.
HINTS — 7 IDEAS
A node holds a sorted array of keys and, if internal, one more child than it has keys. Child i covers everything between key i-1 and key i.
Search scans the key array for the first key not less than the target, then descends into the matching child. Fat nodes mean very few descents.
The trick that keeps it balanced is splitting on the way down: before descending into a full child, split it. A full node has 2t-1 keys — the median moves up into the parent, the two halves become separate nodes.
Because you split before descending, the parent is guaranteed to have room for the promoted median. No cascading fix-up pass is ever needed.
The root is the exception: when the root itself is full, put a new empty root above it and split. That is the only way a B-tree grows taller, which is why all leaves stay at the same depth.
Uniform leaf depth is the whole point — every lookup costs the same number of page reads, so worst-case disk latency is predictable.
Deletion (borrowing from siblings and merging) is the harder half and is left out here; insertion carries the core idea.