Implementing a B+ tree for database range queries

A B+ tree is a balanced search structure designed for storage systems where records live in pages and queries often request an ordered interval. Unlike a binary search tree, it keeps all searchable records at the leaf level and connects those leaves as a linked sequence. This arrangement makes queries such as WHERE postcode BETWEEN 2000 AND 2999 efficient because the database can find the first matching key and then scan forward.

The structure appears in database indexes, file systems, key-value stores, and embedded storage engines. This article develops the core implementation ideas: page layout, insertion, node splitting, range traversal, deletion, and practical engineering decisions. The examples use Python-like pseudocode, but the same design applies in C, C++, Java, or a database engine written in Rust.

Why B+ trees suit range scans

A B+ tree has two types of nodes. Internal nodes contain separator keys and child pointers, while leaf nodes contain keys and record references. Internal keys guide navigation but usually do not store the complete row. Leaf nodes hold the values and are linked from left to right, creating an ordered chain.

That leaf chain is the key advantage for range queries. A lookup for one value follows a path from the root to a leaf in logarithmic time. A range lookup first performs that same search for the lower bound, then follows next pointers until it passes the upper bound. If the range returns k entries, the expected cost is approximately O(log n + k) node visits, plus the cost of fetching the referenced rows.

A normal binary search tree can also maintain sorted keys, but its nodes are usually connected through pointers scattered across memory or disk. A B+ tree keeps many keys in each page, reducing height and expensive storage reads. This matters to a retailer serving customers in Sydney and Melbourne, where an index on suburb, postcode, or product availability may answer broad ordered queries more often than isolated lookups.

The structure is unrelated to model training, although both areas reward careful attention to representations and access patterns. For a separate overview of layered computation and parameter updates, see perceptron fundamentals; a B+ tree instead organises persistent records and page-level navigation.

Representing pages and separators

A practical implementation treats every node as a page with a fixed capacity. A leaf might contain sorted pairs such as (key, record_id), while an internal page contains separator keys and child page identifiers. Using page identifiers instead of direct memory pointers makes the design suitable for disk storage and allows pages to move in a buffer cache.

For an internal node with child pointers C[0] through C[m], there are usually m separator keys. A key K[i] divides the children so that values in C[i] are less than the separator and values in C[i + 1] are greater than or equal to it. The precise equality rule must remain consistent during search and splitting. A common choice is to descend right when key >= separator.

A minimal in-memory model can look like this:

class Leaf:
    def __init__(self):
        self.keys = []
        self.values = []
        self.next = None
        self.parent = None

class Internal:
    def __init__(self):
        self.keys = []
        self.children = []
        self.parent = None

Real storage engines add page headers, node type flags, checksums, free-space information, and transaction metadata. They may store record identifiers as (page_id, slot_id) pairs rather than Python objects. The page size affects the tree’s fan-out: a 4 KB or 8 KB page can hold many compact keys, while large variable-length values reduce the number of entries and increase tree height.

Inserting keys and splitting full pages

Insertion begins by descending from the root to the leaf that should contain the new key. The leaf remains sorted after insertion. If there is room, the operation is complete. If the leaf exceeds its capacity, it splits into two leaves, and the first key of the new right leaf is copied into the parent as a separator.

The copied separator is not removed from the leaf. This is an important distinction between B+ trees and some B-tree variants: the full data entry remains in a leaf so that every record can be found through the linked leaf level. A simplified operation is:

def split_leaf(leaf):
    middle = len(leaf.keys) // 2
    right = Leaf()
    right.keys = leaf.keys[middle:]
    right.values = leaf.values[middle:]
    leaf.keys = leaf.keys[:middle]
    leaf.values = leaf.values[:middle]

    right.next = leaf.next
    leaf.next = right
    return right.keys[0], right

The parent insertion may itself overflow. In that case, the internal node splits and promotes a separator to its parent. Internal separators are generally moved upward rather than duplicated in both resulting internal nodes. If the root splits, a new root is created with two children, increasing the tree height by one. Because every split distributes entries between pages, the tree remains balanced.

Duplicate keys require an explicit policy. The index may store repeated values in a list, append a unique record identifier to form a composite key such as (postcode, customer_id), or reject duplicates for a unique constraint. Composite keys are especially useful for Australian addresses, where postcode alone does not uniquely identify a suburb or property.

Finding a range and scanning leaves

A point lookup uses binary search within each internal page to select a child. At the leaf, another binary search locates the first key that is greater than or equal to the lower bound. The range scan then emits entries while the current key is less than or equal to the upper bound.

