B-tree pages through a range scan

A B-tree range scan usually pays for an initial descent and then visits neighboring data pages. Repeating a point lookup for every requested key can revisit the navigation path. That difference matters when you read an index plan, but it does not directly tell you how many physical storage reads occur: frequently visited pages may already be cached.

This lesson is for a developer who knows sorted arrays and wants to understand page-oriented indexes. We build a tiny, immutable B+tree-style model, trace an interval query, and distinguish logical page requests from distinct pages and actual I/O. Basic Python is sufficient. The model uses invented page identifiers and integer keys, not a database file parser or a benchmark.

Put several ordered keys behind each navigation decision

A storage engine commonly organizes its files into pages. SQLite’s file-format description specifies a fixed page size within a database file. A page can hold several keys and references, so a tree node need not mean one key as it does in a simple binary search tree. The useful branching factor depends on available bytes, key size, headers and occupancy.

Our root has four children and three separators: 4, 8 and 12. The four leaf pages contain keys 0 through 3, 4 through 7, 8 through 11, and 12 through 15. Each leaf also names its next sibling. All records, including their tiny vN values, live in leaves. Every leaf is the same distance from the root.

We define a separator as the smallest key belonging to the child on its right. Therefore a search for 8 goes right of separator 8, into L2. Python’s bisect_right implements that boundary choice. A search for 7 goes into L1. A search below the smallest stored key still starts in L0; one above the largest starts in L3 and can find nothing there.

This convention belongs to the example. Real implementations can use different separator inequalities, high keys and payload placement. SQLite distinguishes table and index B-trees: table-tree data live in leaves, while index-tree keys can also occupy interior cells. It would be wrong to infer that every structure called a B-tree stores all useful information only in leaf pages.

View full-size image ↗

The arrows between leaves encode an ordered next page. They do not assert that sibling pages occupy adjacent disk sectors. Allocation history and page splits can separate their physical locations even when a scan traverses them consecutively.

Descend once, then follow the leaf sequence

The query uses a half-open interval: include keys at least low, but exclude keys equal to high. For [6, 14), routing on 6 selects L1. The scan skips 4 and 5, returns 6 and 7, then follows the sibling pointer. L2 contributes 8 through 11; L3 contributes 12 and 13. Seeing 14 ends the scan.

The following code is a complete Python 3.10-or-later example. read records a logical request before returning an already resident Python object. No file is opened. The fixed pages are trusted, unmodified input; this code does not validate an arbitrary index or repair broken sibling chains.

from bisect import bisect_right
from dataclasses import dataclass


@dataclass(frozen=True)
class Leaf:
    rows: tuple
    next_page: str | None


PAGES = {
    "root": ((4, 8, 12), ("L0", "L1", "L2", "L3")),
    **{
        f"L{i}": Leaf(
            tuple((key, f"v{key}") for key in range(4 * i, 4 * i + 4)),
            f"L{i + 1}" if i < 3 else None,
        )
        for i in range(4)
    },
}


class Index:
    def __init__(self):
        self.visits = []

    def read(self, page_id):
        self.visits.append(page_id)
        return PAGES[page_id]

    def start(self, key):
        separators, children = self.read("root")
        return children[bisect_right(separators, key)]

    def point(self, key):
        leaf = self.read(self.start(key))
        return next((row for row in leaf.rows if row[0] == key), None)

    def scan(self, low, high):
        if low >= high:
            return []
        result = []
        page_id = self.start(low)
        while page_id is not None:
            leaf = self.read(page_id)
            for row in leaf.rows:
                if row[0] >= high:
                    return result
                if row[0] >= low:
                    result.append(row)
            page_id = leaf.next_page
        return result


index = Index()
assert index.scan(6, 14) == [(key, f"v{key}") for key in range(6, 14)]
assert index.visits == ["root", "L1", "L2", "L3"]
print(index.visits)

The result contains eight records, but the request trace contains four pages: root, L1, L2 and L3. The root helps find the first relevant leaf. It is unnecessary to return there for each later record, because the leaf sequence preserves global key order.

