B/B+ Tree External-Memory Search

Why B/B+ Tree External-Memory Search Matters

A dictionary with millions of entries should not require a separate storage read for every binary-tree comparison. B-trees and B+ trees place many ordered keys and child pointers in one page. One page read can therefore choose among many subtrees, keeping the number of storage levels small.

The key distinction is where records live. In a classical B-tree, an internal key can own a record, so equality may finish the search before a leaf. In a B+ tree, internal keys are routing separators; actual records live in leaves. Linked B+ leaves then support ordered range scans after one initial descent.

This lesson implements point search for both structures and an inclusive B+ range query. Static builders create valid balanced trees from sorted unique keys, using an explicit logical byte layout. An LRU buffer-pool simulator distinguishes page visits, cache hits, and page reads, exposing why a short warm path can cost no transfers while a repeated longer path can still miss.

The code is a read-only search laboratory, not an insertion/deletion engine. It includes misses, separator equality, root/leaf cases, range boundaries, cache eviction, and identical Python, C++, and Java output. The prior tree and sorting lessons provide ordering and balancing basics; here the focus is routing correctness and external-memory cost.

Core Concepts and Terminology

A page is the unit transferred between simulated storage and the buffer pool. Let $P$ be bytes per page and $C$ the number of LRU cache frames, each holding one page. The modeled resident-page capacity is $CP$ bytes per index. Page IDs identify nodes; the root ID is known metadata, so no extra header-page read is charged to discover it.

For a concrete logical layout, use a $16$-byte node header, $8$-byte keys, $8$-byte values, and $8$-byte child/leaf pointers. Values are stored as $10k$ for key $k$ so lookup results are easy to verify. These are conceptual encoded widths, not Python object sizes or native C++/Java array layouts.

B-tree convention. A node with $m$ keys has $m$ corresponding values and, if internal, $m+1$ children. An internal page uses $$ 16+16m+8(m+1)=24+24m $$ bytes. Choose minimum degree $t=\lfloor P/48\rfloor$, so at most $2t-1$ keys and $2t$ children fit. Nonroot nodes contain at least $t-1$ keys; the root has a special lower bound. All leaves have equal depth. A common degree is used for both leaf and internal nodes, even though a B-tree leaf has no child pointers and could physically hold more records under a different design.

B+ convention. Internal nodes contain separators and children, with no values. A page with $f$ children uses $16+8(f-1)+8f=8+16f$ bytes. A linked leaf with $\ell$ key/value records uses $24+16\ell$ bytes. Therefore $$ F=\left\lfloor\frac{P-8}{16}\right\rfloor, \qquad L=\left\lfloor\frac{P-24}{16}\right\rfloor $$ are maximum internal fanout and leaf capacity. Nonroot internal nodes have at least $\lceil F/2\rceil$ children, and nonroot leaves have at least $\lceil L/2\rceil$ records. The bulk builder balances the last groups to respect those minima. A leaf root may contain fewer records; an empty index has no root page.

Every B+ separator is the minimum key of its right child subtree. With separators $s_0,\ldots,s_{m-1}$, child intervals are $$ (-\infty,s_0),\ [s_0,s_1),\ldots,\ [s_{m-1},+\infty). $$ Equality must go right: choose the number of separators at most the query key, an upper-bound search. At the final leaf, a lower-bound search finds the first key at least the query. In a B-tree, a lower bound instead identifies either an internal record equal to the query or the child interval containing it.

Cache accounting. Every fetch is one logical visit. A resident page gives a hit and moves to the most-recent end of the LRU order. A missing page gives one read, evicting the least-recent page if all $C$ frames are occupied. No pages are pinned and no updates occur. Search writes are zero. Static layout construction is an uncounted preload, representing an index already on storage; index-building I/O is not measured.

With $P=96$, the B-tree has $t=2$, at most three keys/four children per node. The B+ tree has $F=5$ and $L=4$. With $C=2$, each index models $192$ resident bytes. The sample uses two independent pools, one per tree, and sums their reads; it is not one shared two-frame pool.

How B/B+ Tree External-Memory Search Works, Step by Step

1. Prepare a valid static index. Supply strictly increasing unique keys. The teaching API accepts at most $4096$ keys between $-10^6$ and $10^6$, page sizes from $96$ to $1024$ bytes in multiples of eight, and $1$ through $16$ frames. Its builders respect page capacity, minimum occupancy, child ordering, equal leaf depth, and the B+ separator/leaf-link rules. These bounds simplify experiments; they are not restrictions of the general data structures.

2. Start at the root ID. An empty index returns no records without visiting a page. Otherwise request the root through the pool. Count a hit or a one-page read, update LRU order, and record the visit in the query path.

3. Apply the correct routing rule. In a B-tree, compute the lower-bound slot. If that key equals the target, return its stored value immediately, even in an internal node. If no equal key exists and the node is internal, follow the child at that slot. At a leaf, absence means the key is not present.

In a B+ internal node, compute the upper-bound child index and descend. Do not return merely because the query equals a separator: this page has no associated record value. The separator only identifies the correct interval. The diagram below shows equality at separator twenty-seven.

4. Confirm at the B+ leaf. Compute a lower bound in the leaf keys. Return the stored value only when that slot is within the page and equals the target. Otherwise report absence. Every nonempty B+ point search in this implementation reaches a leaf, for both hits and misses.

5. Extend to an inclusive range. For $[a,b]$, first descend using $a$ under the same B+ routing rule. Begin at the first leaf key at least $a$ and emit key/value records through $b$. Follow next-leaf links when the current leaf is exhausted. Stop immediately after emitting key $b$, on seeing a key greater than $b$, or when there is no next leaf. The initial root descent is performed once, not once per record.

6. Keep the pool across queries. Each query returns its own read/hit deltas and complete visit path. Cache contents persist between queries. Calling pool.clear() removes residents and resets counters to make a cold experiment. LRU may evict the root during a long range scan; the root is not implicitly pinned or free.

Only the current page needs inspection during routing; remember a child/page ID before requesting the next node. The simulator returns a view into immutable host-backed page data, with logical residency tracked by the pool. Actual page bytes, pinning, and concurrency would need a real buffer manager.

