How a B+ Tree Is Built with Data

4
2

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

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

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

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

Root Split: Insert 10

Insert 0: Follow the Search Path

To insert 0:

  1. Compare it with root separator 7 and go left.

  2. Compare it with separators 3 and 5, then choose the leftmost leaf.

  3. Insert it before 1 and 2.

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

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.

CS Core

Read Similar Blogs

Comments0