Ordered indexes, ranges, and pagination

Start with the guided lesson. These sections develop the mechanisms and tradeoffs beyond that first example.

Learning outcomes

• Follow point and range lookups through a B+ tree and explain leaf links and separators.
• Explain hash access, composite-key order, covering access, and page-split maintenance costs.
• Calculate how fanout and entry width influence height without treating an idealized bound as measured capacity.

An index is an ordered promise about access

A tenant’s feed query asks for its newest records. An index on (tenant_id, created_at) places one tenant’s entries near each other and orders them by time. A query asking for every tenant’s records at one timestamp cannot necessarily use the same leading-key restriction efficiently. The difference follows from how composite keys are ordered, not from an arbitrary optimizer preference.

An index is a maintained access structure. It trades additional storage and update work for selected retrieval paths. A design must account for search, insertion, deletion, structural change, concurrency, recovery, and the relationship between index entries and visible table records.

B+ tree structure

A B+ tree uses internal nodes to route searches and leaves to store entries. An internal separator divides key ranges among children. Leaves hold ordered keys and associated references or values. Leaf links can support ordered traversal after the initial search reaches the correct position.

                 [20 | 50]
                /    |    \
        keys <20   20..49   keys >=50
            |         |         |
          leaf ----> leaf ----> leaf

The diagram is illustrative. Separator conventions differ, so an implementation must state whether a boundary belongs to the left or right child. Equality handling must remain consistent through search, split, and recovery. An off-by-one boundary error can make records unreachable even when every page contains valid bytes.

Large fanout keeps trees shallow. With illustrative fanout 200, successive routing levels can address 200, 40,000, 8 million, and 1.6 billion child references. Those are idealized capacities, not exact record counts: leaf occupancy, key width, payload width, and root special cases matter. The useful conclusion is that small changes in entry width can affect fanout and cache efficiency.

Search and range access

A search compares the target key with separators, chooses a child, and repeats until reaching a leaf. Within the leaf, binary search or another local search finds the first candidate. A range scan then advances through entries and leaf links until the upper bound is exceeded.

The cost includes more than comparisons. Each level may require a buffer lookup, pin, latch, and cache miss. Root and upper nodes are often hot, but that is a workload observation rather than a guarantee. Long keys can increase comparison work and reduce fanout. Prefix compression can improve density while adding reconstruction logic.

A secondary index may return a physical row reference or a primary key that requires another lookup. That extra access can dominate when matches are scattered. An index-only or covering path stores enough information to answer selected queries without fetching every base record, subject to visibility rules. Including more columns makes the index larger and more expensive to maintain.

Composite keys and leading prefixes

Lexicographic ordering compares the first component, then the next when earlier components are equal. In (tenant_id, created_at), entries for tenant 17 form a contiguous range. Within that range, timestamps are ordered. A query with tenant equality and a timestamp range naturally maps to an interval.

CREATE INDEX feed_by_tenant_time
ON feed (tenant_id, created_at);

SELECT event_id, created_at
FROM feed
WHERE tenant_id = 17
  AND created_at >= TIMESTAMP '2026-10-01 00:00:00';

The SQL describes a useful access pattern. Actual use depends on the engine, statistics, selected columns, and result size. A query missing the leading tenant predicate may scan many ranges or use another strategy. Some engines implement additional methods such as skip scanning under appropriate conditions; the basic ordering still explains why one index is not equally selective for every predicate combination.

Ordering also interacts with ORDER BY and limits. A matching index can deliver the first few rows without sorting the entire result. A residual predicate that rejects many candidates can make a small limit expensive despite the convenient order. Query plans must account for the number of entries examined, not just the number returned.

Range scans need a visibility contract

A range scan locates the first candidate and walks forward, potentially while other transactions split, delete, and update pages. Structural safety ensures traversal does not follow freed memory or skip a reachable range because of an inconsistent split. Transactional visibility determines which versions belong in the answer. These are separate guarantees.

For example, a snapshot scan may ignore a newly inserted key even though the tree traversal encounters it. It may need an older version of a recently updated row. An engine can keep multiple versions in leaves, reference version chains elsewhere, or recheck base-table metadata. The index’s physical order does not alone define a transaction’s visible set.

Long scans should not hold exclusive structural protection on every visited leaf. Doing so would block unrelated modifications and make a large query dominate concurrency. Implementations use brief latches, stable references, continuation keys, or other techniques. Resuming after releasing a page can require care with duplicate keys and deleted entries: continuing from a nonunique value alone can repeat or skip records. A unique tie-breaker can make the continuation position unambiguous.

Keyset pagination follows the index order

Suppose a feed orders by (created_at, event_id) within one tenant. Timestamps alone are not unique; event identifier provides a deterministic tie-breaker. A next-page query can resume after the last pair rather than count and discard all earlier rows. Conceptually, the predicate is created_at > last_time OR (created_at = last_time AND event_id > last_id) for ascending order, with tenant equality held fixed.

Offset pagination with a large offset can require examining and skipping many candidates. Keyset pagination often avoids that work, but its user-visible semantics differ when data changes between pages. A stable snapshot can provide one consistent result set while retaining versions. Independent page requests can observe changes and need an explicit policy for additions and deletions. An efficient access path does not choose those semantics for the product.

Descending order reverses comparisons and must handle null placement explicitly. Collation also matters for text keys: byte ordering and language-aware ordering can disagree. A persistent index must use comparison rules compatible with its stored order, and a collation change may require rebuilding. Fast binary search over inconsistently ordered keys cannot produce reliable results.

Read a composite key as nested ordered ranges

The table uses (tenant, time, event) with a unique final tie-breaker. Tenant 17 and time at least 10:05 form a contiguous suffix of one tenant range. Time at least 10:05 across all tenants generally forms many separated ranges. A search can exploit repeated range positioning in some engines, but that is different work from one contiguous interval.

The ordered key also supports deterministic continuation after (17, 10:05, 2): event 3 still belongs on the next page even though its timestamp is equal. Using timestamp alone as the cursor can skip it. An exact continuation contract must include all ordering components and define ascending or descending comparison consistently.

If the index payload includes a field needed by the query, it can avoid a base-record fetch when the engine can establish visibility from available metadata. If visibility requires inspecting the row version, coverage of user columns alone is insufficient. This separates three often-confused ideas: a predicate can use an index, the index can supply the requested order, and the index can answer without fetching base records. A design should identify which benefits actually apply.

Case connection and design conclusion

PostgreSQL’s B-tree and multicolumn-index documentation provide concrete examples of ordered indexing and composite-key behavior. The architectural analysis is that an access structure is selected for a query family under a mutation workload. It should not be judged only by an isolated lookup benchmark.

A reviewable index design states key ordering, payload, record references, split and reclamation behavior, visibility handling, and recovery. Lesson 11 contrasts this update-in-place family with log-structured storage, where writes are organized into successive immutable runs and background merging carries a larger share of the cost.

Sources and further reading

• PostgreSQL 18 B-tree implementation
• PostgreSQL 18 multicolumn indexes