B+ Trees
All keys in linked leaves — perfect for rangesA B+ tree is the B-tree used inside almost every database. Every key lives in a leaf, the leaves are linked in order, and the inner nodes are just signposts that point the way. That makes "give me all keys from 6 to 20" a simple walk along the bottom row.
- Leaveshold every key, linked left to right
- Inner nodesonly signposts (copies of keys)
- Range scanfind the first leaf, then follow the links
- Current
- Compared
- Too many / few
- New / found
- 12signpost (inner node)
Ready
Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode
Every operation, in plain steps
These are exactly the steps the visualizer animates.
Leaves and signposts
A B+ tree has two kinds of node. LEAVES hold every key (in a database: the key plus a pointer to its row) and a next pointer to the leaf on their right. INNER nodes hold only signposts — copies of keys that tell a search which child to enter. A key equal to a signpost is always found on its right.
struct Leaf {
int n;
int keys[ORDER - 1]; // the real keys
struct Leaf *next; // the leaf to the right
};
struct Inner {
int n;
int keys[ORDER - 1]; // signposts (copies)
void *child[ORDER]; // key >= keys[i-1] → child[i]
};
Search
- Follow the signposts down: equal keys go RIGHT.
- Always continue to a leaf.
- Look for the key in that leaf.
- Every search visits exactly one node per level.
Insert
- Walk down to the leaf for the key.
- Insert it in sorted order.
- If the leaf is full, split it into two leaves…
- …and link them: left.next = right.
Leaf split vs inner split
- Leaf split: COPY the right leaf's first key up.
- The key stays in the leaf — all data is in leaves.
- Inner split: MOVE the middle signpost up (like a B-tree).
- A root split makes the tree one level taller.
Build tree
- Start with an empty tree.
- Insert the typed keys one by one, in that order.
- Every full leaf splits and COPIES a signpost up.
- The leaf chain always reads the keys in sorted order.
Range scan
- Search for the smallest key of the range.
- Read keys in that leaf.
- Follow next to the following leaf.
- Stop at the first key past the range.
Delete
- Remove the key from its leaf.
- A signpost with the same value may stay — it still guides correctly.
- Too few keys? Borrow from a sibling leaf (fix the signpost)…
- …or merge the two leaves and drop the signpost.
Why databases love it
- Inner nodes are small, so more fit in memory.
- Every lookup has the same cost (tree height).
- Range queries read leaves one after another.
- Used by MySQL (InnoDB), PostgreSQL, SQLite and file systems.
Pseudocode
Language-independent steps. The visualizer shows the same logic in C, Python and Java.
How fast is each operation?
n = number of keys, m = order, k = number of keys the range returns. A range scan costs one search plus reading the leaves that hold the k results. Building a tree of n keys is n inserts, so O(n log n).
| Operation | Best | Average | Worst | Speed |
|---|---|---|---|---|
| Search | O(log n) |
O(log n) |
O(log n) |
Grows with n |
| Insert | O(log n) |
O(log n) |
O(log n) |
Grows with n |
| Delete | O(log n) |
O(log n) |
O(log n) |
Grows with n |
| Range scan (k results) | O(log n) |
O(log n + k) |
O(log n + k) |
Grows with n |
| Build tree (n keys) | O(n log n) |
O(n log n) |
O(n log n) |
Grows with n |
B-tree vs B+ tree
| B-tree | B+ tree | |
|---|---|---|
| Where the keys are | In every node | Only in the leaves (inner nodes hold copies) |
| Leaf split | Middle key MOVES up | First key of the right leaf is COPIED up |
| Search stops | At any level | Always at a leaf |
| Leaves linked? | No | Yes — left to right |
| Range query | Climb up and down the tree | Walk along the leaves |
| Used in | Some file systems | Almost every database index |
Range scan of 6 … 20
| Step | What happens |
|---|---|
| 1 | Search for 6: follow the signposts down to its leaf |
| 2 | Output the keys ≥ 6 in that leaf |
| 3 | Follow next → read the following leaf |
| 4 | Stop at the first key larger than 20 |
Check your understanding
Answer each question — you will see the explanation straight away.
Where are all the keys of a B+ tree stored?
Every key is in a leaf. The inner nodes only hold copies that act as signposts.
A leaf splits into [5, 6] and [7, 10]. What goes up into the parent?
In a leaf split the first key of the new right leaf is COPIED up. 7 stays in the leaf, because all keys must be in the leaves.
Why does a B+ tree link its leaves?
After finding the first key, a range query just follows the next pointers — no need to go back up the tree.
A signpost is 12 and you search for 12. Which child do you go to?
The signpost 12 is the first key of the right subtree, so equal keys go right. The search always ends in a leaf.
After deleting 12 from its leaf, a signpost 12 is still in an inner node. Is the tree broken?
Signposts only have to separate smaller keys from larger ones. 12 still does that, even though 12 itself is gone.
How many nodes does a search visit in a B+ tree with 3 levels?
Searches always go down to a leaf, so every search visits one node per level: exactly 3.
Trees quiz
Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.