Why can a B+tree index efficiently return every row whose key falls within a range, and produce rows already in key order for an ORDER BY without a separate sort step? What property of the structure makes that possible?

## What the structure looks like A B+tree index has two kinds of pages. **Leaf pages** hold the index entries themselves — a key value and a pointer to the corresponding row — stored in ascending key order within the page. **Internal pages** hold only separator keys and pointers to child pages; they are a routing directory, not storage. Every leaf is at the same depth. The critical extra detail, and the one that distinguishes a B+tree from a plain B-tree, is that the leaf pages are **linked to one another in key order**. Read the leaves left to right by following those links and you have read every key in the index, in sorted order, exactly once. ## Answering a range predicate Suppose the query asks for every row whose key lies between two bounds. 1. **Descend once.** Starting at the root, compare against the separator keys to choose a child, repeat, and arrive at the leaf that contains the lower bound — or the first key greater than it, if the bound itself is absent. Because internal pages hold hundreds of separators each, this takes only about three to four page reads even for hundreds of millions of entries. 2. **Position within the leaf.** Entries in the page are sorted, so a binary search inside the page finds the first qualifying entry. 3. **Walk the chain.** Emit entries in order. When the page is exhausted, follow the sibling link to the next leaf and continue. 4. **Stop on the bound.** The first key that exceeds the upper bound ends the scan. There is nothing beyond it that can qualify, precisely because the entries are ordered. No backtracking to the root, no examination of pages outside the range. The cost is the descent plus however many leaf pages the qualifying entries occupy. ## Why this makes range queries cheap The scan's cost tracks the size of the *answer*, not the size of the table. Retrieving 200 rows out of 50 million costs a handful of page reads. That is the fundamental reason B+trees, rather than hash structures, are the default index type in relational engines: hashing gives you one key at a time and destroys ordering, so a range predicate over a hash structure degenerates into examining everything. ## Why ORDER BY can skip the sort Sorting is expensive and, in the general case, **blocking** — the sort must consume all its input before it can emit the first row. A scan of a B+tree emits rows in key order by construction. If a query's ordering matches the index's key order, the planner can drop the sort operator entirely: no memory for a sort workspace, no spilling to temporary disk files, and the first row can be returned immediately. That last point matters enormously for queries that ask for only the first few rows. With an ordered index scan, retrieving the top ten rows means touching a couple of pages and stopping. With a scan-then-sort plan, the same query must read and sort everything before it can know which ten come first. ## Prefix pattern matching is a range in disguise A pattern anchored at the start of a string — everything beginning with a given prefix — is exactly the set of values from that prefix up to (but not including) the prefix with its last character incremented. Because the index stores strings in collation order, that is a contiguous stretch of the leaf chain, so the same descend-and-walk mechanism applies. The converse is equally important: a pattern that is *not* anchored at the start has no contiguous range, because matching values are scattered across the whole key space. The index cannot help, and the engine must examine every row (or use a different structure entirely). This asymmetry — leading-prefix patterns are cheap, leading-wildcard patterns are not — is a direct consequence of ordering, and it is one of the most commonly asked consequences of B+tree structure. A subtlety worth knowing: this depends on the index being stored in a collation whose ordering matches the comparison being performed. If the index is ordered under one collation and the pattern match is defined under different rules, the matching values may not form a contiguous range, and the range trick is unavailable. ## The limit worth naming An index scan that must then fetch the full rows performs one lookup per matching entry, and those lookups land in effectively random locations. Past some fraction of the table, doing many random row fetches costs more than reading the whole table sequentially, and a full scan wins despite examining more rows. So "the index makes ranges cheap" is true for selective ranges and stops being true for broad ones — which is why an index that is perfect for a one-day range may be ignored for a one-year range. ## The one-sentence version Entries are sorted and the leaves are chained, so one descent plus a linear walk answers any contiguous range and delivers it already ordered.