Balanced search trees for data that lives on disk, where one access costs more than a million comparisons — so the answer is nodes with hundreds of children and a tree three levels deep.
Every structure so far assumed the RAM model, where all memory costs the same. B-trees discard that assumption. When data sits on a disk or SSD, a single access costs milliseconds while a comparison costs nanoseconds, so the only quantity worth minimising is the number of node accesses. A B-tree does that by making each node enormous — one full disk page, holding hundreds or thousands of keys — which makes the tree extremely shallow. This is the data structure behind essentially every relational database index and every serious filesystem.
| Access | Typical latency | Relative to a comparison |
|---|---|---|
| CPU comparison | ~1 ns | 1× |
| Main memory | ~100 ns | 100× |
| SSD read | ~100 µs | 100,000× |
| Spinning disk seek | ~5 ms | 5,000,000× |
CLRS models this with explicit DISK-READ and DISK-WRITE operations in the pseudocode, and counts them separately from CPU time.
A B-tree T with root T.root satisfies:
x has: x.n keys stored in non-decreasing order x.key₁ ≤ … ≤ x.keyx.n, and a boolean x.leaf.x.n + 1 children pointers x.c₁, …, x.cx.n+1. Leaves have none.kᵢ in subtree x.cᵢ satisfies k₁ ≤ x.key₁ ≤ k₂ ≤ x.key₂ ≤ …t ≥ 2 bounds node occupancy: every node other than the root has at least t - 1 keys, and every node has at most 2t - 1 keys. A node with exactly 2t - 1 keys is full.t = 3. Keys inside a node act as separators between its children.t is the one parameter. Each node holds between t-1 and 2t-1 keys, and therefore has between t and 2t children. The lower bound is what guarantees nodes stay at least half full, so the tree cannot become sparse and tall. In practice t is chosen so a node exactly fills one disk page — often in the hundreds or low thousands.n ≥ 1, then for any n-key B-tree of height h and minimum degree t ≥ 2,h ≤ logₜ ( (n + 1) / 2 )The proof counts nodes level by level: the root has at least 1 key, and at depth i ≥ 1 there are at least 2ti-1 nodes each holding at least t-1 keys. Summing the geometric series gives n ≥ 2tᵗ - 1, and rearranging gives the bound.
t = 1001 (so up to 2001 keys and 2002 children per node) and one billion keys, the height is at most log₁₀₀₁(500,000,000) ≈ 2.9, so 3 levels. A search touches 3 nodes. If the root is cached in memory, that is 2 disk reads to find any key among a billion. Compare with a red-black tree at 30 levels.The saving compared to a binary tree is a factor of lg t, since logₜ n = lg n / lg t. That is the entire design in one identity.
B-TREE-SEARCH(x, k)
1 i = 1
2 while i ≤ x.n and k > x.keyᵢ
3 i = i + 1
4 if i ≤ x.n and k == x.keyᵢ
5 return (x, i) // found
6 elseif x.leaf
7 return NIL // not in the tree
8 else
9 DISK-READ(x.cᵢ)
10 return B-TREE-SEARCH(x.cᵢ, k)A multiway generalisation of binary search: at each node find which of the x.n + 1 gaps k falls into, then descend.
| Measure | Cost |
|---|---|
| Disk accesses | O(h) = O(logₜ n) — the number that matters |
| CPU time | O(t logₜ n) with a linear scan inside each node |
The linear scan on line 2 could be a binary search, reducing CPU time to O(lg t · logₜ n) = O(lg n). CLRS notes this and then ignores it, because CPU time is not the bottleneck — which is exactly the point of the chapter.
Insertion cannot simply add a key to a full node. The primitive that fixes this is the split.
B-TREE-SPLIT-CHILD(x, i) takes a non-full internal node x and a full child y = x.cᵢ with 2t-1 keys. It splits y around its median key into two nodes of t-1 keys each, and moves the median up into x, which gains one key and one child.O(t) CPU time and O(1) disk writes. This is the only operation that changes the tree’s shape during insertion.The elegant part. Rather than descending, discovering an overflow, and backing up, the algorithm splits every full node it meets on the way down. That guarantees the parent always has room for a key pushed up, so no backtracking is ever needed.
B-TREE-INSERT(T, k)
1 r = T.root
2 if r.n == 2t - 1 // root is full: grow the tree taller
3 s = ALLOCATE-NODE()
4 T.root = s
5 s.leaf = FALSE
6 s.n = 0
7 s.c₁ = r
8 B-TREE-SPLIT-CHILD(s, 1)
9 B-TREE-INSERT-NONFULL(s, k)
10 else B-TREE-INSERT-NONFULL(r, k)B-TREE-INSERT-NONFULL is called only on a node guaranteed not to be full. If the node is a leaf it inserts the key directly; otherwise it finds the right child, splits it if full, and recurses.
| Measure | Insert cost |
|---|---|
| Disk accesses | O(h) — one downward pass, no backtracking |
| CPU time | O(t h) = O(t logₜ n) |
| Splits per insert | At most h, and usually far fewer |
Deletion is the messiest operation in the chapter. CLRS describes it in prose rather than pseudocode, which is itself a comment on its complexity. The governing principle mirrors insertion:
t keys — one more than the minimum. Then removing a key from it cannot push it below the minimum, and again no backtracking is needed.The cases, in outline:
| Case | Situation | Action |
|---|---|---|
| 1 | k is in a leaf with at least t keys | Delete it. Done. |
| 2a | k is in internal node x; the child before k has ≥ t keys | Replace k with its predecessor and recursively delete that. |
| 2b | The child after k has ≥ t keys | Replace k with its successor and recursively delete that. |
| 2c | Both adjacent children have only t-1 keys | Merge them with k into one node of 2t-1 keys, then delete k from it. |
| 3a | k is in a subtree whose root has t-1 keys, and a sibling has ≥ t | Borrow: move a key from the sibling up to the parent and one from the parent down. |
| 3b | Both siblings have t-1 keys | Merge the child with a sibling, pulling a key down from the parent. |
Cost is O(h) disk accesses and O(t h) CPU time, same as insertion. Cases 2a/2b are the direct analogue of BST deletion by successor from Chapter 12; the borrow-or-merge pair in case 3 is the mirror of the split in insertion.
t-1 keys, fix it first by borrowing or merging — and the cases follow from it. This is the same advice as red-black deletion, and for the same reason.O(logₜ n) and then walks sequentially without touching internal nodes at all — which is what makes WHERE x BETWEEN a AND b fast.| Red-black tree | B-tree | |
|---|---|---|
| Children per node | 2 | t to 2t, often hundreds |
Height for n = 10⁹ | ~30 | ~3 |
| Optimises | Comparisons | Node accesses |
| Lives in | Memory | Disk or SSD |
| Found in | std::map, Linux scheduler | Every database index, NTFS, ext4, HFS+, APFS |
t: every non-root node holds between t-1 and 2t-1 keys, so between t and 2t children. A node with 2t-1 keys is full.≤ logₜ((n+1)/2). With t = 1001, a billion keys fit in 3 levels.O(logₜ n) disk accesses, O(t logₜ n) CPU.t-1 keys — borrow from a sibling or merge first. B+ trees, with data only in linked leaves, are what real databases use.Chapter 19 covers disjoint-set forests, a structure with a startling analysis: two simple heuristics bring the amortized cost per operation down to α(n), the inverse Ackermann function, which is at most 4 for any input that will ever exist. It is the last data structure in the book and the one Kruskal’s algorithm in Chapter 21 depends on.