def range_query(tree, low, high):
    leaf = tree.find_leaf(low)
    position = lower_bound(leaf.keys, low)
    results = []

    while leaf is not None:
        while position < len(leaf.keys):
            key = leaf.keys[position]
            if key > high:
                return results
            results.append((key, leaf.values[position]))
            position += 1
        leaf = leaf.next
        position = 0

    return results

The linked leaves avoid returning to the root for every subsequent key. They also support ordered output naturally, which is useful for ORDER BY, time windows, prefix scans, and pagination. A query for transactions between two timestamps can begin at the first timestamp and continue through adjacent leaves until the end time is reached.

The index may return record identifiers rather than full rows. A database then performs heap lookups, sometimes called bookmark lookups, to fetch the data. If the leaf stores every column needed by a query, it becomes a covering index and can avoid those extra reads. For an Australian marketplace preparing an end-of-financial-year report, an index on (sale_date, order_id) can efficiently scan a period while maintaining deterministic ordering.

Deleting entries and maintaining balance

Deletion starts by locating the leaf and removing the key-value pair. If the leaf still contains at least the minimum permitted number of entries, no structural repair is required. If it falls below that threshold, the implementation first tries to borrow an entry from a sibling. Borrowing requires updating the parent separator so that the routing rule remains correct.

If neither adjacent sibling has spare capacity, the underfull leaf merges with a sibling. The parent then loses one child pointer and one separator. That removal can make the parent underfull, causing the same borrow-or-merge process to continue upward. When the root has only one child, the child can replace the root and reduce the tree height.

Leaf links need special care during merges. Suppose left absorbs right; then left.next must become right.next. If a previous-leaf pointer is also stored, it must be updated as well. A stale link can produce missing records, duplicate records, or scans that enter a detached page. Structural changes should therefore be tested with full scans, not only point lookups.

Concurrent databases add another layer of complexity. Readers may be scanning leaf pages while a writer splits or merges them. Techniques such as latch coupling, right-links, write-ahead logging, copy-on-write pages, and multi-version concurrency control help keep searches safe. A learning implementation can begin single-threaded, then add page locking once the invariants are clear.

Testing invariants and performance

A reliable B+ tree implementation should test properties rather than only individual examples. Keys within every node must be sorted, internal separators must route all child keys correctly, and every leaf must appear exactly once in the linked sequence. All leaves should have the same depth, and the root should follow its special minimum-occupancy rule.

Useful tests include inserting sorted keys, reverse-sorted keys, random keys, duplicate keys, and large batches. Run range queries for empty intervals, one-key intervals, bounds outside the stored data, and ranges spanning many leaves. Compare each result with Python’s sorted list or a reference dictionary. This catches split-boundary errors that point lookups can miss.

Measure both logical operations and storage behaviour. Track tree height, page reads, page writes, split frequency, average leaf occupancy, and the number of records returned. A high fan-out usually produces a shallow tree, but overly large entries can reduce fan-out and increase page churn. Keys such as ASX ticker symbols, Australian postcodes, or timestamps have different distributions and should be benchmarked separately.

The same discipline applies when comparing learning strategies in other computational systems. For a separate example of state, action, and update rules, the explanation of Q-learning basics is useful context, while B+ tree testing focuses on deterministic invariants, persistence, and query cost.

Practical implementation choices

Start with an in-memory version that uses a small page capacity, such as four or eight entries. Small pages make splits easy to trigger and expose parent-update bugs quickly. Once the algorithms work, replace object references with page identifiers and add a buffer manager that loads, pins, modifies, and flushes pages.

For applications operating across Australia, timezone and collation rules can affect indexed values. Timestamp ranges should define whether they use UTC or local time, especially when reports cover Sydney, Brisbane, Perth, or daylight-saving transitions. Text indexes need a deliberate collation policy so that ordering is stable across machines and database versions.

Use the following engineering checks before treating the implementation as storage-ready:

• Keep leaf records sorted and connect every leaf to its successor.
• Define duplicate-key behaviour before writing insertion and deletion code.
• Use one consistent separator rule for equality during descent and splitting.
• Verify page identifiers, parent pointers, and sibling links after every structural change.
• Test range results against a simple sorted reference model.
• Record page reads and writes so performance problems are visible rather than guessed.

A production system also needs crash recovery, durable root metadata, checksums, free-page management, and safe handling of partial writes. Australian businesses may need indexes that support postcode searches, local inventory, ASX-related time series, or EOFY reporting, but the underlying guarantees remain the same: ordered leaves, balanced height, correct separators, and predictable range traversal.