Part 06•Chapter 8 of 10•Intermediate

Multiway Trees, B-Trees & B+ Trees

Storage page disk access latency, B-Tree (M-way) balancing invariants, proactive node splitting, and B+ Tree leaf linked-list sequential scans.

~12 min read

2,230 words

17 Sections

Reviewed & Verified (2024 Syllabus)

Keys: [ Prev • ] Next

Disk Block I/O BottlenecksB-Tree Node SplittingB+ Tree Sequential Leaves

When data scales beyond random-access memory, binary trees fail due to disk seek latency. Multiway search trees solve the memory wall by matching node capacity to physical storage pages, collapsing tree height into shallow, high-fanout hierarchies where B-Trees and B+ Trees power virtually all production relational databases and filesystem storage engines.

1. Executive Summary & Learning Objectives

Invented by Rudolf Bayer and Edward M. McCreight in 1970 at Boeing, the B-Tree is a self-balancing search tree optimized for systems reading and writing large blocks of memory. Unlike binary trees whose branching factor is fixed at 2, B-Trees and B+ Trees expand their branching factor to hundreds or thousands of keys per node, keeping the tree exceptionally shallow and minimizing disk I/O operations.

By the end of this chapter, you will be able to:

Analyze the storage hierarchy latencies (L1 cache vs. RAM vs. NVMe SSD vs. HDD) and formulate why binary search trees fail on external storage.
State the formal B-Tree invariants parameterized by minimum degree $t \geq 2$ , calculating key and child boundaries across all levels.
Execute proactive split insertions and borrow/merge deletions in $O (t lo g_{t} n)$ time without cascading backward passes.
Contrast B-Trees and B+ Trees, explaining how separating router keys from doubly-linked data leaves optimizes sequential range queries.
Prove the structural isomorphism between 2-3-4 trees and Red-Black trees.

2. External Memory & The Need for Multiway Trees

The Storage Hierarchy Latency Cliff

Modern computing hardware exhibits latency disparities spanning seven orders of magnitude across the memory hierarchy:

Memory Tier	Typical Access Latency	Latency Scaled to Human Terms ( $1 ns \approx 1 s$ )	Hardware Transfer Granularity
CPU L1 / L2 Cache	$\sim 0.5 - 2 ns$	$1 - 2 seconds$	$64 bytes$ (Cache Line)
Main Memory (DRAM)	$\sim 50 - 100 ns$	$1 - 2 minutes$	$64 bytes$
NVMe Flash SSD	$\sim 10 - 25 μ s$ ( $1 0^{4} ns$ )	$\sim 3 - 7 hours$	$4 KB - 16 KB$ (Page Block)
Mechanical Hard Disk (HDD)	$\sim 5 - 10 ms$ ( $1 0^{7} ns$ )	$\sim 2 - 4 months$	$4 KB$ (Sector Block)

Because operating systems and storage controllers read and write secondary storage strictly in fixed-size blocks (typically $4 KB$ , $8 KB$ , or $16 KB$ ), fetching a single byte costs the same I/O latency as reading the entire page block.

Why Binary Search Trees Fail on External Storage

Suppose an enterprise database indexes $n = 1, 000, 000, 000$ ( $1 0^{9}$ ) records using a balanced binary search tree (AVL or Red-Black Tree):

Tree Height: $h \approx lo g_{2} (1 0^{9}) \approx 30$ levels.
In the worst case, each node resides on a different physical disk page.
A single key lookup requires 30 random page reads.
On an NVMe SSD at $20 μ s$ per read, this takes $600 μ s$ ; on an HDD at $10 ms$ per seek, this takes $300 ms$ per query!

The Multiway Solution: High Fanout, Shallow Trees

Instead of 2 children per node, let each node hold hundreds of keys, precisely matching one storage page block ( $4 KB$ ):

Suppose page size $= 4096 bytes$ , key size $= 8 bytes$ , and pointer size $= 8 bytes$ .
Each node stores $B \approx 256$ keys and $257$ child pointers.
Resulting Tree Height:

h \approx lo g_{256} (1 0^{9}) = \frac{lo g _{10} ( 1 0 ^{9} )}{lo g _{10} ( 256 )} \approx \frac{9}{2.408} \approx 3.73 ⟹ 4 levels

Searching now requires only 3 to 4 page reads—an $87%$ reduction in physical I/O!

3. B-Tree Invariants & Structural Mechanics

A B-Tree is a self-balancing search tree parameterized by a minimum degree $t \geq 2$ :