flowchart TD
    A["Validate point key or B+ range"] --> B{"Empty index?"}
    B -->|Yes| Z["Return empty result with zero visits"]
    B -->|No| C["Fetch root: hit or one page read"]
    C --> D{"Internal page?"}
    D -->|Yes| E{"B+ tree?"}
    E -->|Yes| F["Upper bound chooses child; equality goes right"]
    E -->|No| G{"Lower-bound key equals target?"}
    G -->|Yes| Y["Return internal B-tree record"]
    G -->|No| H["Choose lower-bound child"]
    F --> I["Fetch selected child through pool"]
    H --> I
    I --> D
    D -->|No| J{"Point query?"}
    J -->|Yes| K["Lower bound confirms leaf hit or absence"]
    J -->|No| L["Emit leaf records within inclusive range"]
    L --> M{"Need another leaf?"}
    M -->|Yes| N["Fetch next-leaf page through pool"]
    N --> L
    M -->|No| O["Return records, visits, reads, and hits"]
    K --> O
    Y --> O

Worked Example with a Full Trace

Use keys $[3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51]$, with stored value $10k$ at key $k$. Set $P=96$ and $C=2$ for each independent index pool. Both pools begin empty.

Complete B-tree layout. The bulk builder produces nine pages and three levels. Each internal key below owns its stored value.

• Page 0: leaf keys $[3,6]$.
• Page 1: leaf keys $[12,15]$.
• Page 2: leaf keys $[21,24]$.
• Page 3: internal keys $[9,18]$, children $[0,1,2]$.
• Page 4: leaf keys $[30,33]$.
• Page 5: leaf keys $[39,42]$.
• Page 6: leaf keys $[48,51]$.
• Page 7: internal keys $[36,45]$, children $[4,5,6]$.
• Page 8: root key $[27]$, children $[3,7]$.

Complete B+ layout. There are six pages and two levels. Only leaves store values; the root's keys are routing copies.

• Page 0: leaf $[3,6,9,12]$, next $1$.
• Page 1: leaf $[15,18,21,24]$, next $2$.
• Page 2: leaf $[27,30,33]$, next $3$.
• Page 3: leaf $[36,39,42]$, next $4$.
• Page 4: leaf $[45,48,51]$, next $-1$ (end).
• Page 5: root separators $[15,27,36,45]$, children $[0,1,2,3,4]$.

A full B+ root uses $16+4\cdot8+5\cdot8=88$ bytes; a four-record linked leaf uses $24+4\cdot16=88$ bytes. Both fit the $96$-byte page. The B-tree's two-key internal pages use $16+2\cdot16+3\cdot8=72$ bytes. Page IDs are local to their own index: B-tree page 5 is unrelated to B+ page 5.

Query 1: B-tree get(27). Fetch root page 8: miss, cache $[8]$. Its lower-bound slot is zero and the key matches. Return stored $270$ without descending. Path $[8]$; reads $1$, hits $0$.

Query 2: B-tree get(33). Fetch page 8: hit, still $[8]$. Lower-bound search compares root key $27\lt33$, returns slot one, and selects page 7. Fetch 7: miss, cache $[8,7]$. In its keys $[36,45]$, binary search checks middle key $45$, then $36$, giving slot zero. Follow page 4. Fetch 4: miss, evict 8, cache $[7,4]$. Its keys are $[30,33]$; lower-bound search checks $33$, then $30$, giving slot one. Return $330$. Path $[8,7,4]$; reads $2$, hits $1$.

Query 3: repeat B-tree get(33). Start at $[7,4]$. Fetch 8: miss, evict 7 → $[4,8]$. Fetch 7: miss, evict 4 → $[8,7]$. Fetch 4: miss, evict 8 → $[7,4]$. The same record $330$ is returned, but every visit misses: reads $3$, hits $0$. Repetition alone does not make a path fit in cache.

Query 4: B+ get(27). Its separate pool is cold. Fetch root page 5: miss → $[5]$. Upper-bound binary search in $[15,27,36,45]$ checks $36\gt27$ and then $27\le27$, selecting child two. Fetch leaf 2: miss → $[5,2]$. Lower bound in $[27,30,33]$ checks $30$ and $27$, returning slot zero; return stored $270$. Path $[5,2]$; reads $2$, hits $0$. The root's separator match did not itself return a record.

Query 5: B+ get(33). Fetch 5: hit → $[2,5]$. Upper bound again selects child two. Fetch 2: hit → $[5,2]$. Leaf lower bound is slot two; return $330$. Reads $0$, hits $2$.

Query 6: B+ get(34). The same pages hit in the same order and leave cache $[5,2]$. Root routing still chooses child two; leaf lower bound is slot three, past its end. Return absence, with reads $0$ and hits $2$. A failed lookup can also be entirely cached.

Query 7: B+ range(21,45), inclusive. Start at cache $[5,2]$.

1. Fetch root 5: hit → $[2,5]$. Upper bound at $21$ selects child one.
2. Fetch leaf 1: miss, evict 2 → $[5,1]$. Lower bound at $21$ is slot two. Emit $21,24$, with their stored values.
3. Follow next to leaf 2: miss, evict 5 → $[1,2]$. Emit $27,30,33$.
4. Follow next to leaf 3: miss, evict 1 → $[2,3]$. Emit $36,39,42$.
5. Follow next to leaf 4: miss, evict 2 → $[3,4]$. Emit $45$ and stop at the inclusive high endpoint; do not emit $48$ or $51$.

The range returns nine records with keys $[21,24,27,30,33,36,39,42,45]$, path $[5,1,2,3,4]$, reads $4$, and hits $1$. It descends once and then uses the leaf chain. The root has been evicted by the end.

Totals. B-tree queries use six reads and one hit; B+ queries use six reads and five hits. Across both independent pools, eighteen logical visits equal twelve page reads plus six hits. Query transfers are twelve pages, or $12\cdot96=1152$ logical bytes, with zero writes. Preloading the trees is outside these totals.

Implementation in Python, C++, and Java

Each panel is standalone. Save Python as main.py and run python3 main.py. Save C++ as main.cpp and compile with g++ -std=c++17 -O2 main.cpp -o tree-search. Save Java as Main.java and run javac Main.java followed by java Main. Python 3.7 or newer supplies dataclasses; the C++ panel targets C++17; Java uses ordinary classes.

Construct Index(keys, page_bytes, frames, plus) in Python/C++, or new Index(keys, pageBytes, frames, plus) in Java. The boolean plus selects B+ when true and B-tree when false. Supply a Python list, C++ vector<int>, or Java int[]; null/nonsequence inputs are outside the contract. Keys must be strictly increasing and unique, and the builders do not mutate them. Each key stores value $10k$; this is an illustrative payload chosen during construction, not a value recomputed by search.

