2-3 Trees & B-Trees — Conceptual Introduction

If you've ever used a database—and you have, whether you realized it or not—you've relied on B-trees. These remarkable structures are the backbone of virtually every database system in production today, from the SQLite database on your phone to the massive PostgreSQL clusters powering major web applications.

The B-tree isn't just another balanced tree variant. It's a purpose-built structure designed from the ground up for disk-based storage. Every design decision, from branching factor to node layout, reflects deep understanding of how magnetic and solid-state storage actually works. Understanding B-trees means understanding how databases achieve their remarkable performance.

A B-tree of order m (also called minimum degree t in some literature, where m = 2t) is a self-balancing tree that 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 (thus at least ⌈m/2⌉-1 keys)
3. The root has at least 2 children if it is not a leaf
4. All leaves are at the same depth
5. A node with k children contains exactly k-1 keys

Ordering Properties:

6. Keys within a node are stored in sorted order: k₁ < k₂ < ... < k_{j}
7. For internal nodes, child pointer Cᵢ points to a subtree containing keys between kᵢ and kᵢ₊₁

Example: B-tree of order 5

• Maximum children: 5 (so maximum keys: 4)
• Minimum children (non-root): ⌈5/2⌉ = 3 (so minimum keys: 2)
• Root minimum: 2 children or is a leaf

This means every internal node holds between 2 and 4 keys, and between 3 and 5 children. This "half-full" minimum ensures good space utilization while maintaining balance.

B-trees aren't just theoretically interesting—they're engineered to exploit how storage hardware actually works.

Understanding block-based I/O:

Storage devices (HDDs, SSDs, networked storage) transfer data in fixed-size blocks or pages, typically 4KB to 64KB. When you request any byte within a block, the entire block is read:

Request 1 byte at offset 1000:
  → System reads entire 4KB block containing offset 1000
  → Block transferred: bytes 0-4095
  → Your 1 byte extracted from the block
  → The other 4,095 bytes: wasted bandwidth (if unused)

B-tree node sizing strategy:

The key insight: size each B-tree node to exactly fill one disk block. If blocks are 4KB:

Node layout (example):
  - Node metadata: 16 bytes
  - Key count: 4 bytes
  - Keys: 8 bytes each × 500 keys = 4,000 bytes
  - Child pointers: 8 bytes each × 501 pointers ≈ 4,008 bytes
  (Total: ≈8,028 bytes → fits in two 4KB blocks, or adjust for single block)

Practical node sizing calculation:

For a 4KB block with:

• 8-byte keys
• 8-byte child pointers (or value pointers)
• 16 bytes node metadata

Available space: 4096 - 16 = 4080 bytes

Each key-pointer pair: 8 + 8 = 16 bytes Maximum pairs: 4080 ÷ 16 = 255

So order m ≈ 256 (255 keys, 256 children)

The resulting height:

For n keys with order 256:

• Height 1: up to 255 keys (root only)
• Height 2: up to 255 × 256 = 65,280 keys
• Height 3: up to ~16 million keys
• Height 4: up to ~4 billion keys

A B-tree indexing 4 billion records requires only 4 disk reads for any search!

Additional disk-friendly properties:

1. Sequential access within nodes: After loading a node, searching through its keys happens in memory—fast sequential access

2. Predictable I/O: The maximum number of disk reads is exactly the tree height, enabling precise performance prediction

3. Cache efficiency: Frequently accessed nodes (especially near the root) stay in memory buffers, further reducing disk I/O

4. Write optimization: Changes are localized to specific nodes; we rarely need to rewrite large portions of the tree

Search in a B-tree generalizes binary search tree search to handle multiple keys per node.

Algorithm:

BTreeSearch(node, target):
    if node is null:
        return NOT_FOUND
    
    // Binary search within the node's keys
    i = 0
    while i < node.keyCount and target > node.keys[i]:
        i = i + 1
    
    // Check if we found the key
    if i < node.keyCount and target == node.keys[i]:
        return (node, i)  // Found at position i in this node
    
    // If this is a leaf, key doesn't exist
    if node.isLeaf:
        return NOT_FOUND
    
    // Read child from disk if not in memory
    DiskRead(node.children[i])
    
    // Recursively search in appropriate child
    return BTreeSearch(node.children[i], target)

Complexity Analysis:

• Disk I/O: O(log_m n) = O(height) block reads

  • Each level requires one disk read
  • Height is O(log_m n) ≈ O(log n / log m)
  • For m = 256, this is roughly log₂ n / 8

• CPU operations: O(m × height) = O(m × log_m n)

  • At each node, we search among up to m-1 keys
  • With binary search within nodes: O(log(m) × log_m n) = O(log n)

• Overall: O(log n) CPU operations, O(log_m n) disk I/Os

  • The disk I/O is the dominant cost
  • For large m, log_m n is much smaller than log₂ n

B-tree insertion follows the same principles as 2-3 tree insertion but handles larger nodes and uses proactive splitting to simplify implementation.

Core Principle:

Keys are always inserted into leaf nodes. If a node becomes overfull (m keys), it splits into two nodes with ⌈m/2⌉-1 keys each, promoting the median key to the parent.

Two approaches: Reactive vs. Proactive Splitting

Proactive Insertion Algorithm (preferred for disk):

BTreeInsert(tree, key):
    root = tree.root
    
    // If root is full, split it first (creates new root)
    if root.keyCount == m - 1:
        newRoot = AllocateNode()
        newRoot.isLeaf = false
        newRoot.children[0] = root
        SplitChild(newRoot, 0, root)
        tree.root = newRoot
        InsertNonFull(newRoot, key)
    else:
        InsertNonFull(root, key)

InsertNonFull(node, key):
    i = node.keyCount - 1
    
    if node.isLeaf:
        // Make room and insert key
        while i >= 0 and key < node.keys[i]:
            node.keys[i + 1] = node.keys[i]
            i = i - 1
        node.keys[i + 1] = key
        node.keyCount = node.keyCount + 1
        DiskWrite(node)
    else:
        // Find child to descend into
        while i >= 0 and key < node.keys[i]:
            i = i - 1
        i = i + 1
        
        DiskRead(node.children[i])
        
        // Proactively split if child is full
        if node.children[i].keyCount == m - 1:
            SplitChild(node, i, node.children[i])
            if key > node.keys[i]:
                i = i + 1
        
        InsertNonFull(node.children[i], key)

The Split Operation:

SplitChild(parent, childIndex, fullChild):
    // fullChild has m-1 keys, we split into two nodes with (m-1)/2 keys each
    medianIndex = floor((m - 1) / 2)  // index of median key
    
    // Create new sibling node
    newNode = AllocateNode()
    newNode.isLeaf = fullChild.isLeaf
    
    // Move upper half of keys to new node
    newNode.keyCount = floor((m - 1) / 2)
    for j = 0 to newNode.keyCount - 1:
        newNode.keys[j] = fullChild.keys[medianIndex + 1 + j]
    
    // If not leaf, move corresponding children
    if not fullChild.isLeaf:
        for j = 0 to newNode.keyCount:
            newNode.children[j] = fullChild.children[medianIndex + 1 + j]
    
    // Adjust fullChild to keep only lower half
    fullChild.keyCount = medianIndex  // keeps keys 0 to medianIndex-1
    
    // Make room in parent for the promoted key and new child
    for j = parent.keyCount downto childIndex + 1:
        parent.children[j + 1] = parent.children[j]
    parent.children[childIndex + 1] = newNode
    
    for j = parent.keyCount - 1 downto childIndex:
        parent.keys[j + 1] = parent.keys[j]
    parent.keys[childIndex] = fullChild.keys[medianIndex]  // promote median
    parent.keyCount = parent.keyCount + 1
    
    DiskWrite(fullChild)
    DiskWrite(newNode)
    DiskWrite(parent)

Deletion is more complex than insertion because we must handle underflow while maintaining the minimum key requirement.

Cases to handle:

1. Key is in a leaf node: Remove directly (may cause underflow)
2. Key is in an internal node: Replace with predecessor or successor, then delete that

Handling underflow (node has fewer than ⌈m/2⌉-1 keys):

1. Borrow from sibling: If an adjacent sibling has extra keys, rotate through the parent
2. Merge with sibling: If no sibling can lend, merge with a sibling (pulling down a parent key)

Case 1: Key k in leaf node x

Simply remove k from x.
If x now has too few keys:
    If immediate sibling has spare keys:
        Borrow one key via rotation through parent
    Else:
        Merge x with a sibling, pulling down separator from parent

Case 2: Key k in internal node x

Let y = child preceding k, z = child following k

Case 2a: If y has at least ⌈m/2⌉ keys:
    Find predecessor k' of k (rightmost key in y's subtree)
    Replace k with k' in x
    Recursively delete k' from y's subtree

Case 2b: If z has at least ⌈m/2⌉ keys:
    Find successor k' of k (leftmost key in z's subtree)
    Replace k with k' in x
    Recursively delete k' from z's subtree

Case 2c: If both y and z have exactly ⌈m/2⌉-1 keys:
    Merge k and all of z into y
    Child y now contains k and all keys from z
    Recursively delete k from y

Proactive approach (ensuring minimum keys during descent):

Just as proactive splitting prevents backtracking during insertion, we can ensure nodes have at least t keys (where t = ⌈m/2⌉) during descent:

BTreeDelete(node, key):
    // Ensure node has at least t keys (unless root)
    i = FindKeyPosition(node, key)
    
    if KeyFoundAt(node, i):
        if node.isLeaf:
            RemoveFromLeaf(node, i)
        else:
            DeleteFromInternalNode(node, i)
    else:
        if node.isLeaf:
            // Key not in tree
            return NOT_FOUND
        
        // Ensure child has enough keys before descending
        EnsureMinimumKeys(node, i)
        
        // Recurse into child
        BTreeDelete(node.children[i], key)