Invariant #	Invariant Rule	Formal Boundary Condition	Architectural Purpose
1	Root Capacity	The root contains between $1$ and $2 t - 1$ keys. If not a leaf, it has at least $2$ children.	Allows the tree to grow upward through root splits.
2	Internal Node Keys	Every internal node except root has at least $t - 1$ keys and at most $2 t - 1$ keys.	Guarantees at least $50%$ storage page utilization.
3	Internal Node Children	An internal node with $k$ keys has exactly $k + 1$ children (between $t$ and $2 t$ children).	Matches multiway search partitioning boundaries.
4	Key Ordering	Keys in each node are strictly sorted: $K_{1} < K_{2} < \dots < K_{k}$ .	Enables fast in-node binary search.
5	Subtree Range Invariant	For child subtrees $C_{0}, C_{1}, \dots, C_{k}$ of node $u$ : $keys (C_{0}) < K_{1} < keys (C_{1}) < \dots < K_{k} < keys (C_{k})$ .	Preserves the global multiway search invariant.
6	Uniform Leaf Depth	All leaves appear at the exact same depth $h$ .	Ensures uniform, predictable worst-case performance.

Proactive Split Insertion ( $O (t lo g_{t} n)$ )

In classical algorithms, inserting into a full leaf requires splitting that node and propagating the median key upward, which can trigger cascading splits back to the root.

CLRS formalizes Proactive Splitting: As the search algorithm descends from the root toward the target insertion leaf, whenever it encounters any node that is already full (contains exactly $2 t - 1$ keys), it splits that node immediately before descending further. Consequently, the parent is guaranteed to have space to accept the promoted median key!

Phase	Topological State	Keys in Involved Nodes	Structural Changes
Before Split	Full Child Node $Y$ ( $2 t - 1$ keys).	$Y . keys = [K_{1}, K_{2}, \dots, K_{t}, \dots, K_{2 t - 1}]$ .	$Y$ is the $i$ -th child of non-full Parent $P$ .
Split Execution	Median key $K_{t}$ is extracted.	- Median: $K_{t}$ . - Left slice: $[K_{1}, \dots, K_{t - 1}]$ . - Right slice: $[K_{t + 1}, \dots, K_{2 t - 1}]$ .	$K_{t}$ is inserted into $P$ at position $i$ . $Y$ retains the left $t - 1$ keys. A new sibling node $Z$ is allocated for the right $t - 1$ keys.
After Split	Parent $P$ has one additional key and child.	- $P$ : contains $K_{t}$ . - $Y$ : $t - 1$ keys, $t$ children. - $Z$ : $t - 1$ keys, $t$ children.	Both $Y$ and $Z$ now have room for future insertions. Invariant 2 and 6 preserved!

4. B+ Trees: The Universal Database Storage Engine Standard

While a standard B-Tree stores satellite data records in both internal router nodes and leaf nodes, the B+ Tree enforces a strict separation between routing indices and payload data:

Dimension / Layer	Internal Nodes (Router Layer)	Leaf Nodes (Data Layer)
Stored Contents	Search keys and child pointers only. Zero data payloads!	All actual data records or tuple row IDs (`RID`).
Key Duplication	Keys may be duplicated in leaves as exact data anchors.	Contains every single key present in the entire database.
Inter-Node Links	Downward child pointers only.	Linked sequentially via a Doubly-Linked List.
Query Traversal	Pure routing: Guides searches down to appropriate leaf.	Terminal points for lookups and start points for range scans.

Why B+ Trees Dominate Relational Databases (PostgreSQL, MySQL InnoDB)

Higher Branching Factor ( $B$ ):
- Because internal nodes store zero tuple data, many more index keys fit into each $4 KB$ disk page. The resulting tree is shorter, reducing disk I/O.
High-Performance Range Scans (BETWEEN A AND B):
- In a standard B-Tree, a range scan requires an in-order tree walk that jumps repeatedly between disk pages across different levels of the tree.
- In a B+ Tree, the engine performs a single binary search to find the start key leaf, then traverses the horizontal linked list of leaves linearly!
Predictable Query Latency:
- Every lookup traverses the exact same depth $h$ to reach a leaf, eliminating latency jitter.

5. Step-by-Step Dry Run State Trace: B-Tree Insertion & Node Split

Consider a B-Tree with minimum degree $t = 2$ (each node holds at most $2 t - 1 = 3$ keys and at least $t - 1 = 1$ key).
Inserting keys sequentially: $[10, 20, 30]$ into a single root node:

Step	Operation	Current Node Keys	Node Condition	Mutation / Split Action	Resulting Hierarchy
1	Insert $10$	`[10]`	Count = 1 ( $< 3$ )	Insert into sorted position.	Root: `[10]`
2	Insert $20$	`[10, 20]`	Count = 2 ( $< 3$ )	Insert into sorted position.	Root: `[10, 20]`
3	Insert $30$	`[10, 20, 30]`	Count = 3 (Node Full!)	Node is full ( $2 t - 1 = 3$ ). Root must split upon next insertion.	Root: `[10, 20, 30]`
4	Insert $25$	Needs insertion into `[10, 20, 30]`	Full Node Encountered!	Root Split Triggered: Median key $20$ promoted to become new Root!	New Root: `[20]` Left Child: `[10]` Right Child: `[30]`
5	Complete Insert $25$	Target leaf is Right Child `[30]`	Count = 1 ( $< 3$ )	Insert $25$ into right leaf: `[25, 30]`.	Root: `[20]` Left: `[10]` Right: `[25, 30]`

6. The Isomorphism Between 2-3-4 Trees and Red-Black Trees

A 2-3-4 Tree is a B-Tree of minimum degree $t = 2$ :

2-Node: 1 key, 2 children.
3-Node: 2 keys, 3 children.
4-Node: 3 keys, 4 children.

Every Red-Black Tree is structurally isomorphic to a 2-3-4 Tree:

2-3-4 Tree Node	Equivalent Red-Black Tree Subtree	Node Color Encoding
2-Node `[ B ]`	Single node `[ B ]`	`B` is `BLACK`.
3-Node `[ A │ B ]`	Parent `[ B ]` with left child `[ A ]` (or right child `[ B ]` with left child `[ A ]`)	`B` is `BLACK`, `A` is `RED`.
4-Node `[ A │ B │ C ]`	Node `[ B ]` with two children: left `[ A ]` and right `[ C ]`	Root `B` is `BLACK`, both children `A` and `C` are `RED`.

Isomorphism Consequence: When a 2-3-4 tree splits a 4-node $[A ∣ B ∣ C]$ , median key $B$ moves up. In the isomorphic Red-Black Tree, this corresponds precisely to Case 1 (Uncle Color Flip): recoloring children $A$ and $C$ to BLACK and parent $B$ to RED!

7. Asymptotic Complexity Matrix

Operation	B-Tree (Memory Keys)	B-Tree (Disk Block I/O)	B+ Tree Range Query ( $k$ items)	Binary Search Tree (Disk I/O)
Search	$O (t lo g_{t} n)$	$O (lo g_{t} n)$	$O (lo g_{t} n + k / B)$	$O (lo g_{2} n)$
Insertion	$O (t lo g_{t} n)$	$O (lo g_{t} n)$	$O (lo g_{t} n)$	$O (lo g_{2} n)$
Deletion	$O (t lo g_{t} n)$	$O (lo g_{t} n)$	$O (lo g_{t} n)$	$O (lo g_{2} n)$
Range Scan	$O (k lo g_{t} n)$	$O (k)$ random I/Os	$O (lo g_{t} n + k / B)$ sequential I/Os	$O (k lo g_{2} n)$ random I/Os

8. Common Traps, Edge Cases & Implementation Pitfalls

Underflow on Deletion (Borrow vs. Merge):
- When deleting from an internal node with $t - 1$ keys, check whether an immediate sibling has $\geq t$ keys. If so, borrow a key via parent rotation; if both siblings have $t - 1$ keys, merge the node with a sibling and drop a parent key.
Page Fragmentation in In-Memory B-Trees:
- In languages with garbage collection (JavaScript/Python/Java), allocating array objects inside nodes can induce heap fragmentation. Systems implementations in C/C++ or Rust allocate contiguous page-aligned byte buffers.
Failure to Maintain Doubly-Linked Leaf Chain:
- In B+ Trees, when a leaf splits, the next and prev pointers of the leaf chain must be updated atomically. Omitting this breaks concurrent range scans.

9. Real-World Applications & Practice Problems

Production Systems

PostgreSQL & MySQL InnoDB Storage Engines: Use B+ Trees as the default indexing structure (BTREE) for primary keys and secondary indices.
Modern Filesystems (Btrfs, XFS, APFS, NTFS): Manage filesystem directory namespaces and extent allocation maps using B-Trees.
SQLite Database: Uses B-Trees for database table organization and B+ Trees for indices.

Practice Problems

Implement B-Tree Search and Split Insertion — Implement multiway key search and proactive child split.
B+ Tree Leaf Chain Scan — Implement lower-bound binary search to leaf followed by doubly-linked list iteration.

10. References & Academic Attribution

Bayer, R., & McCreight, E. M. (1970). Organization and maintenance of large ordered indices. Boeing Scientific Research Laboratories, Report No. 20.
Comer, D. (1979). The ubiquitous B-tree. ACM Computing Surveys (CSUR), 11(2), 121–137.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 18 (B-Trees). MIT Press.