B+ Trees & Disk-Based Indexing: Engineering High-Throughput Storage Engines — Shah Meer | Shah Meer

Why Standard In-Memory Trees Fail on Disk

Binary search trees (like AVL or Red-Black trees) exhibit optimal $O(\log_2 N)$ search complexity in theoretical memory models. However, when applied to persistent storage layers—such as SSDs or NVMe drives—they suffer from a fatal flaw: excessive tree depth leading to devastating random I/O reads.

In physical storage, data is fetched in fixed-size blocks or pages (typically 4KB to 16KB). A binary tree node containing two child pointers and a single key occupies only a tiny fraction of a 4KB block, wasting 99% of each fetched page.

---

1. The Architectural Anatomy of a B+ Tree

The B+ Tree solves this disparity through high fan-out:

Internal Routing Nodes: Contain $M$ keys and $M+1$ child pointers. They store no actual record values—only boundary routing keys.

Leaf Nodes: Contain exclusively data records or record pointers. All leaf nodes are linked sequentially via a bidirectional linked list, enabling lightning-fast range scans (SELECT WHERE age BETWEEN 20 AND 30).

text code

[ 25 | 50 | 75 ] <-- Root / Internal Page (Fan-out: 100-1000) / | | \ [10..24] [25..49] [50..74] [75..100] | <---------> | <---------> | <--- Doubly Linked Leaves

With a 4KB page size and 16-byte key-pointer pairs, an internal node can easily achieve a fan-out of 250+. A 3-level B+ Tree can index over 15 million records while requiring at most 3 page reads to locate any arbitrary record.

---

2. Cache-Line Alignment & In-Page Binary Search

In modern C++ storage engine development, maximizing CPU L1/L2 cache locality within a single B+ Tree node is as important as minimizing disk reads.

Here is a simplified layout structure for an in-memory page frame:

cpp code

#include <cstdint>
#include <algorithm>
constexpr size_t PAGE_SIZE = 4096;
constexpr size_t MAX_KEYS = (PAGE_SIZE - sizeof(uint32_t)  2) / (sizeof(int64_t) + sizeof(uint64_t));
struct alignas(64) BPlusTreeNode {
    bool is_leaf;
    uint16_t num_keys;
    int64_t keys[MAX_KEYS];
    uint64_t pointers[MAX_KEYS + 1];
// Fast branchless binary search within page keys
    int find_key_index(int64_t target_key) const {
        auto it = std::lower_bound(keys, keys + num_keys, target_key);
        return std::distance(keys, it);
    }
};

[!TIP]

Aligning node structures to 64-byte boundaries (alignas(64)) ensures that accessing neighboring keys does not trigger cache-line splits across CPU core memory buses.

---

3. Node Splitting and Merge Invariants

When an insert operation pushes a node beyond MAX_KEYS, the node must undergo a split:

Allocate a new page sibling.

Distribute keys evenly (the lower half remains in the current node; the upper half moves to the sibling).

Push the median key upward into the parent node.

If the root splits, allocate a new root page, increasing tree height by 1.

Because tree growth occurs uniformly at the root rather than at the leaves, B+ Trees guarantee strict mathematical height balancing across all search paths.

---

Conclusion

Understanding how low-level hardware constraints shape higher-level algorithmic architectures is what separates basic application coders from systems engineers. The B+ Tree remains the foundational bedrock of PostgreSQL, MySQL InnoDB, and SQLite because it directly bridges algorithmic elegance with physical machine realities.