EnsureMinimumKeys(node, childIndex):
    child = node.children[childIndex]
    
    if child.keyCount >= t:
        return  // Already has enough keys
    
    // Try borrowing from left sibling
    if childIndex > 0 and node.children[childIndex - 1].keyCount >= t:
        BorrowFromLeft(node, childIndex)
    // Try borrowing from right sibling
    else if childIndex < node.keyCount and node.children[childIndex + 1].keyCount >= t:
        BorrowFromRight(node, childIndex)
    // Must merge
    else:
        if childIndex > 0:
            MergeWithLeft(node, childIndex)
        else:
            MergeWithRight(node, childIndex)

While B-trees are powerful, most database systems actually use a variant called the B+ tree. This modification optimizes for the specific access patterns databases need.

Key differences:

1. All data in leaves: B+ trees store actual data (or pointers to data) only in leaf nodes. Internal nodes contain only keys for navigation.

2. Leaf nodes are linked: Leaves form a linked list, enabling efficient range scans.

3. Duplicated keys: Keys from internal nodes are repeated in leaves (they guide navigation but the actual key-value pairs are in leaves).

4. Higher branching factor: Since internal nodes don't store values, they can fit more keys per block.

Why B+ trees dominate databases:

1. Range queries: With linked leaves, scanning all records from 30 to 60 just follows leaf links—no tree traversal needed after finding 30.

2. Better cache utilization: Internal nodes (more frequently accessed) contain only keys and fit more easily in memory. Data-heavy leaves can stay on disk.

3. Consistent access patterns: Every search traverses to a leaf, making performance predictable.

4. Full scans: Scanning the entire table just traverses the leaf linked list—no internal nodes needed.

5. Simpler deletion: Deleting from a leaf doesn't affect navigation (internal keys can remain as "signpost" values).

Let's consolidate the time and space complexity for B-tree operations. For a B-tree with n keys and order m:

Space complexity:

• Nodes: O(n/m) nodes (each leaf holds up to m-1 keys, so ~n/(m/2) leaves)
• Height: O(log_m n) levels
• Per-node space: O(m) for keys and children
• Total space: O(n) keys + O(n) child pointers = O(n)

Space utilization:

B-trees guarantee at least 50% space utilization (minimum ⌈m/2⌉ children). In practice, with random insertions, utilization is typically around 69% (ln 2 = 0.693). Bulk loading from sorted data can achieve near-100% utilization.

Implementing a production B-tree involves numerous practical considerations beyond the core algorithms:

1. Node layout and serialization:

Typical node layout on disk:
┌─────────────────────────────────────────────────┐
│ Header (16 bytes)                               │
│   - Node type (leaf/internal)                   │
│   - Key count                                   │
│   - Pointer to parent (optional)                │
├─────────────────────────────────────────────────┤
│ Keys array (variable)                           │
│   key[0], key[1], ..., key[n-1]                 │
├─────────────────────────────────────────────────┤
│ Children/Values array (variable)                │
│   - For internal: child node pointers           │
│   - For leaves: value data or value pointers    │
├─────────────────────────────────────────────────┤
│ Leaf: next/prev leaf pointers (B+ trees)        │
└─────────────────────────────────────────────────┘

2. Buffer pool management:

Production systems don't read/write directly to disk. A buffer pool caches frequently-used pages in memory:

• Hot nodes (especially near the root) stay in memory
• LRU or clock algorithms evict cold pages
• Dirty pages are written back asynchronously
• Pinning prevents eviction during operations

3. Concurrency control:

Multiple threads accessing the B-tree need coordination:

• Lock coupling (crabbing): Hold lock on parent while locking child, then release parent
• Optimistic concurrency: Assume no conflicts, validate and retry if wrong
• B-link trees: Add sibling pointers to handle concurrent splits gracefully

4. Recovery and durability:

Database B-trees must survive crashes:

• Write-ahead logging (WAL): Log changes before applying them
• Checkpointing: Periodically flush all dirty pages
• Recovery: Replay log from last checkpoint after crash
• Page LSNs: Track which log records have been applied to each page

5. Variable-length keys:

Not all keys are fixed-size (e.g., strings):

• Slot directory: Store offsets to key locations
• Key compression: Prefix compression for strings with common prefixes
• Overflow pages: For very large keys that don't fit in a node

6. Bulk loading optimization:

When building a B-tree from sorted data, direct construction is faster than repeated inserts:

BulkLoad(sorted_data):
    1. Fill leaf pages sequentially (near-100% utilization)
    2. Create internal pages bottom-up, one level at a time
    3. No rebalancing needed—tree is perfectly balanced by construction

This achieves O(n/B) I/O complexity versus O(n × log n) for n insertions.

We've explored B-trees in depth, understanding their structure, operations, and practical considerations. Let's consolidate the key insights:

What's next:

In the final page of this module, we'll connect B-trees to real database systems, exploring how PostgreSQL, MySQL, and other systems use B-trees for indexing, why database designers choose B-trees over alternatives, and how to design effective indexes using your B-tree knowledge.