Introduction
A B+ Tree does not need a large structure before it can store data. It can begin as a single leaf page and grow as entries are inserted.
Following a small example makes that growth easier to understand. We will see how a full leaf splits, how separator keys appear in a parent, and how an overflowing root increases the tree’s height.
Set Up the Example
Assume each inserted entry contains a search key and an associated record or record reference. For this walkthrough:
Each leaf holds at most three entries.
Each internal node holds at most three separator keys, giving it at most four children.
Leaf entries remain sorted.
All leaves stay at the same depth.
A separator represents the smallest key in its right subtree.
Equality follows the child to the right of that separator.
We insert keys 1 through 10, then insert 0. These are teaching keys, not automatically generated hidden database identifiers. Real page capacities and split policies depend on the implementation.
Start with One Leaf
Insert keys 1, 2, and 3. All three fit into one leaf page, which also serves as the root because there is no level above it yet.
Each key has an associated record or record reference. The leaf is now full, but no split is needed until another insertion exceeds its three-entry capacity.
Start with One Leaf
Insert 4: The First Leaf Split
Inserting 4 would create four entries in a leaf that holds only three. Split the entries into two sorted leaves and create a new root containing separator 3.
Leaf | Keys |
|---|---|
Left | 1, 2 |
Right | 3, 4 |
Keys below 3 follow the left child, while keys greater than or equal to 3 follow the right child. The data entry for 3 remains in the right leaf; its copy in the root guides navigation. The leaves are also linked in key order.
First Leaf Split: Insert 4
Insert 5 Through 8: The Root Gains Separators
Key 5 fits into the right leaf, making its contents 3, 4, 5. Inserting 6 overflows that leaf, so it splits into 3, 4 and 5, 6. Separator 5 is then copied into the root.
Key 7 fits into the rightmost leaf. Inserting 8 causes another split, producing leaves 5, 6 and 7, 8, with separator 7 copied into the root.
After inserting | Root separators | Leaf groups, left to right |
|---|---|---|
4 | 3 | (1, 2), (3, 4) |
6 | 3, 5 | (1, 2), (3, 4), (5, 6) |
8 | 3, 5, 7 | (1, 2), (3, 4), (5, 6), (7, 8) |
Each leaf split adds a child pointer and a separator to its parent. After inserting 8, the root has three separators and four children. It is full, but it has not overflowed.
After Inserting 8: The Root Is Full
Insert 9 and 10: The Root Splits
Key 9 fits into the rightmost leaf, producing 7, 8, 9. Inserting 10 splits that leaf into 7, 8 and 9, 10, so separator 9 must enter the root.
The root would now contain 3, 5, 7, 9, exceeding its three-separator capacity. Using one valid internal-node split, promote separator 7 into a new root.
Level | Contents and children |
|---|---|
New root | Separator 7; points to two internal nodes |
Left internal node | Separators 3, 5; points to leaves (1, 2), (3, 4), (5, 6) |
Right internal node | Separator 9; points to leaves (7, 8), (9, 10) |
Unlike a leaf split, this internal split moves separator 7 upward rather than retaining it in either resulting internal node. The data entry for 7 remains in its leaf. The tree now has three levels, with every leaf at the same depth.
Root Split: Insert 10
Insert 0: Follow the Search Path
To insert 0:
Compare it with root separator
7and go left.Compare it with separators
3and5, then choose the leftmost leaf.Insert it before
1and2.
The leaf becomes 0, 1, 2, which fits without another split. The search path locates the correct leaf without scanning every page.
Insert 0: Follow the Search Path
What the Finished Tree Supports
A lookup for 6 follows the root, the left internal node, and the leaf containing 5, 6. A range search from 2 through 6 first locates 2, then follows the linked leaves to collect the remaining qualifying entries.
Future inserts follow the same process: locate the leaf, insert in order, and split upward when necessary. Deletions may require separator changes, redistribution, or merging, depending on the tree’s rules.
Summary
A B+ Tree begins with a leaf and grows through controlled splits. Leaf splits copy separators into parents, while internal splits can promote separators to the next level.
A new root increases the height while preserving equal leaf depth. This balanced organization keeps searches guided, and linked leaves make consecutive traversal efficient.
Be the first to add a comment.