A binary search tree with 1 billion nodes has height ~30. Each level transition in a pointer-based tree is a potential disk seek — 5-10ms per seek. That's 150-300ms just to find one key. B-trees solve this by packing hundreds of keys per node, reducing tree height to 3-4 levels for billions of records.
Why Binary Trees Fail on Disk
The fundamental problem is the ratio between random access and sequential access on disk:
HDD: random seek ≈ 10ms, sequential read ≈ 200MB/s
SSD: random read ≈ 100μs, sequential read ≈ 3GB/s
Key insight: sequential I/O is 100-1000× faster than random I/OA binary tree stored on disk means every node access is a random read. B-trees minimize random reads by maximizing keys per node.
// Binary tree node: 1 key, 2 pointers
struct BSTNode {
int key;
struct BSTNode *left, *right;
};
// B-tree node: up to ORDER-1 keys, ORDER pointers
#define ORDER 256
struct BTreeNode {
int keys[ORDER - 1];
struct BTreeNode *children[ORDER];
int num_keys;
bool is_leaf;
};B-Tree Invariants
class BTreeNode:
def __init__(self, is_leaf=False):
self.keys = []
self.children = []
self.is_leaf = is_leaf
def is_full(self):
return len(self.keys) == ORDER - 1
def b_tree_insert(root, key):
if root.is_full():
new_root = BTreeNode()
new_root.children.append(root)
b_tree_split_child(new_root, 0)
root = new_root
b_tree_insert_nonfull(root, key)
def b_tree_split_child(parent, index):
ORDER = 256
full_node = parent.children[index]
mid = ORDER // 2 - 1
new_node = BTreeNode(is_leaf=full_node.is_leaf)
new_node.keys = full_node.keys[mid + 2:]
new_node.children = full_node.children[mid + 1:]
parent.keys.insert(index, full_node.keys[mid + 1])
parent.children.insert(index + 1, new_node)
full_node.keys = full_node.keys[:mid]
full_node.children = full_node.children[:mid + 1]B+ Trees: The Database Standard
B+ trees modify the B-tree with two critical changes:
- All data lives in leaves — internal nodes only store routing keys
- Leaves are linked — sequential scans don't need tree traversal
B-tree:
[10 | 20 | 30]
/ | | \
[1-9] [11-19] [21-29] [31+]
(data) (data) (data) (data)
B+ tree:
[10 | 20 | 30] ← routing only
/ | | \
[1-9] [11-19] [21-29] [31+] ← all data here
→→→→→→→→→→→→→→→→→→→→→→→→→ ← linked leaves// B+ tree leaf node with linked list
struct BPlusLeaf {
int keys[ORDER - 1];
Record records[ORDER - 1]; // actual data
struct BPlusLeaf *next; // linked list for range scans
int num_keys;
};
// Range query: O(log n) to find start, then O(k) sequential reads
void range_scan(BPlusLeaf *start, int low, int high) {
BPlusLeaf *current = start;
while (current) {
for (int i = 0; i < current->num_keys; i++) {
if (current->keys[i] >= low && current->keys[i] <= high) {
process(current->records[i]);
}
}
current = current->next; // sequential I/O!
}
}Page Layout and Write-Ahead Logging
B-tree nodes are stored in fixed-size pages (typically 4KB-16KB). Page splits are the expensive operation:
def btree_page_split(page, new_key, new_value):
"""Page split: allocate new page, redistribute keys, update parent."""
all_keys = page.keys + [new_key]
all_values = page.values + [new_value]
all_keys.sort()
mid = len(all_keys) // 2
new_page = allocate_page()
page.keys = all_keys[:mid]
page.values = all_values[:mid]
new_page.keys = all_keys[mid + 1:]
new_page.values = all_values[mid + 1:]
# Write-ahead log: log the split before modifying pages
wal_log.write(PageSplitRecord(page.id, new_page.id, all_keys))
# Update parent pointer
insert_key_into_parent(page.parent, all_keys[mid], new_page.id)
return new_pagetradeoff / B-Tree vs LSM-Tree for Writes
For OLTP databases with mixed read/write workloads, B+ trees remain the dominant choice because point queries and range scans are the most common operations. LSM-trees shine for write-heavy workloads like time-series data or logging.
B-trees excel at read-heavy workloads with point queries. LSM-trees (used by RocksDB, Cassandra) batch writes into sorted runs and merge later, achieving higher write throughput at the cost of read amplification.
Synthesis
B-trees and B+ trees minimize disk I/O by maximizing the branching factor at each node. B+ trees add linked leaves for efficient range scans. Every major relational database uses B+ trees as the primary index structure because they optimize for the hardware reality: sequential I/O is orders of magnitude faster than random I/O.