B-Trees & B+ Trees: High-Fanout On-Disk Indexing and Page Architectures

In-memory self-balancing search trees (like AVL or Red-Black trees) maintain a binary branching factor of 2. For massive on-disk datasets spanning hundreds of gigabytes, a binary tree with millions of elements reaches a depth of 25 to 30 levels, requiring dozens of random disk I/O operations per point lookup.

Invented by Rudolf Bayer and Edward M. McCreight in 1970, the **B-Tree**—and its dominant variant, the **B+ Tree**—is a self-balancing, multi-way search tree optimized specifically for hardware block storage and page-oriented file systems. By packing hundreds or thousands of keys into fixed-size disk blocks (pages), B+ Trees achieve massive branching fanout, reducing tree height to typically 3 to 4 levels for billions of rows.

Structural Differences: B-Tree vs. B+ Tree

While both structures maintain sorted keys and balanced leaf depths, their internal anatomy differs fundamentally:

1. Standard B-Tree (Payloads in All Nodes)

Data Storage: Key-value data payloads (or tuple record pointers) are stored inside both internal routing nodes and leaf nodes.
Lookup Characteristics: If a queried key matches an entry in the root or an upper-level internal node, the search terminates immediately without descending to the leaves.
Trade-off: Because large values consume space in upper-level index pages, the branching fanout decreases significantly, increasing overall tree height.

2. Modern B+ Tree (Leaf-Only Data & Linked Leaf Chains)

Data Storage: Internal nodes store strictly routing keys and child page pointers (no record payloads). All actual data payloads (or row pointers) reside exclusively in leaf nodes.
Contiguous Leaf Chain: All leaf pages are interconnected via bidirectional horizontal pointers (`prev_leaf` and `next_leaf`), forming a continuous doubly-linked list.
High Fanout: Internal nodes fit many more keys per page, maximizing fanout (often 100 to 1,000+ children per node) and keeping tree height low ($h \le 4$).
Range Scan Performance: Range queries (`WHERE id BETWEEN 10 AND 500`) execute by descending to the first leaf node in $O(\log N)$ time, then scanning horizontally along leaf pointers with sequential page reads without revisiting upper-level index nodes.

On-Disk Page Layouts: The Slotted Page Architecture

Database engines manage storage in fixed-size blocks (typically 4 KB, 8 KB, or 16 KB) called **Pages**. Because row entries within a page can vary in size (due to variable-length types like `VARCHAR` or `TEXT`), engines organize page bytes using the **Slotted Page** layout:

Page Header: Fixed-size metadata at the beginning of the page storing the LSN, transaction visibility flags, free space boundaries, and total slot count.
Slot Array (Line Pointers): Grows downward from the header. Each slot is a small fixed-size integer array storing the exact byte offset and length of a tuple within that page.
Tuple Storage Area: Grows upward from the bottom of the page, storing raw variable-length byte payloads.
Free Space Gap: Located dynamically between the end of the slot array and the top of the tuple data, avoiding page defragmentation on record modifications.

Concurrency Control: Latch Crabbing (Coupling)

Multiple concurrent threads reading and writing to an on-disk B+ Tree must prevent race conditions and structural corruption during splits and merges without holding a global index lock. Systems use **Latch Crabbing (Coupling)**:

Read Traversal (Search)

Acquire shared (S) latch on parent -> Acquire S latch on child -> Release S latch on parent. Descend level by level until reaching the leaf.

Write Traversal (Insert / Delete)

Acquire exclusive (X) latch on root.
Descend to child and acquire X latch on child.
Check if child is **safe** (an insert is safe if the child is not full; a delete is safe if the child is above minimum occupancy).
If child is safe, release all X latches held on ancestor nodes (the crab moves forward).
If child is unsafe (may trigger a split or merge), retain ancestor latches until modifications propagate upward.

C++ Conceptual Simulation Blueprint (B+ Tree Leaf & Internal Routing)

#include <iostream>
#include <vector>
#include <algorithm>

constexpr int ORDER = 4; // Max keys per node

struct BPlusNode {
    bool isLeaf;
    std::vector<int> keys;
    std::vector<BPlusNode*> children; // Pointers to children (internal) or null
    BPlusNode* nextLeaf = nullptr;    // Horizontal linked list pointer (leaves only)

    BPlusNode(bool leaf) : isLeaf(leaf) {}
};

class BPlusTreeIndex {
private:
    BPlusNode* root;

public:
    BPlusTreeIndex() {
        root = new BPlusNode(true);
    }

    bool search(int key) const {
        BPlusNode* curr = root;
        // 1. Descend through internal routing nodes
        while (!curr->isLeaf) {
            auto it = std::upper_bound(curr->keys.begin(), curr->keys.end(), key);
            int idx = std::distance(curr->keys.begin(), it);
            curr = curr->children[idx];
        }

        // 2. Binary search within leaf node
        return std::binary_search(curr->keys.begin(), curr->keys.end(), key);
    }

    std::vector<int> rangeScan(int startKey, int endKey) const {
        std::vector<int> results;
        BPlusNode* curr = root;

        // 1. Navigate to the first leaf
        while (!curr->isLeaf) {
            auto it = std::upper_bound(curr->keys.begin(), curr->keys.end(), startKey);
            int idx = std::distance(curr->keys.begin(), it);
            curr = curr->children[idx];
        }

        // 2. Scan horizontally along linked leaf pages
        while (curr) {
            for (int k : curr->keys) {
                if (k >= startKey && k <= endKey) {
                    results.push_back(k);
                } else if (k > endKey) {
                    return results;
                }
            }
            curr = curr->nextLeaf;
        }
        return results;
    }
};

Real-World Relational Engines & Indexing Systems

MySQL InnoDB: Stores all table rows inside a primary clustered index structured as an on-disk B+ Tree (16 KB page size), where secondary indexes store secondary keys pointing to primary keys.
PostgreSQL B-Tree (nbtree): Implements Lehman-Yao B+ Tree variants with high-concurrency right-sibling pointers, allowing concurrent lookups during concurrent page splits without locking parent nodes.
SQLite Database Engine: Manages both table data (B+ Tree with 64-bit integer rowids) and secondary indexes (B-Tree mapping index keys to rowids) across database page files.
Operating System File Systems (ext4, NTFS, APFS, XFS): Indexing file extents, inode allocations, and directory hierarchies using high-fanout B+ Tree disk structures.