If there's one data structure that powers the modern database world, it's the B-tree. Invented by Rudolf Bayer and Edward McCreight in 1970 at Boeing Research Labs, the B-tree has become the de facto standard index structure in virtually every relational database system: PostgreSQL, MySQL, SQL Server, Oracle, SQLite, and countless others.

The B-tree's dominance isn't accidental. It was specifically designed to optimize disk I/O operations, making it ideally suited for databases where data far exceeds available memory. More than 50 years later, despite dramatic changes in storage technology, B-trees remain the optimal choice for most indexing scenarios.

In this page, we'll explore B-trees from their mathematical foundations through their practical behavior in production database systems, giving you the deep understanding needed to reason about B-tree index performance and design effective indexing strategies.

To understand why B-trees dominate database indexing, we must first understand the problem they solve: minimizing disk I/O while maintaining efficient search, insert, and delete operations.

The Memory Hierarchy Reality:

Modern computer systems have a dramatic performance gap between memory and disk:

• RAM access: ~100 nanoseconds
• SSD random read: ~100 microseconds (1,000x slower)
• HDD random read: ~10 milliseconds (100,000x slower than RAM)

When data doesn't fit in memory, database performance is dominated by disk I/O. The goal of any disk-based data structure is to minimize the number of disk reads per operation.

Why Not Binary Search Trees?

A balanced binary search tree (like an AVL tree or Red-Black tree) provides O(log₂ N) search performance. For a billion elements, that's about 30 comparisons—which sounds excellent. But there's a critical problem:

Each comparison might require a disk read.

In a binary tree, each node has only 2 children. To store 1 billion elements, you need a tree of height ~30. If each node is on a different disk page, you need 30 disk reads per lookup—that's 30 × 10ms = 300ms per search on an HDD, or about 3 queries per second.

The B-tree Solution:

B-trees solve the disk I/O problem by maximizing the fanout—the number of children per node. Instead of 2 children (binary), B-trees have hundreds or thousands of children per node.

The key insight is that a single disk read retrieves an entire disk page (typically 4KB-16KB). Rather than wasting most of that page on a single tree node with 2 children, B-trees pack as many keys and pointers as possible into each page.

With a fanout of 500:

• Height for 1 billion elements: log₅₀₀(1,000,000,000) ≈ 3.35
• Only 4 disk reads needed for any lookup
• That's a 7-8x improvement over binary trees

The Logarithmic Base Matters:

Remember that log₂(N) vs log₅₀₀(N) = log₂(N) / log₂(500) ≈ log₂(N) / 9. By increasing the fanout from 2 to 500, we reduce tree height by a factor of 9.

A B-tree of order m (also called minimum degree t in some definitions) satisfies the following properties:

Structural Properties:

1. Every node has at most m children (and thus at most m-1 keys)
2. Every non-root internal node has at least ⌈m/2⌉ children (and thus at least ⌈m/2⌉-1 keys)
3. The root has at least 2 children if it is not a leaf
4. All leaves appear at the same depth (the tree is perfectly balanced)
5. Keys within a node are sorted in ascending order

Node Structure:

Each node contains:

• n keys: k₁ < k₂ < ... < kₙ (sorted)
• n+1 child pointers: c₀, c₁, ..., cₙ (for internal nodes)
• Metadata: node type (leaf/internal), parent pointer (optional), key count

The Search Invariant:

For each key kᵢ in an internal node:

• All keys in subtree pointed to by cᵢ₋₁ are less than kᵢ
• All keys in subtree pointed to by cᵢ are greater than kᵢ

This invariant enables binary search within nodes to find the correct child pointer.

Why the Minimum Fill Requirement?

The requirement that non-root nodes be at least half-full serves critical purposes:

1. Guarantees logarithmic height: With at least ⌈m/2⌉ children per node, height is O(log_{m/2} N)
2. Bounds wasted space: At least 50% of allocated space is used
3. Enables efficient rebalancing: There's always room to borrow keys from siblings

Height Calculation:

For a B-tree of order m with N keys:

• Maximum height: log_{⌈m/2⌉}((N+1)/2)
• For m=500, N=1 billion: height ≈ 3-4

This height guarantee is what makes B-trees so powerful—regardless of the data distribution, lookups require at most 4 disk reads for billion-element indexes.

Searching a B-tree combines traversal from root to leaf with binary search within each node. The algorithm is elegant and efficient.

Search Algorithm:

BTREE_SEARCH(node, key):
    i = 0
    // Find the smallest index i where key ≤ node.keys[i]
    while i < node.n and key > node.keys[i]:
        i = i + 1
    
    // Case 1: Found exact match
    if i < node.n and key == node.keys[i]:
        return (node, i)  // Return node and position
    
    // Case 2: Not found in this node
    if node.is_leaf:
        return NOT_FOUND  // Key doesn't exist
    else:
        // Recursively search the appropriate child
        return BTREE_SEARCH(node.children[i], key)

Searching Within a Node:

The inner search (finding position i) can be done via:

• Linear search: O(m) - simple, fast for small m
• Binary search: O(log m) - better for large m

In practice, for typical B-tree orders (m < 500), linear search is often faster due to better cache behavior and simpler code.

Time Complexity Analysis:

• Disk I/O: O(log_m N) — one disk read per level
• CPU comparisons: O(m × log_m N) with linear search, O(log m × log_m N) with binary search
• Total: O(log N) with constants depending on m

Practical Performance:

In practice, B-tree search performance is dominated by disk I/O. The CPU comparisons within each node are nearly instantaneous compared to disk access. This is why we optimize for minimizing tree height, even at the cost of more comparisons per node.

Caching Effects:

The root node and upper internal nodes are accessed by every lookup. Databases keep these nodes cached in the buffer pool, often resulting in:

• Root: always in cache (100%)
• Level 1 internal nodes: usually in cache (90%+)
• Level 2 internal nodes: often in cache (50-80%)
• Leaf nodes: cache hit rate depends on access pattern

For a height-4 B-tree with good caching, a typical lookup might require only 1-2 actual disk reads, not 4.

Insertion in a B-tree is more complex than search because it must maintain all B-tree invariants, particularly the balanced height property and the minimum/maximum key constraints.

Insertion Algorithm Overview:

1. Search for the leaf node where the key should be inserted
2. If the leaf has room (< m-1 keys), insert the key in sorted position
3. If the leaf is full, split the node and propagate a key upward
4. If the split propagates to and splits the root, create a new root (tree grows taller)

The Splitting Operation:

When a node with m-1 keys needs to accept a new key:

1. Create a new sibling node
2. Take the middle key as the separator
3. Move the upper half of keys to the new sibling
4. Insert the separator and pointer to the new sibling into the parent
5. If the parent overflows, recursively split it

Root Splitting (Tree Height Increase):

When a split propagates all the way to the root and the root itself splits, the tree grows taller:

1. Split the root into two nodes
2. Create a new root containing only the median key
3. Set the new root's children as the two split halves

This is the only way a B-tree increases in height. It ensures that all paths from root to leaves remain the same length (perfect balance).

Insertion Complexity:

• Best case: Leaf has room → O(log N) to find leaf, O(1) to insert
• Worst case: Splits propagate to root → O(log N) splits, each O(m)
• Amortized: O(log N) per insertion

Page Splits and I/O:

In database terms, each split involves:

1. Reading the full node (1 I/O)
2. Writing the modified original node (1 I/O)
3. Writing the new sibling node (1 I/O)
4. Writing the parent with the new key (1 I/O)

This is 4 I/O operations per split level. In the worst case (splits to root), a single insert might trigger 4 × height = 12-16 I/O operations. However, this is rare—most inserts don't cause any splits.

Deletion in a B-tree must maintain the minimum fill constraint: non-root nodes must have at least ⌈m/2⌉-1 keys. When deletion causes underflow, the tree must be rebalanced.

Deletion Algorithm Overview:

Case 1: Key is in a leaf node

• Simply remove the key
• If the leaf now has fewer than minimum keys, rebalance

Case 2: Key is in an internal node

• Replace with predecessor (max key in left subtree) or successor (min key in right subtree)
• Delete the predecessor/successor from its leaf node (reduces to Case 1)

Rebalancing on Underflow:

When a node has too few keys after deletion:

Option A: Borrow from sibling (Rotation)

• If an adjacent sibling has more than minimum keys
• Move a key from sibling → parent → underflowed node
• Maintain B-tree properties through "rotation"

Option B: Merge with sibling

• If both siblings have exactly minimum keys
• Combine the underflowed node with a sibling
• Pull down the separator key from the parent
• Parent now has one fewer key (may trigger recursive rebalancing)

Root Shrinking (Tree Height Decrease):

If the root becomes empty after a merge (its only children merged into one), the merged node becomes the new root. This is the only way a B-tree decreases in height.

Deletion Complexity:

• Best case: Simple leaf deletion, no underflow → O(log N)
• Worst case: Merges propagate to root → O(log N) merges
• Amortized: O(log N)

Lazy Deletion in Databases:

Many database systems don't immediately perform deletion rebalancing. Instead, they use lazy deletion:

1. Mark entries as deleted (tombstone)
2. Periodically reorganize via VACUUM/OPTIMIZE
3. Rebalance during natural operations

This approach reduces immediate deletion overhead at the cost of some space inefficiency and occasional expensive cleanup operations.

While we've been discussing B-trees, virtually all database systems actually use a variant called the B+ tree. The B+ tree modifies the basic B-tree structure in ways that significantly improve database performance.

Key Differences from B-trees:

Why Databases Use B+ Trees:

1. Higher Fanout: Since internal nodes don't store data (only keys and pointers), they can fit more keys per node. Higher fanout means shorter trees, fewer disk reads, and faster lookups.

2. Efficient Range Scans: Leaf nodes are linked into a doubly-linked list. Range queries can:

• Navigate to the starting key (O(log N))
• Follow the leaf chain sequentially (O(K) for K results)

In a pure B-tree, range scans require tree traversal for each key, which is much less efficient.

3. Predictable Performance: All data accesses follow the same path length (root → internal → ... → leaf). In a B-tree, internal node hits might be faster than leaf hits, causing variable performance.

4. Easier Caching: With data only in leaves, internal nodes are purely structural. They can be cached more aggressively since they're smaller and used more frequently.

Understanding B-tree performance characteristics helps you predict query costs and design effective indexes.

Operation Complexity Summary:

Factors Affecting Real-World Performance:

1. Cache Hit Rate:

• Internal nodes are frequently accessed → high cache hit rate
• Leaf nodes have variable cache hit rate based on access pattern
• Hot data (frequently accessed) stays cached

2. Fill Factor:

• Nodes split when 100% full, leaving two ~50% full nodes
• Average fill is typically 70-80%
• FILLFACTOR parameter lets you leave room for inserts

3. Key Size:

• Larger keys = fewer keys per node = higher tree = more I/O
• VARCHAR(255) indexed → fewer keys per page than INT
• Consider key compression for text indexes

4. Index Fragmentation:

• Random inserts cause page splits, leading to fragmentation
• Fragmented indexes have worse sequential scan performance
• REINDEX/REBUILD commands defragment

The B-tree family includes several important variants optimized for specific scenarios.

B Tree:*

B* trees require nodes to be at least 2/3 full (instead of 1/2). They achieve this by redistributing keys among siblings before splitting:

• Advantage: Higher space utilization (~80% vs ~70%)
• Disadvantage: More complex insertion, potentially more I/O per insert
• Usage: Some filesystems (HFS+)

B-link Tree:

B-link trees add right-sibling pointers to internal nodes (not just leaves). This enables lock-free concurrent access:

• During modifying operations, only the affected node is locked
• Concurrent readers can follow sibling links if a node splits mid-read
• PostgreSQL uses a B-link tree variant for its B-tree indexes

Copy-on-Write B-trees (CoW-B-trees):

Instead of modifying nodes in place, CoW-B-trees create new versions of modified nodes:

• Advantage: Snapshots are free (just keep old root); crash recovery is simpler
• Disadvantage: More I/O per write; garbage collection needed
• Usage: LMDB, modern filesystems (Btrfs, ZFS)

Prefix-Compressed B-trees:

For string keys with common prefixes, prefix compression stores only the distinguishing suffix:

• Keys: 'database', 'dataframe', 'datatype', 'dataviz'
• Stored: 'database', '+frame', '+type', '+viz' (+ indicates prefix from previous)

This significantly reduces space for sorted string keys.

Write-Optimized B-trees (Bε-trees, LSM-trees):

Traditional B-trees require random I/O for each insert. Write-optimized variants batch writes:

• Bε-tree: Buffer pending modifications in internal nodes
• LSM-tree: Write to memory, merge to disk in sorted runs
• Trade-off: Worse read performance for better write performance
• Usage: RocksDB, LevelDB, Cassandra (LSM-trees)

These variants are covered in detail when we discuss NoSQL databases and write-heavy workloads.

We've explored B-tree indexes from their foundational motivation through their practical implementation in database systems. Let's consolidate the essential insights:

What's Next:

With B-tree mastery established, we'll explore an alternative index structure in the next page: Hash indexes. You'll understand when hash indexes outperform B-trees, their fundamental limitations, and why they're used sparingly despite their O(1) lookup promise.