Both modes expose point(key). B+ mode also exposes range_query(lo, hi) in Python/C++ and rangeQuery(lo, hi) in Java. The range is inclusive. Each query returns a list of stored key/value records, a path of every page visit, and read/hit deltas. Absence is an empty list, so zero and negative payloads remain ordinary valid data. pool.clear() empties that index's cache and resets its counters without changing the tree.

Invalid page size/frame parameters raise PARAMETER; more than $4096$ keys raises SIZE; a key outside the declared range raises VALUE; duplicates or descending adjacent keys raise ORDER. Parameters, size, all values, then order are checked in that sequence. Point queries validate their key before any fetch. A range on B-tree mode raises MODE; B+ range endpoints are validated before RANGE rejects reversed bounds. Invalid queries do not change cache state. Python additionally checks exact integer types and an exact boolean mode, rejecting booleans/floats used as keys or integer parameters.

Static layout preparation. The B-tree builder chooses the smallest height whose maximum capacity can hold all keys, then allocates feasible child subtree sizes and consumes the sorted keys in order. The B+ builder balances records across leaves, links those leaves, and builds balanced internal layers with right-subtree minimum separators. These are fixture/bulk-layout builders for read-only search; there is no insertion, split, deletion, or crash-recovery implementation.

Page and cache model. Disk.add checks the conceptual encoded byte size of every generated node. Construction is uncounted preload. Pool.fetch is the only query page-access path; LRU residency metadata determines whether that fetch counts a hit or one $P$-byte read. Python uses OrderedDict, C++ uses a list plus hash map, and Java uses access-ordered LinkedHashMap. No root is pinned and no background writes occur.

Simulated disk nodes are stored in host RAM. The cache tracks logical resident page IDs rather than allocating and serializing actual page bytes; record/path result arrays and builder metadata are also outside the $CP$ cache budget. The program is a page-transfer simulator, not a real memory-capped storage engine. Actual file reads, byte serialization, page guards, and pin/unpin lifetimes would replace these abstract accesses. Inline stored values require no extra table-page read in this model; an index storing record IDs could require additional row fetches.

from dataclasses import dataclass
from collections import OrderedDict
from bisect import bisect_left, bisect_right


@dataclass(frozen=True)
class Node:
    keys: tuple
    values: tuple
    children: tuple = ()
    next_leaf: int = -1


@dataclass
class Query:
    records: list
    path: list
    reads: int
    hits: int


class Disk:
    def __init__(self, page_bytes, plus):
        self.page_bytes, self.plus = page_bytes, plus
        self.pages = []

    def add(self, node):
        if self.plus:
            size = (24 + 16 * len(node.keys) if not node.children else
                    16 + 8 * len(node.keys) + 8 * len(node.children))
        else:
            size = 16 + 16 * len(node.keys) + 8 * len(node.children)
        assert size <= self.page_bytes
        page = len(self.pages)
        self.pages.append(node)
        return page


class Pool:
    def __init__(self, disk, frames):
        self.disk, self.frames = disk, frames
        self.lru = OrderedDict()
        self.reads = self.hits = 0

    def fetch(self, page):
        if page in self.lru:
            self.hits += 1
            self.lru.move_to_end(page)
        else:
            self.reads += 1
            if len(self.lru) == self.frames:
                self.lru.popitem(last=False)
            self.lru[page] = None
        return self.disk.pages[page]

    def clear(self):
        self.lru.clear()
        self.reads = self.hits = 0


