101
0/276
Loading content...
Before we tackle the complexity of B-trees—the industrial-strength data structures powering modern databases—we need a stepping stone. Enter the 2-3 tree: a beautifully simple structure that captures the essence of multi-way balanced trees while remaining approachable enough to fully understand.
The 2-3 tree is not merely a pedagogical curiosity. It represents a fundamental insight about balance: by allowing nodes to have varying numbers of children (2 or 3), we gain the flexibility to maintain perfect balance without complex rotations. This flexibility principle extends to B-trees, where nodes can have anywhere from ⌈m/2⌉ to m children.
By the end of this page, you will understand the structure and invariants of 2-3 trees, how their balance is guaranteed, and why they serve as the mental model for understanding B-trees. You'll trace through insertion and deletion operations, seeing how nodes split and merge to maintain perfect balance.
A 2-3 tree is a balanced search tree where every node is one of two types:
2-node: Contains exactly one key and has exactly two children
3-node: Contains exactly two keys (k₁ < k₂) and has exactly three children
Every leaf in a 2-3 tree is at the same depth. This is the defining property that guarantees O(log n) operations. Unlike AVL trees that maintain approximate balance, 2-3 trees achieve perfect balance—every root-to-leaf path has exactly the same length.
Formal Invariants:
These invariants collectively guarantee that the tree remains balanced and supports efficient search, insertion, and deletion.
The power of 2-3 trees lies in their guaranteed height bounds. Let's analyze the relationship between the number of keys and tree height.
Best Case Height (all 3-nodes):
When every node is a 3-node with 2 keys, the tree has maximum branching factor 3. At height h:
Maximum keys at height h: 2 + 6 + 18 + ... + 2×3^h = 3^(h+1) - 1 keys
Worst Case Height (all 2-nodes):
When every node is a 2-node with 1 key, the tree degenerates to a perfectly balanced binary tree. At height h:
Maximum keys at height h: 2^(h+1) - 1 keys
| Number of Keys (n) | Min Height (all 3-nodes) | Max Height (all 2-nodes) |
|---|---|---|
| 7 | 1 | 2 |
| 26 | 2 | 4 |
| 80 | 3 | 6 |
| 1,000 | ~6 | ~10 |
| 1,000,000 | ~12 | ~20 |
| 1,000,000,000 | ~19 | ~30 |
The key insight:
For n keys, the height of a 2-3 tree is bounded by:
log₃(n+1) - 1 ≤ height ≤ log₂(n+1) - 1
Both bounds are O(log n), meaning 2-3 trees guarantee logarithmic operations regardless of the mix of 2-nodes and 3-nodes. The tree automatically adjusts its structure during operations—more 3-nodes mean a shorter tree, more 2-nodes mean a taller (but still logarithmic) tree.
Unlike AVL trees where balance is measured by height differences, 2-3 trees achieve balance through perfect leaf depth. This makes the height analysis simpler and the guarantees stronger—there's no 'worst case' within the logarithmic bound.
Searching in a 2-3 tree extends the binary search tree algorithm to handle nodes with two keys.
Algorithm:
Search(node, target):
if node is null:
return NOT_FOUND
if node is a 2-node with key k:
if target == k: return FOUND
if target < k: return Search(node.left, target)
else: return Search(node.right, target)
if node is a 3-node with keys k₁, k₂:
if target == k₁ or target == k₂: return FOUND
if target < k₁: return Search(node.left, target)
if target > k₂: return Search(node.right, target)
else: return Search(node.middle, target) // k₁ < target < k₂
Trace example:
Consider a 2-3 tree containing keys [10, 20, 30, 40, 50, 60, 70, 80, 90]. Let's search for 45:
Start at root [40]
At node [60, 80]
At node [50]
At leaf [45] — Found!
Each step descends one level, making at most 1-2 comparisons per level. Total comparisons: O(log n).
Time Complexity:
Insertion in a 2-3 tree is where the magic happens. Unlike AVL trees that rebalance through rotations after insertion, 2-3 trees maintain balance through node splitting and key promotion.
Core principle: New keys are always inserted at leaf nodes. If this creates an overflow (a would-be 4-node), we split and promote.
Case 1: Inserting into a 2-node
This is the simple case. A 2-node has room for one more key, so it simply becomes a 3-node:
Before: [30] After inserting 50: [30, 50]
/ \ / | \
No restructuring needed—the tree remains balanced.
Case 2: Inserting into a 3-node (causes split)
A 3-node already has 2 keys—adding a third creates a temporary "4-node" which violates our invariants. We handle this by:
Before: [30, 50] Insert 40 creates temp [30, 40, 50]
/ | \
→ Split into:
[40] (promoted to parent)
/ \
[30] [50] (new 2-nodes)
When we promote a key to the parent, the parent might also overflow! If the parent was a 3-node, it too must split and promote. This ripple can propagate all the way to the root. If the root splits, a new root is created, and the tree height increases by one.
Case 3: Splitting propagates to the root
When a split reaches the root and the root is a 3-node, the root itself splits. The middle key becomes a new root with two children:
Before: [30, 60] After inserting 45 (causes cascading splits):
/ | \
[10] [45] [80] [45]
/ \
[30] [60]
/ \ / \
[10] [40] [50] [80]
(tree grows taller by 1)
Key insight: 2-3 trees grow from the bottom up, not the top down. The tree only gets taller when the root splits—and when this happens, the entire tree gains one level simultaneously, preserving the equal-depth invariant.
Complete Insertion Algorithm:
Insert(tree, key):
if tree is empty:
create a new 2-node as root with key
return
result = InsertRecursive(tree.root, key)
if result is a promoted key with two children:
create new root as 2-node with promoted key
set children to left and right from result
InsertRecursive(node, key):
if node is a leaf:
return AbsorbOrSplit(node, key, null, null)
// Find the appropriate child
child = appropriate child based on key comparison
result = InsertRecursive(child, key)
if result indicates promotion:
return AbsorbOrSplit(node, promoted_key, left_child, right_child)
else:
return NO_PROMOTION
AbsorbOrSplit(node, key, left, right):
if node is a 2-node:
convert to 3-node, absorbing key and children
return NO_PROMOTION
else: // node is a 3-node
create temp 4-node with all 3 keys
split into two 2-nodes
return (middle_key, left_2node, right_2node)
Deletion in 2-3 trees is more complex than insertion but follows a symmetric logic: instead of splitting overflowing nodes, we borrow from siblings or merge underflowing nodes.
The challenge: If we delete a key from a 2-node, it becomes empty (a "1-node"), which violates our invariants. We must restructure to maintain balance.
Step 1: Reduce to deleting from a leaf
If the key to delete is in an internal node, we replace it with its in-order predecessor or successor (which is always in a leaf or near-leaf node), then delete that replacement key from its original position.
Case 1: Delete from a 3-node
Simple! A 3-node with 2 keys can lose one and become a valid 2-node:
Before: [30, 50] After deleting 50: [30]
No restructuring needed.
Case 2: Delete from a 2-node with a 3-node sibling (Borrow/Rotate)
If deleting from a 2-node would leave it empty, but a sibling is a 3-node, we can "borrow" a key through the parent:
Before: [50] After deleting 30 (borrow from sibling):
/ \
[30] [60, 80] [60]
/ \
[50] [80]
We rotate: 50 moves down to replace the deleted key, and 60 moves up to replace 50.
Case 3: Delete from a 2-node with 2-node siblings (Merge)
If the sibling is also a 2-node, neither can spare a key. We merge the empty slot, its sibling, and the separating key from the parent into a single 3-node:
Before: [50] After deleting 30 (merge):
/ \
[30] [70] [50, 70]
(merged node)
This reduces the number of nodes at this level and may cause the parent to underflow, triggering recursive restructuring.
If merging propagates to the root and the root is a 2-node that loses its only key, the merged node becomes the new root, and the tree shrinks by one level. This is the only way a 2-3 tree decreases in height—symmetrically to how it only grows when the root splits.
Complete Deletion Algorithm:
Delete(tree, key):
result = DeleteRecursive(tree.root, key)
if root is empty:
tree.root = root's only child (if any)
DeleteRecursive(node, key):
if key is in this node:
if node is a leaf:
return RemoveFromLeaf(node, key) // may cause underflow
else:
replace key with in-order predecessor/successor
delete that predecessor/successor from its location
else:
child = appropriate child
result = DeleteRecursive(child, key)
if child underflowed:
return FixUnderflow(node, child) // borrow or merge
return OK
FixUnderflow(parent, emptyChild):
sibling = adjacent sibling of emptyChild
if sibling is a 3-node:
Rotate(parent, emptyChild, sibling)
return OK
else: // sibling is a 2-node
Merge(parent, emptyChild, sibling)
return (parent may now underflow)
The 2-3 tree's perfect balance isn't coincidental—it's a direct consequence of the insertion and deletion algorithms.
Insertion preserves balance:
Therefore, all leaves remain at the same depth after insertion.
Deletion preserves balance:
Therefore, all leaves remain at the same depth after deletion.
By allowing nodes to temporarily hold different numbers of keys (2 or 3), we gain the flexibility to absorb insertions and deletions locally. Only when this flexibility is exhausted (overflow or underflow) do we propagate changes upward—and when we reach the root, the change affects all paths equally.
Contrast with AVL trees:
AVL trees maintain balance through rotations that locally adjust height. This works but allows height differences of 1 at each node, leading to trees that are approximately (not perfectly) balanced.
2-3 trees take a different approach: perfect balance through flexibility in node size. The cost is more complex node handling, but the benefit is simpler height analysis and absolute guarantees.
The flexibility principle:
This is the core insight that extends to B-trees: by allowing nodes to hold a range of keys (not a fixed number), we create slack that absorbs changes without propagation. Most insertions and deletions complete without any restructuring—only boundary cases trigger splits or merges.
The 2-3 tree is actually a special case of the B-tree family. Understanding this connection illuminates both structures.
A 2-3 tree is a B-tree of order 3:
In B-tree terminology:
For m=3:
| B-Tree Order (m) | Children per Node | Keys per Node | Common Name |
|---|---|---|---|
| 3 | 2 to 3 | 1 to 2 | 2-3 Tree |
| 4 | 2 to 4 | 1 to 3 | 2-3-4 Tree |
| 5 | 3 to 5 | 2 to 4 | — |
| 101 | 51 to 101 | 50 to 100 | Typical DB B-Tree |
| 1001 | 501 to 1001 | 500 to 1000 | Large B-Tree |
What changes with higher orders:
The algorithm structure remains identical:
This is why 2-3 trees are the perfect learning model: understand them deeply, and you understand all B-trees.
There's a fascinating equivalence between 2-3 trees and red-black trees that reveals deep structure in balanced tree theory.
The transformation:
Every 2-3 tree can be transformed into an equivalent red-black tree:
2-node transformation:
[K] → K (black)
/ \ / \
A 2-node becomes a black node with two children.
3-node transformation:
[K₁, K₂] → K₂ (black)
/ | \ / \
K₁ child
(red)
/ \
A 3-node becomes a black node with a red left child. The red child represents the "same node" as its black parent—they were one 3-node in the 2-3 tree.
This transformation explains the red-black tree properties: No two red nodes in a row (a 2-3 node has at most 2 keys), and all paths have the same number of black nodes (all 2-3 tree paths pass through the same number of nodes, and each becomes one black node).
Why this matters:
The practical trade-off:
Most programming language standard libraries (Java's TreeMap, C++'s std::map) use red-black trees because binary nodes are simpler to implement efficiently.
We've explored the 2-3 tree in depth, establishing the conceptual foundation for B-trees. Let's consolidate the key insights:
What's next:
With the 2-3 tree firmly understood, we're ready to explore B-trees—the industrial-strength generalization that powers modern database systems. B-trees use the same principles but with much higher branching factors, optimized for disk-based storage.
You now understand 2-3 trees: their structure, invariants, operations, and place in the balanced tree family. This knowledge transfers directly to B-trees—the same algorithms, just with larger nodes filled with more keys.