B+ Tree Insert and Split
Eight keys, four splits, and a tree that grows at the root so every leaf stays the same depth.
Skip to the animationA B+ tree is a shallow, always-balanced index in which every key lives in a leaf, the leaves are chained in sorted order, and the tree grows at the root rather than the leaves.
Why databases use this and not a BST
A binary search tree over a million keys is about twenty levels deep. On disk, each level is a separate page read, and a page read is roughly a hundred thousand times slower than a comparison. The fix is not a faster comparison — it is fewer levels.
A B+ tree node is sized to one disk page, so it holds hundreds of keys rather than one. With a branching factor of a few hundred, a million keys fit in three levels. The shape of the tree is dictated by the hardware, not by elegance.
The animation uses order 3 — at most 3 children and 2 keys per node — purely so the splits are visible. A real node holds hundreds, and splits are correspondingly rare.
The rules
- All keys live in leaves. Internal nodes hold separator keys only — signposts, not data.
- Every leaf is at the same depth. This is what makes lookup cost identical for every key, not merely bounded.
- A node holds at most `order − 1` keys. Exceed that and it splits.
- Leaves are chained. Each leaf points to its right-hand neighbour, so the leaf level is a sorted linked list.
- The tree grows upward. Height only ever increases by creating a new root.
Insertion, and the two kinds of split
- 1Walk from the root to the correct leaf, comparing against the separator keys.
- 2Insert the key into that leaf in sorted position.
- 3If the leaf still fits, stop — this is the common case and it touches one page.
- 4If it overflows, split it in two and copy the first key of the right half up into the parent.
- 5If the parent now overflows, split it too and move its middle key up.
- 6If the overflow reaches the root, create a new root. The tree is now one level taller.
The copy/move distinction is the single most commonly dropped mark in exams, and it follows directly from the first rule:
| Splitting a… | The middle key is… | Because |
|---|---|---|
| Leaf | copied up | the key is data and must stay findable by scanning the leaves |
| Internal node | moved up | the key is only a separator, so two copies would be meaningless |
What the leaf chain buys
This is the difference between a B+ tree and a B tree, and it is the reason every relational database picked the B+ variant. A range query — WHERE grade BETWEEN 5 AND 20 — descends once to find the first matching leaf and then walks the sibling pointers sideways, never touching an internal node again.
In a B tree, where keys are scattered through internal nodes too, the same query has to keep climbing up and down. The same property makes a full ordered scan of the index a single sequential pass along the leaf level.
Costs
| Operation | Cost | Note |
|---|---|---|
| Search | O(log_b n) | b is the branching factor — hundreds, so the log is tiny |
| Insert | O(log_b n) | usually one page write; a split is rare |
| Delete | O(log_b n) | may merge or borrow from a sibling |
| Range scan | O(log_b n + k) | descend once, then walk the leaf chain |
Advantages and disadvantages
Advantages
- Height stays tiny because the branching factor is huge — three levels covers millions of keys.
- Perfectly balanced by construction, with no rotations and no pathological input order.
- Range queries and ordered scans are near-sequential thanks to the leaf chain.
- Node size maps onto a disk page, so one node visited is one page read.
Disadvantages
- Nodes are typically only about 70% full, so the index carries some slack.
- Splits and merges cost extra page writes, and a hot key range can cause repeated ones.
- Exact-match lookups alone are beaten by a hash index, which is O(1) — but a hash index cannot do ranges at all.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.