def balanced_sizes(n, groups):
    return [n // groups + (i < n % groups) for i in range(groups)]


def check_key(key):
    if type(key) is not int or not -1000000 <= key <= 1000000:
        raise ValueError("VALUE")


class Index:
    def __init__(self, keys, page_bytes=96, frames=2, plus=True):
        if (type(page_bytes) is not int or type(frames) is not int
                or type(plus) is not bool):
            raise ValueError("PARAMETER")
        if not (96 <= page_bytes <= 1024 and page_bytes % 8 == 0 and 1 <= frames <= 16):
            raise ValueError("PARAMETER")
        if len(keys) > 4096:
            raise ValueError("SIZE")
        for key in keys:
            check_key(key)
        if any(keys[i] >= keys[i + 1] for i in range(len(keys) - 1)):
            raise ValueError("ORDER")
        self.plus = plus
        self.disk = Disk(page_bytes, plus)
        self.pool = Pool(self.disk, frames)
        self.t = ((page_bytes - 24) // 24 + 1) // 2
        self.leaf_capacity = (page_bytes - 24) // 16
        self.fanout = (page_bytes - 8) // 16
        self.root, self.levels = -1, 0
        if not keys:
            return
        if plus:
            self._build_plus(keys)
        else:
            self._build_b(keys)

    def _build_b(self, keys):
        t = self.t
        height = 0
        while (2 * t) ** (height + 1) - 1 < len(keys):
            height += 1
        cursor = 0

        def build(n, h, root):
            nonlocal cursor
            if h == 0:
                data = tuple(keys[cursor:cursor + n])
                cursor += n
                return self.disk.add(Node(data, tuple(k * 10 for k in data)))
            low, high = t ** h - 1, (2 * t) ** h - 1
            count = next(c for c in range(2 if root else t, 2 * t + 1)
                         if c - 1 + c * low <= n <= c - 1 + c * high)
            sizes = balanced_sizes(n - count + 1, count)
            separators, children = [], []
            for j, size in enumerate(sizes):
                children.append(build(size, h - 1, False))
                if j + 1 < count:
                    separators.append(keys[cursor])
                    cursor += 1
            return self.disk.add(Node(tuple(separators), tuple(k * 10 for k in separators),
                                      tuple(children)))
        self.root = build(len(keys), height, True)
        self.levels = height + 1
        assert cursor == len(keys)

    def _build_plus(self, keys):
        groups = (len(keys) + self.leaf_capacity - 1) // self.leaf_capacity
        layer = []
        start = 0
        for i, size in enumerate(balanced_sizes(len(keys), groups)):
            data = tuple(keys[start:start + size])
            page = self.disk.add(Node(data, tuple(k * 10 for k in data), (),
                                      i + 1 if i + 1 < groups else -1))
            layer.append((page, data[0]))
            start += size
        self.levels = 1
        while len(layer) > 1:
            groups = (len(layer) + self.fanout - 1) // self.fanout
            next_layer, start = [], 0
            for size in balanced_sizes(len(layer), groups):
                group = layer[start:start + size]
                page = self.disk.add(Node(tuple(v for p, v in group[1:]), (),
                                          tuple(p for p, v in group)))
                next_layer.append((page, group[0][1]))
                start += size
            layer = next_layer
            self.levels += 1
        self.root = layer[0][0]

    def point(self, key):
        check_key(key)
        before_r, before_h = self.pool.reads, self.pool.hits
        path, records = [], []
        page = self.root
        while page != -1:
            path.append(page)
            node = self.pool.fetch(page)
            if self.plus and node.children:
                page = node.children[bisect_right(node.keys, key)]
                continue
            j = bisect_left(node.keys, key)
            if j < len(node.keys) and node.keys[j] == key:
                records.append((key, node.values[j]))
                break
            if not node.children:
                break
            page = node.children[j]
        return Query(records, path, self.pool.reads - before_r, self.pool.hits - before_h)

    def range_query(self, lo, hi):
        if not self.plus:
            raise ValueError("MODE")
        check_key(lo)
        check_key(hi)
        if lo > hi:
            raise ValueError("RANGE")
        before_r, before_h = self.pool.reads, self.pool.hits
        path, records = [], []
        page = self.root
        while page != -1:
            path.append(page)
            node = self.pool.fetch(page)
            if node.children:
                page = node.children[bisect_right(node.keys, lo)]
                continue
            stop = False
            for j in range(bisect_left(node.keys, lo), len(node.keys)):
                key = node.keys[j]
                if key > hi:
                    stop = True
                    break
                records.append((key, node.values[j]))
                if key == hi:
                    stop = True
                    break
            if stop:
                break
            page = node.next_leaf
        return Query(records, path, self.pool.reads - before_r, self.pool.hits - before_h)


def show(label, query):
    records = "[" + ",".join(f"{k}:{v}" for k, v in query.records) + "]"
    path = "[" + ",".join(map(str, query.path)) + "]"
    print(f"{label} records={records} path={path} reads={query.reads} hits={query.hits}")


def main():
    keys = list(range(3, 52, 3))
    b = Index(keys, 96, 2, False)
    plus = Index(keys, 96, 2, True)
    print("page_bytes=96 cache_frames=2")
    print(f"B t={b.t} pages={len(b.disk.pages)} root={b.root} levels={b.levels}")
    print(f"B+ leaf_capacity={plus.leaf_capacity} fanout={plus.fanout} "
          f"pages={len(plus.disk.pages)} root={plus.root} levels={plus.levels}")
    for key in [27, 33, 33]:
        show(f"B get({key})", b.point(key))
    for key in [27, 33, 34]:
        show(f"B+ get({key})", plus.point(key))
    show("B+ range(21,45)", plus.range_query(21, 45))
    reads = b.pool.reads + plus.pool.reads
    hits = b.pool.hits + plus.pool.hits
    print(f"totals reads={reads} hits={hits} transfers={reads} writes=0")


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cassert>
#include <iostream>
#include <list>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;

struct Node {
    vector<int> keys, values, children;
    int next_leaf = -1;
};
struct Query {
    vector<pair<int,int>> records;
    vector<int> path;
    int reads, hits;
};
struct Disk {
    int page_bytes;
    bool plus;
    vector<Node> pages;
    Disk(int p, bool b) : page_bytes(p), plus(b) {}
    int add(Node node) {
        int n = static_cast<int>(node.keys.size()), c = static_cast<int>(node.children.size());
        int size = plus ? (c ? 16 + 8 * n + 8 * c : 24 + 16 * n) : 16 + 16 * n + 8 * c;
        assert(size <= page_bytes);
        int id = static_cast<int>(pages.size()); pages.push_back(move(node)); return id;
    }
};
struct Pool {
    Disk& disk;
    int frames, reads = 0, hits = 0;
    list<int> lru;
    unordered_map<int,list<int>::iterator> resident;
    Pool(Disk& d, int f) : disk(d), frames(f) {}
    const Node& fetch(int page) {
        auto it = resident.find(page);
        if (it != resident.end()) {
            ++hits; lru.splice(lru.end(), lru, it->second);
        } else {
            ++reads;
            if (static_cast<int>(lru.size()) == frames) {
                resident.erase(lru.front()); lru.pop_front();
            }
            lru.push_back(page); resident[page] = prev(lru.end());
        }
        return disk.pages[page];
    }
    void clear() { lru.clear(); resident.clear(); reads = hits = 0; }
};
vector<int> balanced_sizes(int n, int groups) {
    vector<int> sizes;
    for (int i = 0; i < groups; ++i) sizes.push_back(n / groups + (i < n % groups));
    return sizes;
}
vector<int> scaled(const vector<int>& keys) {
    vector<int> values;
    for (int k : keys) values.push_back(k * 10);
    return values;
}
int power(int base, int exponent) {
    int result = 1;
    while (exponent--) result *= base;
    return result;
}
void check_key(int key) {
    if (key < -1000000 || key > 1000000) throw invalid_argument("VALUE");
}
struct Index {
    bool plus;
    Disk disk;
    Pool pool;
    int t, leaf_capacity, fanout, root = -1, levels = 0;
    Index(const vector<int>& keys, int page_bytes = 96, int frames = 2, bool plus_ = true)
        : plus(plus_), disk(page_bytes, plus_), pool(disk, frames),
          t(0), leaf_capacity(0), fanout(0) {
        if (page_bytes < 96 || page_bytes > 1024 || page_bytes % 8 || frames < 1 || frames > 16)
            throw invalid_argument("PARAMETER");
        t = ((page_bytes - 24) / 24 + 1) / 2;
        leaf_capacity = (page_bytes - 24) / 16; fanout = (page_bytes - 8) / 16;
        if (keys.size() > 4096) throw invalid_argument("SIZE");
        for (int key : keys) check_key(key);
        for (size_t i = 1; i < keys.size(); ++i)
            if (keys[i-1] >= keys[i]) throw invalid_argument("ORDER");
        if (keys.empty()) return;
        if (plus) build_plus(keys);
        else {
            int h = 0, cursor = 0;
            while (power(2 * t, h + 1) - 1 < static_cast<int>(keys.size())) ++h;
            root = build_b(keys, cursor, static_cast<int>(keys.size()), h, true);
            levels = h + 1; assert(cursor == static_cast<int>(keys.size()));
        }
    }
    int build_b(const vector<int>& keys, int& cursor, int n, int h, bool is_root) {
        if (h == 0) {
            vector<int> data(keys.begin() + cursor, keys.begin() + cursor + n); cursor += n;
            return disk.add(Node{data, scaled(data), {}, -1});
        }
        int low = power(t, h) - 1, high = power(2 * t, h) - 1, count = 0;
        for (int c = is_root ? 2 : t; c <= 2 * t; ++c)
            if (c - 1 + c * low <= n && n <= c - 1 + c * high) { count = c; break; }
        assert(count > 0);
        auto sizes = balanced_sizes(n - count + 1, count);
        vector<int> separators, children;
        for (int j = 0; j < count; ++j) {
            children.push_back(build_b(keys, cursor, sizes[j], h - 1, false));
            if (j + 1 < count) separators.push_back(keys[cursor++]);
        }
        return disk.add(Node{separators, scaled(separators), children, -1});
    }
    void build_plus(const vector<int>& keys) {
        int groups = (static_cast<int>(keys.size()) + leaf_capacity - 1) / leaf_capacity;
        vector<pair<int,int>> layer;
        int start = 0, i = 0;
        for (int size : balanced_sizes(static_cast<int>(keys.size()), groups)) {
            vector<int> data(keys.begin() + start, keys.begin() + start + size);
            int page = disk.add(Node{data, scaled(data), {}, i + 1 < groups ? i + 1 : -1});
            layer.emplace_back(page, data[0]); start += size; ++i;
        }
        levels = 1;
        while (layer.size() > 1) {
            groups = (static_cast<int>(layer.size()) + fanout - 1) / fanout;
            vector<pair<int,int>> next; start = 0;
            for (int size : balanced_sizes(static_cast<int>(layer.size()), groups)) {
                vector<int> separators, children;
                for (int j = 0; j < size; ++j) {
                    children.push_back(layer[start+j].first);
                    if (j) separators.push_back(layer[start+j].second);
                }
                int page = disk.add(Node{separators, {}, children, -1});
                next.emplace_back(page, layer[start].second); start += size;
            }
            layer = move(next); ++levels;
        }
        root = layer[0].first;
    }
    Query point(int key) {
        check_key(key);
        int before_r = pool.reads, before_h = pool.hits, page = root;
        Query result;
        while (page != -1) {
            result.path.push_back(page);
            const Node& node = pool.fetch(page);
            if (plus && !node.children.empty()) {
                size_t j = upper_bound(node.keys.begin(), node.keys.end(), key) - node.keys.begin();
                page = node.children[j]; continue;
            }
            size_t j = lower_bound(node.keys.begin(), node.keys.end(), key) - node.keys.begin();
            if (j < node.keys.size() && node.keys[j] == key) {
                result.records.emplace_back(key, node.values[j]); break;
            }
            if (node.children.empty()) break;
            page = node.children[j];
        }
        result.reads = pool.reads - before_r; result.hits = pool.hits - before_h; return result;
    }
    Query range_query(int lo, int hi) {
        if (!plus) throw invalid_argument("MODE");
        check_key(lo); check_key(hi);
        if (lo > hi) throw invalid_argument("RANGE");
        int before_r = pool.reads, before_h = pool.hits, page = root;
        Query result;
        while (page != -1) {
            result.path.push_back(page);
            const Node& node = pool.fetch(page);
            if (!node.children.empty()) {
                size_t j = upper_bound(node.keys.begin(), node.keys.end(), lo) - node.keys.begin();
                page = node.children[j]; continue;
            }
            bool stop = false;
            size_t j = lower_bound(node.keys.begin(), node.keys.end(), lo) - node.keys.begin();
            for (; j < node.keys.size(); ++j) {
                int key = node.keys[j];
                if (key > hi) { stop = true; break; }
                result.records.emplace_back(key, node.values[j]);
                if (key == hi) { stop = true; break; }
            }
            if (stop) break;
            page = node.next_leaf;
        }
        result.reads = pool.reads - before_r; result.hits = pool.hits - before_h; return result;
    }
};
void show(const string& label, const Query& q) {
    cout << label << " records=[";
    for (size_t i = 0; i < q.records.size(); ++i) {
        if (i) cout << ',';
        cout << q.records[i].first << ':' << q.records[i].second;
    }
    cout << "] path=[";
    for (size_t i = 0; i < q.path.size(); ++i) { if (i) cout << ','; cout << q.path[i]; }
    cout << "] reads=" << q.reads << " hits=" << q.hits << '\n';
}
int main() {
    vector<int> keys;
    for (int k = 3; k <= 51; k += 3) keys.push_back(k);
    Index b(keys,96,2,false), plus(keys,96,2,true);
    cout << "page_bytes=96 cache_frames=2\nB t=" << b.t << " pages=" << b.disk.pages.size()
         << " root=" << b.root << " levels=" << b.levels
         << "\nB+ leaf_capacity=" << plus.leaf_capacity << " fanout=" << plus.fanout
         << " pages=" << plus.disk.pages.size() << " root=" << plus.root << " levels=" << plus.levels << '\n';
    for (int key : {27,33,33}) show("B get(" + to_string(key) + ")", b.point(key));
    for (int key : {27,33,34}) show("B+ get(" + to_string(key) + ")", plus.point(key));
    show("B+ range(21,45)", plus.range_query(21,45));
    int reads = b.pool.reads + plus.pool.reads, hits = b.pool.hits + plus.pool.hits;
    cout << "totals reads=" << reads << " hits=" << hits << " transfers=" << reads << " writes=0\n";
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.List;

public class Main {
    static final class Node {
        final int[] keys, values, children;
        final int nextLeaf;
        Node(int[] keys, int[] values, int[] children, int nextLeaf) {
            this.keys = keys; this.values = values; this.children = children; this.nextLeaf = nextLeaf;
        }
    }
    static final class Query {
        final List<int[]> records = new ArrayList<>();
        final List<Integer> path = new ArrayList<>();
        int reads, hits;
    }
    static final class Disk {
        final int pageBytes;
        final boolean plus;
        final List<Node> pages = new ArrayList<>();
        Disk(int pageBytes, boolean plus) { this.pageBytes = pageBytes; this.plus = plus; }
        int add(Node node) {
            int n = node.keys.length, c = node.children.length;
            int size = plus ? (c == 0 ? 24 + 16*n : 16 + 8*n + 8*c) : 16 + 16*n + 8*c;
            if (size > pageBytes) throw new AssertionError("page size");
            int id = pages.size(); pages.add(node); return id;
        }
    }
    static final class Pool {
        final Disk disk;
        final int frames;
        final LinkedHashMap<Integer, Boolean> lru = new LinkedHashMap<>(16, 0.75f, true);
        int reads, hits;
        Pool(Disk disk, int frames) { this.disk = disk; this.frames = frames; }
        Node fetch(int page) {
            if (lru.containsKey(page)) { ++hits; lru.get(page); }
            else {
                ++reads;
                if (lru.size() == frames) lru.remove(lru.keySet().iterator().next());
                lru.put(page, true);
            }
            return disk.pages.get(page);
        }
        void clear() { lru.clear(); reads = hits = 0; }
    }
    static int[] balancedSizes(int n, int groups) {
        int[] sizes = new int[groups];
        for (int i = 0; i < groups; ++i) sizes[i] = n/groups + (i < n%groups ? 1 : 0);
        return sizes;
    }
    static int[] array(List<Integer> values) {
        int[] a = new int[values.size()];
        for (int i = 0; i < a.length; ++i) a[i] = values.get(i);
        return a;
    }
    static int[] scaled(int[] keys) {
        int[] values = new int[keys.length];
        for (int i = 0; i < keys.length; ++i) values[i] = keys[i] * 10;
        return values;
    }
    static int power(int base, int exponent) {
        int result = 1;
        while (exponent-- > 0) result *= base;
        return result;
    }
    static void checkKey(int key) {
        if (key < -1000000 || key > 1000000) throw new IllegalArgumentException("VALUE");
    }
    static int bound(int[] keys, int key, boolean upper) {
        int lo = 0, hi = keys.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (keys[mid] < key || (upper && keys[mid] == key)) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
    static final class Index {
        final boolean plus;
        final Disk disk;
        final Pool pool;
        final int t, leafCapacity, fanout;
        int root = -1, levels, cursor;
        Index(int[] keys, int pageBytes, int frames, boolean plus) {
            if (pageBytes < 96 || pageBytes > 1024 || pageBytes%8 != 0 || frames < 1 || frames > 16)
                throw new IllegalArgumentException("PARAMETER");
            if (keys.length > 4096) throw new IllegalArgumentException("SIZE");
            for (int key : keys) checkKey(key);
            for (int i = 1; i < keys.length; ++i)
                if (keys[i-1] >= keys[i]) throw new IllegalArgumentException("ORDER");
            this.plus = plus; disk = new Disk(pageBytes, plus); pool = new Pool(disk, frames);
            t = ((pageBytes - 24)/24 + 1)/2;
            leafCapacity = (pageBytes - 24)/16; fanout = (pageBytes - 8)/16;
            if (keys.length == 0) return;
            if (plus) buildPlus(keys);
            else {
                int h = 0;
                while (power(2*t, h+1)-1 < keys.length) ++h;
                root = buildB(keys, keys.length, h, true); levels = h+1;
                if (cursor != keys.length) throw new AssertionError("coverage");
            }
        }
        int buildB(int[] keys, int n, int h, boolean isRoot) {
            if (h == 0) {
                int[] data = Arrays.copyOfRange(keys, cursor, cursor+n); cursor += n;
                return disk.add(new Node(data, scaled(data), new int[0], -1));
            }
            int low = power(t,h)-1, high = power(2*t,h)-1, count = 0;
            for (int c = isRoot ? 2 : t; c <= 2*t; ++c)
                if (c-1+c*low <= n && n <= c-1+c*high) { count = c; break; }
            if (count == 0) throw new AssertionError("child count");
            int[] sizes = balancedSizes(n-count+1, count);
            List<Integer> separators = new ArrayList<>(), children = new ArrayList<>();
            for (int j = 0; j < count; ++j) {
                children.add(buildB(keys, sizes[j], h-1, false));
                if (j+1 < count) separators.add(keys[cursor++]);
            }
            int[] data = array(separators);
            return disk.add(new Node(data, scaled(data), array(children), -1));
        }
        void buildPlus(int[] keys) {
            int groups = (keys.length+leafCapacity-1)/leafCapacity, start = 0, i = 0;
            List<int[]> layer = new ArrayList<>();
            for (int size : balancedSizes(keys.length, groups)) {
                int[] data = Arrays.copyOfRange(keys, start, start+size);
                int page = disk.add(new Node(data, scaled(data), new int[0], i+1 < groups ? i+1 : -1));
                layer.add(new int[]{page, data[0]}); start += size; ++i;
            }
            levels = 1;
            while (layer.size() > 1) {
                groups = (layer.size()+fanout-1)/fanout;
                List<int[]> next = new ArrayList<>(); start = 0;
                for (int size : balancedSizes(layer.size(), groups)) {
                    List<Integer> separators = new ArrayList<>(), children = new ArrayList<>();
                    for (int j = 0; j < size; ++j) {
                        children.add(layer.get(start+j)[0]);
                        if (j != 0) separators.add(layer.get(start+j)[1]);
                    }
                    int page = disk.add(new Node(array(separators), new int[0], array(children), -1));
                    next.add(new int[]{page, layer.get(start)[1]}); start += size;
                }
                layer = next; ++levels;
            }
            root = layer.get(0)[0];
        }
        Query point(int key) {
            checkKey(key);
            int beforeR = pool.reads, beforeH = pool.hits, page = root;
            Query result = new Query();
            while (page != -1) {
                result.path.add(page); Node node = pool.fetch(page);
                if (plus && node.children.length != 0) {
                    page = node.children[bound(node.keys,key,true)]; continue;
                }
                int j = bound(node.keys,key,false);
                if (j < node.keys.length && node.keys[j] == key) {
                    result.records.add(new int[]{key,node.values[j]}); break;
                }
                if (node.children.length == 0) break;
                page = node.children[j];
            }
            result.reads = pool.reads-beforeR; result.hits = pool.hits-beforeH; return result;
        }
        Query rangeQuery(int lo, int hi) {
            if (!plus) throw new IllegalArgumentException("MODE");
            checkKey(lo); checkKey(hi);
            if (lo > hi) throw new IllegalArgumentException("RANGE");
            int beforeR = pool.reads, beforeH = pool.hits, page = root;
            Query result = new Query();
            while (page != -1) {
                result.path.add(page); Node node = pool.fetch(page);
                if (node.children.length != 0) {
                    page = node.children[bound(node.keys,lo,true)]; continue;
                }
                boolean stop = false;
                for (int j = bound(node.keys,lo,false); j < node.keys.length; ++j) {
                    int key = node.keys[j];
                    if (key > hi) { stop = true; break; }
                    result.records.add(new int[]{key,node.values[j]});
                    if (key == hi) { stop = true; break; }
                }
                if (stop) break;
                page = node.nextLeaf;
            }
            result.reads = pool.reads-beforeR; result.hits = pool.hits-beforeH; return result;
        }
    }
    static void show(String label, Query q) {
        StringBuilder s = new StringBuilder(label+" records=[");
        for (int i = 0; i < q.records.size(); ++i) {
            if (i != 0) s.append(',');
            int[] a = q.records.get(i); s.append(a[0]).append(':').append(a[1]);
        }
        s.append("] path=[");
        for (int i = 0; i < q.path.size(); ++i) { if (i != 0) s.append(','); s.append(q.path.get(i)); }
        System.out.println(s.append("] reads=").append(q.reads).append(" hits=").append(q.hits));
    }
    public static void main(String[] args) {
        int[] keys = new int[17];
        for (int i = 0; i < keys.length; ++i) keys[i] = 3*(i+1);
        Index b = new Index(keys,96,2,false), plus = new Index(keys,96,2,true);
        System.out.println("page_bytes=96 cache_frames=2");
        System.out.println("B t="+b.t+" pages="+b.disk.pages.size()+" root="+b.root+" levels="+b.levels);
        System.out.println("B+ leaf_capacity="+plus.leafCapacity+" fanout="+plus.fanout
                           +" pages="+plus.disk.pages.size()+" root="+plus.root+" levels="+plus.levels);
        for (int key : new int[]{27,33,33}) show("B get("+key+")",b.point(key));
        for (int key : new int[]{27,33,34}) show("B+ get("+key+")",plus.point(key));
        show("B+ range(21,45)",plus.rangeQuery(21,45));
        int reads = b.pool.reads+plus.pool.reads, hits = b.pool.hits+plus.pool.hits;
        System.out.println("totals reads="+reads+" hits="+hits+" transfers="+reads+" writes=0");
    }
}

Expected standard output, identical in all three languages:

• page_bytes=96 cache_frames=2
• B t=2 pages=9 root=8 levels=3
• B+ leaf_capacity=4 fanout=5 pages=6 root=5 levels=2
• B get(27) records=[27:270] path=[8] reads=1 hits=0
• B get(33) records=[33:330] path=[8,7,4] reads=2 hits=1
• B get(33) records=[33:330] path=[8,7,4] reads=3 hits=0
• B+ get(27) records=[27:270] path=[5,2] reads=2 hits=0
• B+ get(33) records=[33:330] path=[5,2] reads=0 hits=2
• B+ get(34) records=[] path=[5,2] reads=0 hits=2
• B+ range(21,45) records=[21:210,24:240,27:270,30:300,33:330,36:360,39:390,42:420,45:450] path=[5,1,2,3,4] reads=4 hits=1
• totals reads=12 hits=6 transfers=12 writes=0

Complexity, Correctness, and Invariants

Height and point-search transfers. Let $H$ be the number of page levels, with an empty index having $H=0$. In a B-tree of minimum degree $t\ge2$, a nonempty height-$H$ tree has at least $2t^{H-1}-1$ records, with the usual root exception already included. Consequently $$ H\le1+\log_t\left(\frac{N+1}{2}\right). $$ For a leaf root this gives $H=1$ when $N=1$; larger root-only trees also respect the inequality. Uniform leaf depth and minimum occupancy keep worst-case point descent logarithmic in page fanout. Open Data Structures' B-tree chapter develops this external-memory view.

B+ height is similarly logarithmic because nonroot internal fanout is at least $\lceil F/2\rceil$ and leaf occupancy at least $\lceil L/2\rceil$. For $H\ge2$, the tree has at least $2\lceil F/2\rceil^{H-2}$ leaves and at least $$ 2\left\lceil\frac{L}{2}\right\rceil \left\lceil\frac{F}{2}\right\rceil^{H-2} $$ records. Treat a leaf root and empty index separately. With fixed-size keys and constant occupancy, this gives the usual $O(1+\log_F N)$ page-level search scale.

A cold B-tree point hit can take just one read at the root, or up to $H$ reads at a leaf; a miss descends to a leaf. Every nonempty cold B+ point query here makes exactly $H$ visits and reads, whether the key exists or not. With caching, actual reads can be any count from zero through the number of visited pages. Best/average/worst physical I/O therefore depends on query targets and cache history; there is no universal average without a workload model. The root is not automatically free.

CPU work. Binary search within pages costs $O(\log(2t))$ comparisons per B-tree node and $O(\log F)$ per B+ internal node, with $O(\log(L+1))$ at a B+ leaf. Thus B-tree point CPU cost is $O(H\log(2t))$, and B+ point cost is $O(H\log(F+1)+\log(L+1))$ as a convenient upper bound. LRU hash operations are expected constant time per visit, not a worst-case guarantee for adversarial hash behavior. Cache hits still require routing/comparison work. Worst-case point cost is logarithmic in $N$ comparisons under these capacities; an early B-tree hit can finish sooner.

B+ range queries. Let $Z$ be the number of returned records and $V$ the number of leaf pages visited, including boundary leaves with no qualifying record if needed. A nonempty range visit path has $H-1$ internal visits plus $V$ leaf visits. Minimum leaf occupancy and the two boundary effects imply $$ O\left(H+\frac{Z}{L}+1\right) $$ page visits and at most that many cold reads. The sample has $H=2$, $V=4$, and five visits. Warm reads depend on LRU state; linked leaves are not assumed physically consecutive, so sequential leaf order does not guarantee adjacent disk blocks or low device latency.

The simple range loop performs a lower-bound search in each visited leaf, so its CPU upper bound is $O(H\log(F+1)+V\log(L+1)+Z)$. Starting later leaves at slot zero could remove their repeated lower-bound work. Returned results use $O(Z)$ host space here; a streaming consumer could process them incrementally.

Memory and accounting. The modeled cache budget is $CP$ bytes per index, plus LRU metadata for at most $C$ page IDs. The read-only routing state is constant-sized, apart from the returned visit log and results. A point path log uses $O(H)$ IDs; a range log uses $O(H+V)$ IDs. All simulated disk pages and builder input are retained in host RAM outside the cache model. A cache miss transfers one page; a hit transfers none; no query writes or dirty-page evictions occur. Building and serializing an actual index would incur separate costs not measured here.

B-tree correctness invariant. At every descent, if the key exists and was not matched in the current node, it is contained in the chosen child interval. The ordered internal records split children into strict intervals because keys are unique. Lower bound either finds the stored record or selects exactly the interval that can contain it. A missing leaf match proves absence.

B+ correctness invariant. An internal separator equals the minimum of its right subtree. Upper bound selects the unique half-open child interval containing the target, including equality on the right. Each descent preserves membership in the possible subtree. Leaf lower bound then confirms a record or proves absence. Returning a separator's position alone would not prove the existence of a record value on that internal page.

Range correctness. The initial descent and lower bound find the earliest possible qualifying position. Within-leaf keys and next-leaf links increase globally, so scanning emits each matching key once in sorted order. Encountering a key greater than the high endpoint rules out every later key; equality permits immediate stopping under the unique-key contract. A next-leaf ID of $-1$ proves the right edge of the index was reached.

Why the static builders are valid. A B-tree subtree of edge-height $h$ has nonroot capacity between $t^{h+1}-1$ and $(2t)^{h+1}-1$ records. For an internal node, the builder chooses a legal child count $c$ such that its $c-1$ records plus $c$ feasible child subtrees can hold the requested total; balanced child sizes stay within those bounds. In-order consumption preserves intervals and every record exactly once. B+ balanced groups satisfy half occupancy, equal-height layer construction preserves depth, and right-child minima define the separators. The leaf chain follows the original sorted record order.

The cache does not change routing correctness: every fetch returns the same immutable page contents whether it hits or misses. It only changes the counted storage work.

Variants, Pitfalls, and Optimizations

Match equality routing to separator meaning. This B+ model uses the minimum of the right subtree, so equality goes right. Other valid layouts may use different fences or truncated separators and require different comparisons. Memorizing “use lower bound” or “use upper bound” without the interval invariant produces subtle false negatives. The diagram below shows the failure for key twenty-seven.

Separate routing keys from stored records. A B-tree internal key owns a value here and can answer a point query. A B+ internal separator has no payload and is only a guide to a leaf. Likewise, scanning only B-tree leaves would omit internal records; the linked-leaf range implementation is deliberately B+ only.

Treat warm cache claims carefully. A repeated three-page path can miss every time in a two-frame LRU pool. Roots and upper levels are often valuable cache residents, but this code does not pin them, and a range scan can evict them. Production policies may reserve/pin upper pages, isolate scan traffic, prefetch, or use more sophisticated replacement. Each changes residency assumptions and must be reflected in measurements.

Page size means bytes, not an arbitrary key count. Larger values, longer keys, slot arrays, alignment, free space, compression metadata, and sibling links affect capacity. This model fixes widths for clarity. Real variable-length pages require space accounting rather than just testing a maximum number of keys. The SQLite file-format specification illustrates concrete headers, cell layouts, and different B-tree page types; its actual format is not the simplified layout implemented here.

Unique keys and composite keys. The code rejects duplicate input keys. To index repeated user keys, use a total composite key such as $(\text{user key},\text{record ID})$, or a correctly designed duplicate list/posting representation. Define how separators and lower/upper bounds handle that representation. Composite keys also occupy more bytes and can reduce fanout. Range queries over a prefix need bounds for the full comparison order.

Leaf links and range endpoints. A correct point-search tree can still have a broken leaf chain. A missing link loses range results, an out-of-order link breaks sorting, and a cycle prevents termination. Validate link coverage separately. Keep endpoint inclusivity explicit; this API includes both bounds and rejects reversed bounds before touching the cache.

Payload and table access. Values are inline in the model, so finding a leaf record completes the query. A real secondary index may return row identifiers requiring additional heap/table reads. Covering indexes can avoid some of them. Do not interpret the index's page count as the total query I/O without checking where requested columns live.

Static search versus updates. Insertion/deletion requires splitting, redistribution/merging, separator maintenance, root changes, and valid leaf links. Persistence adds serialization, write-ahead/recovery or other durability mechanisms, and safe publication of changed pages. Concurrent readers/writers need latches, page guards, or a suitable versioning protocol. CMU's B+ tree project connects leaf/internal page access, buffer-pool fetching, ordered iteration, and update/concurrency responsibilities. The read-only sample intentionally isolates search.

Alternative layouts and refinements. Prefix/fence-key compression can raise internal fanout; bulk loading can improve occupancy and leaf layout; interpolation or SIMD-assisted page search can change CPU costs. B-link sibling/fence mechanisms address concurrency in specific designs. Cache-oblivious layouts, buffered tree variants, and LSM-based indexes explore different locality/write tradeoffs. Their guarantees and page formats must be analyzed on their own assumptions rather than borrowed from this static model.

Practice Problems and Real-World Use

Verify structure before performance: keys are strictly ordered, every B-tree record appears exactly once across all nodes, every B+ record appears once across leaves, children satisfy their key intervals, and all leaves have the same depth. Check nonroot minimum occupancy, root exceptions, every page's encoded size, separator equality to right-subtree minima, and the complete acyclic next-leaf chain.

Use an independent sorted-map or array oracle for point membership and inclusive range results. For each returned visit path, replay LRU with a simple list and verify per-query reads/hits, final residency order, and cumulative totals. A repeated query can produce the same records and path while its transfer count changes. Test cold, warm, and intentionally undersized pools.

All three programs agree on $7042$ construction-and-query workloads: $7014$ valid layouts and $28$ rejected constructions, covering $71900$ query/reset operations. The checks compare complete page layouts, returned records, visit paths, LRU order, and every read/hit counter. A separate flat key/value oracle passed $7760$ point/range comparisons. Structural validation checks degree/half occupancy, equal depths, record coverage, byte limits, separators, and leaf links. Inputs include empty and single-page indexes, exhaustive small key subsets, many page-capacity boundaries, randomized sorted keys, the maximum $4096$ records, page sizes up to $1024$, key/range misses, duplicate/unsorted keys, invalid limits, and cache capacities that trigger eviction. Python also passed $28$ exact-type rejection checks. C++ ran with address and undefined-behavior sanitizers, and sample stdout matches byte for byte across languages.

For a file-backed extension, serialize the stated page format, route all reads through a bounded buffer manager, and stream range results to an independent verifier. Measure logical visits, page-cache misses, bytes, and elapsed time separately. Add table-record fetches only when the payload model requires them, and measure index construction separately from search.