The previous chapter ended by pointing out that multilevel indexing, narrowing a search hierarchically through several smaller and smaller index levels, is exactly the same fundamental idea used by one of the most important data structures in all of database systems: the B+ tree. Nearly every relational database in widespread use today relies on some variation of the B+ tree to implement its indexes, making it one of the most practically significant topics in this entire course, well beyond its frequent appearance in exams and interviews.
What makes the B+ tree so well suited for database indexing is that it stays perfectly balanced at all times, no matter how many insertions and deletions occur, guaranteeing that every single search, insertion, and deletion operation takes roughly the same, predictable amount of time. This reliability matters enormously for a database engine, which cannot afford unpredictable slowdowns as a table grows from a few hundred rows to many millions.
In this tutorial, you will learn the structure of a B+ tree, including the important distinction between its internal nodes and leaf nodes, how searching works by walking down from the root, and complete worked examples showing exactly how a B+ tree grows through insertion and shrinks through deletion, including the node-splitting and node-merging operations that keep the tree balanced.
A B+ tree is a balanced, multi-level tree data structure where every leaf node sits at exactly the same depth from the root, guaranteeing consistent performance for every operation regardless of which specific value is being searched for. Unlike a plain binary search tree, where each node holds only one key and has at most two children, each node of a B+ tree can hold many keys and have many children, an arrangement often called a high branching factor, which dramatically reduces the tree's overall height even for enormous amounts of data.
The defining feature that distinguishes a B+ tree from the closely related B-tree is where the actual data resides. In a B+ tree, all of the actual record pointers are stored exclusively in the leaf nodes, while internal nodes exist purely to guide the search, holding only key values used for navigation, never actual data. Additionally, every leaf node in a B+ tree is linked to the next leaf node in sorted order, forming a connected sequential chain across the bottom of the tree.
Every B+ tree is characterized by a single number called its order, often denoted n, which determines the maximum number of children an internal node is allowed to have, and correspondingly, the maximum number of keys it can hold.
| Node Type | Contents | Rules |
|---|---|---|
| Internal Node | Key values used purely for navigation, plus pointers to child nodes. | Can hold at most n-1 keys and at most n child pointers; must hold at least ⌈n/2⌉-1 keys, except the root. |
| Leaf Node | Key values paired with actual record pointers, plus one pointer to the next leaf node. | Can hold at most n-1 keys; must hold at least ⌈(n-1)/2⌉ keys, except the root when it is also a leaf. |
This minimum-fill requirement, guaranteeing every non-root node stays at least half full, is exactly what keeps the tree efficiently packed, avoiding the kind of sparse, wasteful structure that could otherwise develop after many deletions.
Searching for a specific key begins at the root and proceeds downward, at each internal node comparing the target key against the keys stored in that node to decide which child pointer to follow next, continuing this process until a leaf node is reached, where the actual record pointer, if it exists, is found directly.
Searching for key 45 in a B+ tree of order 3: Root node: [30] If target < 30, go left; if target ≥ 30, go right. 45 ≥ 30, so go right. Internal node: [40, 50] 45 falls between 40 and 50, so follow the middle pointer. Leaf node: [40, 45, 50] 45 is found directly in this leaf node, along with its record pointer.
Since every leaf sits at exactly the same depth, this search always takes the same number of steps, regardless of which key is being searched for, giving B+ trees their predictable, reliable search performance.
Consider building a B+ tree of order 3, meaning each node can hold at most 2 keys, by inserting the keys 10, 20, 5, 6, 12, and 30 one at a time. Watching this tree grow step by step reveals exactly how and why node splitting occurs.
Leaf (root): [10, 20] Both keys fit within the maximum of 2 keys per node for order 3, so no splitting is needed yet.
Attempting to insert 5 into [10, 20] would create [5, 10, 20], exceeding the maximum of 2 keys. The leaf node splits into two leaves, and the smallest key of the new right leaf is copied up into a new root node to guide future searches. New Structure: Root: [10] Leaf 1: [5, 10] → linked to → Leaf 2: [20]
6 belongs in Leaf 1, since 6 < 10. Leaf 1 becomes [5, 6, 10], exceeding the maximum of 2 keys, so it splits again. New Structure: Root: [6, 10] Leaf 1: [5, 6] → Leaf 2: [10] → Leaf 3: [20]
12 belongs in Leaf 2, since 10 ≤ 12 < 20. Leaf 2 becomes [10, 12], which fits within the maximum of 2 keys, no split needed. Structure remains: Root: [6, 10] Leaf 1: [5, 6] → Leaf 2: [10, 12] → Leaf 3: [20]
30 belongs in Leaf 3, since 30 ≥ 20. Leaf 3 becomes [20, 30], which fits within the maximum of 2 keys, no split needed. Final Structure: Root: [6, 10] Leaf 1: [5, 6] → Leaf 2: [10, 12] → Leaf 3: [20, 30]
Notice how every leaf remains linked to the next one in sorted order, forming a chain across the bottom of the tree, from Leaf 1 through Leaf 3. This linked chain is what allows a B+ tree to efficiently support range queries, such as finding every key between 6 and 20, by locating the starting key once and then simply following the leaf-level links forward, without needing to repeatedly search back down from the root for each subsequent value.
The pattern demonstrated across the insertion example above generalizes into a clear rule followed whenever any node exceeds its maximum capacity.
Leaf node overflow: 1. Split the leaf into two leaves, dividing the keys evenly between them. 2. Copy (not move) the smallest key of the new right leaf up into the parent node. 3. Update the leaf-level links so the two new leaves remain properly connected in order. Internal node overflow: 1. Split the internal node into two internal nodes, dividing the keys evenly. 2. Move (not copy) the middle key up into the parent node. 3. If the parent itself now overflows, repeat this same splitting process upward, potentially all the way up to the root, which is exactly how the tree's height can grow over time as more keys are inserted.
The distinction between copying a key up during a leaf split versus moving a key up during an internal node split is important: leaf nodes must retain every key alongside its record pointer, since leaves are the only place actual data pointers live, while internal nodes exist purely for navigation and do not need to retain a key once it has served its purpose of dividing two child subtrees.
Deleting a key follows a similar search-then-modify process, first locating the leaf containing the key to remove it, and then checking whether the leaf still satisfies the minimum-fill requirement discussed earlier. If removing the key causes the leaf to fall below its minimum allowed number of keys, called underflow, the tree must be rebalanced, either by borrowing a key from a neighboring sibling leaf, or by merging with a neighboring sibling leaf if borrowing is not possible.
Starting structure (order 3, minimum 1 key per leaf): Root: [10] Leaf 1: [5, 8] → Leaf 2: [10, 15] Delete key 5: Leaf 1 becomes [8], which still satisfies the minimum of 1 key, so no rebalancing needed. Final Structure: Root: [10] Leaf 1: [8] → Leaf 2: [10, 15]
Continuing, now delete key 8: Leaf 1 becomes empty [], violating the minimum-fill requirement, causing underflow. Since Leaf 2 has more than the minimum number of keys, borrowing is attempted first: the smallest key of Leaf 2 could be moved into Leaf 1. If borrowing were not possible, Leaf 1 and Leaf 2 would instead be merged into a single leaf, and the corresponding key would be removed from the parent, potentially causing the parent itself to underflow and trigger further rebalancing upward, following the same logic used during insertion-driven splits, just in reverse.
| Aspect | B-Tree | B+ Tree |
|---|---|---|
| Data Storage | Record pointers can be stored in both internal nodes and leaf nodes. | Record pointers are stored exclusively in leaf nodes. |
| Leaf Node Links | Leaf nodes are typically not linked to each other. | Leaf nodes are linked together in sorted order, supporting efficient range queries. |
| Search Consistency | A key might be found in an internal node, ending the search early at varying depths. | Every search always proceeds all the way down to a leaf node, at a consistent, predictable depth. |
| Common Usage | Less commonly used directly for database indexing today. | The standard choice for indexing in the vast majority of modern relational database systems. |
The linked leaf structure and the guarantee that every search reaches the same consistent depth are exactly why B+ trees, rather than plain B-trees, have become the overwhelmingly preferred choice for implementing indexes in real-world database systems, since range queries and predictable performance matter enormously in practical database workloads.
B+ trees strike an excellent balance between the theoretical multilevel indexing concept introduced in the previous chapter and the practical realities of storing data on disk, where minimizing the number of disk accesses needed for any operation is critical for performance. By keeping the tree shallow through a high branching factor, and by keeping it perfectly balanced through disciplined splitting and merging rules, a B+ tree guarantees that even a table with millions of rows can be searched, inserted into, or deleted from using only a small, predictable number of disk accesses.
| Mistake | Correct Understanding |
|---|---|
| Assuming internal nodes store actual record pointers. | In a B+ tree, only leaf nodes store record pointers; internal nodes hold keys purely for navigation. |
| Confusing copying a key up during a leaf split with moving it during an internal split. | Leaf splits copy the key up while retaining it in the leaf, since leaves must keep every key with its data pointer; internal splits move the key up entirely. |
| Believing all B+ trees have the same height regardless of the number of keys. | The tree's height grows as more keys are inserted and nodes repeatedly overflow and split, though it grows very slowly thanks to the high branching factor. |
| Thinking B-trees and B+ trees are interchangeable in practice. | B+ trees are strongly preferred for database indexing specifically because of their linked leaves and consistent search depth, advantages plain B-trees do not offer. |
The B+ tree turns the multilevel indexing concept from the previous chapter into a precise, self-balancing data structure, guaranteeing that every leaf sits at exactly the same depth and that every operation completes in a small, predictable number of steps, even as a table grows to millions of rows. Through a complete worked insertion sequence demonstrating node splitting, and a worked deletion example demonstrating underflow handling, this chapter showed exactly how a B+ tree maintains its balance and efficiency through every change.
In this tutorial, you learned the structure of internal and leaf nodes in a B+ tree, how searching walks down from the root to a leaf, a complete worked example building a tree through six insertions with two node splits, how deletion handles underflow through borrowing or merging, and how B+ trees compare to plain B-trees. With this foundation, you are ready to move on to hashing, an alternative approach to organizing data for fast retrieval that takes a fundamentally different strategy from the tree-based indexing covered in this chapter.