Why Red-Black Trees Are Not Ideal for Disk Storage
The red-black trees discussed earlier in this series achieve excellent O(log n) performance when data fits entirely in main memory, where every node access costs roughly the same small amount of time. But when data is too large for memory and must reside on disk, a completely different cost model applies: reading a single disk block takes orders of magnitude longer than any in-memory operation, similar in spirit to the memory hierarchy latency differences discussed earlier in this series regarding computer architecture. In this setting, the number of disk accesses, not the number of comparisons, dominates running time.
The Core Idea: Wide, Shallow Trees
A B-Tree minimizes disk accesses by drastically reducing tree height: instead of each node having only 2 children like a binary search tree, a B-tree node holds many keys and can have hundreds or thousands of children, matching the size of a single disk block. This means a B-tree over millions of keys might have a height of only 3 or 4, requiring only 3 or 4 disk reads to find any key, compared to the far greater height a balanced binary tree would need.
Formal B-Tree Properties
A B-tree is defined by a Minimum Degree t (t ≥ 2), which bounds the number of keys each node can hold.
Every node other than the root must have
at least t-1 keys (and thus at least t children if internal)
Every node can have at most 2t-1 keys
(and thus at most 2t children if internal)
The root may have as few as 1 key
(unless the tree is empty)
Keys within a node are stored in sorted order
All leaves appear at exactly the same depth
(the tree is always perfectly height-balanced)Each internal node with k keys has exactly k+1 children, and the keys act as separators: the subtree between two consecutive keys contains all values falling between them, generalizing the binary-search-tree property discussed earlier in this series to multiple children per node.
Example internal node with 3 keys (t=2, so 1-3 keys allowed):
[10 | 20 | 30]
/ | | \
c0 c1 c2 c3
c0: all keys < 10
c1: all keys between 10 and 20
c2: all keys between 20 and 30
c3: all keys > 30Searching a B-Tree
Search generalizes the binary-search-tree search discussed earlier in this series: within each node, scan (or binary search) the sorted keys to find the correct child to descend into, then recurse.
B-TREE-SEARCH(x, k):
i = 1
while i ≤ x.n and k > x.key[i]:
i = i + 1
if i ≤ x.n and k == x.key[i]:
return (x, i) // found
elif x.leaf:
return NIL // not found
else:
DISK-READ(x.c[i])
return B-TREE-SEARCH(x.c[i], k)Since the tree has height O(logₜ n), and each node requires one disk access (or one in-memory scan through up to 2t-1 keys), the total search cost is O(t logₜ n) — a small number of expensive disk accesses combined with fast in-memory work within each node.
Insertion: Splitting Full Nodes on the Way Down
Inserting into a B-tree must handle the case where a node is already full (has 2t-1 keys) and cannot accept another key without violating the maximum-keys property. The standard technique Splits a full node into two nodes, each with t-1 keys, pushing the middle key up into the parent.
B-TREE-SPLIT-CHILD(x, i):
// splits the full child x.c[i] in half,
// moving its median key up into x
z = ALLOCATE-NODE()
y = x.c[i]
z.leaf = y.leaf
z.n = t - 1
copy y's last t-1 keys into z
copy y's last t children into z (if not leaf)
y.n = t - 1
insert z as a new child of x, right after y
move y's median key up into x at position i
x.n = x.n + 1The key insight for maintaining efficiency is a Proactive Splitting strategy: rather than descending all the way down and then discovering a node is full (which would require backtracking), the algorithm splits any full node it encounters on the way down, before descending into it. This guarantees that by the time the algorithm reaches the correct leaf for insertion, that leaf is guaranteed not to be full, since its parent would have already split it if it were.
B-TREE-INSERT(T, k):
r = T.root
if r.n == 2t - 1:
// root is full — grows the tree by one level
s = ALLOCATE-NODE()
T.root = s
s.leaf = FALSE
s.n = 0
s.c[1] = r
B-TREE-SPLIT-CHILD(s, 1)
B-TREE-INSERT-NONFULL(s, k)
else:
B-TREE-INSERT-NONFULL(r, k)Because splitting is done proactively in a single downward pass, insertion requires only O(logₜ n) disk accesses, matching the tree's height, with no need for a separate upward pass or backtracking.
Deletion: A More Involved Downward Pass
Deletion follows a similar proactive philosophy, but must handle more cases: if a key to be deleted is in an internal node, it must be replaced by its predecessor or successor (analogous to the binary-search-tree deletion discussed earlier in this series), and if a node the algorithm needs to descend into has only the minimum t-1 keys, it must first be given an extra key, either by borrowing one from an adjacent sibling or by merging with a sibling, before the descent continues. This ensures every node visited during the downward pass has enough keys to safely lose one, again avoiding the need for a separate backtracking phase.
Why B-Trees Dominate in Disk-Based and Database Systems
B-trees, and their common variant B+ Trees (which store all actual data in the leaves and use internal nodes purely for navigation), form the backbone of nearly every relational database index and many file systems. The choice of minimum degree t is typically tuned so that a single node exactly fills one disk block (often 4KB or larger), maximizing the number of keys examined per disk access and minimizing the tree's height for a given number of keys.
Practical example:
With t = 1000 (a realistic value for database indexes),
a B-tree can index over 1 billion keys with a height of only 3,
meaning any key can be found with at most 3 disk readsThis dramatic height reduction compared to a binary search tree — which would need roughly 30 levels for the same billion keys — is precisely why B-trees, rather than red-black trees, are the standard choice whenever data must be stored on disk rather than kept entirely in memory.