Indexes as ordered shortcuts

The shortcut with a contract

An index lets the database find candidate rows without reading the whole table. It is not a second copy of the table in a prettier format. It is a maintained access path, tuned for particular questions. In a Postgre-like system, the classic example is the B-tree, a balanced ordered structure that maps key values to heap tuple locations. When a predicate lines up with the index's order, the executor can jump close to the answer.

A B-tree keeps keys sorted across pages. Internal pages guide the search. Leaf pages hold key entries and tuple identifiers, often with links to neighboring leaves for range scans. To find a key, the engine starts at the root, chooses a child by comparing keys, descends through internal pages, and lands on a leaf. From there it finds matching entries and visits the heap to check visibility and retrieve columns.

Why B-trees stay shallow

This design works well because height grows slowly. A table with millions of entries can often be searched through only a few page reads near the root plus leaf and heap access. Frequently used upper pages tend to stay hot in the buffer pool. The index turns a broad table scan into a narrow navigation problem.

The shortcut is conditional

An index scan only wins when the shortcut is shorter. If a query asks for one account by primary key, a sequential scan wastes time checking unrelated rows, and the index gives a direct path. If a query asks for every row where a boolean column is true and almost all rows are true, the index may be a detour. It reads index pages, then visits heap pages anyway. Indexes help when they reduce work or provide useful order, but they are not automatically faster.

The heap recheck is one of the most important details. A B-tree entry points to a physical tuple location, but MVCC visibility is decided by the heap tuple and transaction status. An index can say that a tuple with a given key was placed at a location. It cannot always say that the tuple is visible to your snapshot. The executor follows the pointer, inspects the heap version, and may discard it. This is why an index scan can touch many heap pages even when the index lookup itself is selective.

Covering and index-only scans refine the story. If the query needs only columns stored in the index, the executor may avoid heap access, but only when it can prove the heap page has no tuple versions requiring visibility checks for the current snapshot. Visibility map structures can make that proof cheap for pages known to contain only universally visible tuples. The index then becomes more than a shortcut to the heap. It becomes a source of answers.

Order is a feature

Composite indexes depend on key order. An index on `(customer_id, created_at)` is useful for equality on `customer_id` and ranges on `created_at` within each customer. It is not equally useful for searching by `created_at` alone, because the primary ordering groups by customer first. This is a physical consequence of sorted keys, not an arbitrary planner limitation. The index can only accelerate paths that align with its order.

Ordering is itself a benefit. A B-tree can produce keys in sorted order, which may let the planner skip a separate sort for `order by`, merge joins, or grouped operations. This is why an index can be chosen even when it is not the most selective filter. It may deliver rows in exactly the shape a later operator needs.

Uniqueness adds another role. A unique index is both an access path and a constraint enforcement mechanism. When inserting a key, the database checks whether a visible conflicting key already exists. Under concurrency, that check must coordinate with transactions inserting the same key at the same time. The index participates in correctness, not just speed.

There are many index families beyond B-trees. Hash indexes support equality. GiST, SP-GiST, GIN, and BRIN serve different data shapes, including geometric values, full-text search, arrays, ranges, and large naturally ordered tables. The general lesson is that an index encodes assumptions about the predicates and access patterns it can accelerate. Different questions deserve different shortcuts.