PostgreSQL’s B-tree implementation notes describe forward scans that descend initially and then walk leaf right links. The same notes explain extra machinery for concurrent page changes, including locks and remembering the appropriate sibling link. Our immutable model demonstrates ordered traversal, not those concurrency guarantees. The cited source is a captured development-branch document, not a promise about every released version.

A real query may also need to fetch table rows. Our leaves contain the complete requested value, so the trace stops at the index. PostgreSQL’s notes describe leaf entries with keys and heap tuple identifiers; a query needing other row fields can incur additional heap access. Four model page requests are therefore not an estimate for an arbitrary database query returning eight rows.

Count the page that proves the range has ended

Now change the upper bound to 8. L1 returns 6 and 7, then runs out of entries. This implementation follows its sibling link to L2, reads the first key 8, and stops without returning any row from that page. Its trace is root, L1, L2: three requests for two results.

There is nothing contradictory about a visited page contributing no output. It supplies evidence that the interval has ended. An implementation that carries a suitable upper fence from the parent might avoid that extra request. Ours deliberately retains only the chosen child identifier, so that optimization is absent. Count the code’s behavior instead of assuming every visited leaf must contain an answer.

Continue in the same Python session to compare repeated point requests and boundary cases:

scan_index = Index()
rows = scan_index.scan(6, 14)
point_index = Index()
assert [point_index.point(key) for key in range(6, 14)] == rows
assert len(scan_index.visits) == 4
assert len(point_index.visits) == 16
assert set(scan_index.visits) == set(point_index.visits)
assert len(set(scan_index.visits)) == 4

boundary = Index()
assert boundary.scan(6, 8) == [(6, "v6"), (7, "v7")]
assert boundary.visits == ["root", "L1", "L2"]
empty = Index()
assert empty.scan(8, 8) == [] and empty.visits == []
missing = Index()
assert missing.scan(20, 24) == []
assert missing.visits == ["root", "L3"]
print("logical requests:", len(scan_index.visits), len(point_index.visits))
print("distinct pages:", len(set(scan_index.visits)), len(set(point_index.visits)))

An empty or reversed interval returns before descending. An interval entirely above the stored keys still requires the root and final leaf in this model. The distinction is between a query that is empty by its own bounds and a nonempty query interval whose contents happen to be absent.

View full-size image ↗

Separate logical work from cache misses

Eight point lookups each request the root and one leaf, producing sixteen logical requests. The range scan makes four. Both touch exactly the same four distinct pages. Under a deliberately simple initially empty cache that keeps every requested page, both would have four misses; every repeated point request after a page’s first appearance would hit.

That cache calculation is hypothetical. An actual buffer pool may already contain the root, may evict pages, and may perform read-ahead. Operating-system and device caches add other boundaries. A logical miss at one layer need not mean a physical device read. Consequently neither the four-versus-sixteen count nor the four-distinct-pages count establishes a latency ratio.

The scan still avoids repeated navigation work and can expose useful access locality. But the end-to-end outcome also depends on row fetching, filtering, key comparisons, synchronization and result handling. State what you counted before comparing implementations. A page-request trace is an explanation of an algorithm, not a substitute for database instrumentation under a stated workload.

Keep page capacity and update costs in the picture

With a much larger tree, a point search follows multiple internal levels. More children per page can reduce the number of levels, but larger keys can reduce that fanout. Large payloads may require overflow storage; SQLite’s format describes overflow pages for payloads that do not fit their cell allocation. Counting only tree nodes can then omit additional reads.

A static full leaf is easy to scan; maintaining it during insertion is another task. Inserts can require moving entries, splitting pages and updating navigation information. Deletions and concurrent readers add further rules. This example implements none of them, and its perfectly even four-record leaves should not be treated as a normal occupancy guarantee.

For a reproducible exercise, enumerate every integer interval whose bounds run from -2 through 18 and compare the returned records with filtering the original sixteen-row list. Then add an initially empty, non-evicting cache counter around read and reproduce the four misses for both main workloads. Finally test [6, 8) and explain which additional fence information could remove its stop-page request. Keep the result order, boundary convention and counted layer explicit in each change.