Database Indexing

Database indexing reduces query work only when index-page reads + distinct heap-page reads is cheaper than scanning every heap page. An index first narrows the predicate to candidate keys. A row identifier (RID) is only an address pointing to a row's heap page; unless the requested columns are stored in the index, the database must read that page too.

Think of the index as a directory, not the record itself. Hashing jumps to an equality bucket; a B+ tree preserves key order; an INCLUDE payload may answer the projection without following the address. Hold one tiny table constant and the result rows never change. Only the pages needed to produce them do.

How Database Indexing Works

The default query is:

SELECT tier
FROM customers
WHERE customer_id = 84;

The table contains 16 rows stored two per heap page. Its physical row order is deliberately unrelated to customer_id, and the matching row lives at RID P7:S0: heap page 7, slot 0.

A table scan has no shortcut. It reads all eight heap pages and tests both rows on each page. The cost is eight logical page reads even though only one row qualifies, because a page—not an individual row—is the modeled I/O unit.

A hash index computes one bucket number for an equality key. Reading that bucket exposes several key → RID entries, including collisions. The engine must compare the complete key because sharing a bucket does not imply equality. For key 84, the trace reads bucket H4, finds 84 → P7:S0, and then reads heap page P7: two page reads.

A B+ tree preserves key order. The default trace reads root page I0, whose separators narrow the search to leaf L3. The leaf stores 84 → P7:S0, so the path follows that RID to heap page P7: three page reads.

A covering B+ tree stores the projected tier value beside the key and RID. Root I0 and leaf L3 are enough; the leaf payload returns Basic without reading P7. That path costs two page reads.

The exact totals describe this model, not a universal benchmark. The durable idea is the decomposition: index-page reads plus distinct heap-page reads.

Equality, Range, and Key Order

Hashing is a strong fit for exact equality because the hash function maps one key to one bucket. It does not preserve the ordering relationship between keys. Keys 68 through 84 do not necessarily occupy adjacent bucket numbers, so treating a run of buckets as a BETWEEN range could silently miss qualifying rows.

A B+ tree does preserve order. For customer_id BETWEEN 68 AND 84, the trace descends once, starts at leaf L2, and follows the sibling link into L3. The ordered leaves contain five matching keys. A non-covering tree then follows their RIDs to five distinct heap pages. In this model that costs one root, two leaves, and five heap pages: eight reads. The covering tree costs only the three index-page reads because every requested tier value is already in the leaves.

This distinction is about index capability, not notation. An equality predicate may use either structure. An ordered range needs an ordered access path.

Covering Indexes and RID Fetches

An ordinary secondary index entry identifies a row but may not contain every requested column. The RID is the bridge from logical key order back to physical heap storage. Several qualifying RIDs on the same heap page are grouped into one page read; the lesson never charges twice for fetching the same page in one path.

A covering index contains all columns required by the query: predicate columns plus projected columns. For the default query, (customer_id) INCLUDE (tier) covers the answer. Change the projection to email, however, and the same leaf no longer covers the query. The not-covered preset follows P7:S0 and pays the extra heap-page read.

Covering is therefore query-relative. An index can cover one projection and fail to cover another. Wider indexes also consume storage and can make writes more expensive, so “include every column” is not a free solution.

Why an Optimizer Can Ignore an Index

The low-selectivity preset asks for ten Basic customers. Those rows are scattered across all eight heap pages. A non-covering B+ tree reads one root, three leaves, and eight heap pages: 12 reads. The plain scan reads the same eight heap pages without the four index-page reads, so the optimizer can rationally choose the scan.

An index may be valid yet still be more expensive. Selectivity matters because it controls how many entries qualify; physical clustering matters because it controls how many distinct heap pages those RIDs touch. A small result concentrated on one heap page is very different from many results scattered everywhere.

The comparison panel keeps all four modeled totals visible, but the decision is deliberately narrower: should this selected index path replace the scan? Its header names the other totals as counterfactual costs. They do not imply that every index exists at once, and they are not evidence until you replay that access path. In the low-selectivity B+ tree run, the selected-path answer is no. A separately available covering index would change the alternatives because it avoids the heap fetches.

Database Indexing Step by Step

1. Read the SQL predicate and projection. Equality or range determines the capabilities required from the access path.
2. Run the table-scan baseline. Each P# heap chip records one whole page read.
3. Select the configured index path. Hashing computes a bucket; the B+ tree reads a root and one or more leaves.
4. Verify the candidate keys. Hash collisions require full-key checks; B+ tree leaves preserve ordered key intervals.
5. Decide whether the leaf payload covers the projection. If not, collect the matching RIDs.
6. Group RIDs by heap page and fetch each distinct page once.
7. Compare exact cold logical page reads and keep the cheapest valid alternative visible.

The missing-key preset is a useful boundary case. The hash bucket or B+ tree leaf proves that key 85 is absent, so no heap page is touched. An unsuccessful lookup can be cheaper than a successful one because there is no row to fetch.

Database Indexing Edge Cases

• Missing equality key: an index can prove absence from its bucket or leaf, so the trace performs no heap fetch.
• Range across leaf boundaries: the B+ tree starts in L2 and follows its ordered sibling link into L3; a hash index has no equivalent ordered walk.
• Hash collision: keys 44, 52, 68, and 84 share teaching bucket H4, so the complete key comparison—not bucket membership—selects the match.
• Several RIDs on one page: matching rows in the same heap page are fetched together and count as one logical page read.
• Projection not covered: an index that covers tier still needs the heap when the query asks for email.
• Low selectivity: a valid non-covering index can touch every heap page and add index-page reads on top.

Page-Read Complexity by Access Path

Let P be the number of heap pages, N the number of index entries, f the B+ tree fanout, L the number of leaf pages visited, and H the number of distinct heap pages containing matches.

• Table scan: O(P) heap-page reads.
• Hash equality lookup: average O(1) bucket pages plus H heap pages.
• B+ tree point lookup: O(log_f N) index levels plus H heap pages.
• B+ tree range lookup: O(log_f N + L + H) page reads.
• Covering B+ tree: the same index traversal, but H = 0 for columns stored in the leaf payload.

These expressions describe access growth, not elapsed time. Page caching, prefetch, storage hardware, concurrency, and optimizer estimates can all change real execution cost.

Reading a Real Query Plan

The animation gives you a page-accounting habit, not a vendor-specific cost formula. When you inspect a real execution plan, check:

• the estimated and actual qualifying row counts;
• the index condition and projected columns, including whether the plan is index-only or still fetches heap/table pages;
• the number of heap fetches or data pages touched, not only the index lookup;
• the competing table/sequence scan and whether stale statistics, poor clustering, or cardinality estimates changed the choice;
• cache state, prefetch, and engine support for hash indexes or included columns; and
• the storage and write-amplification cost of maintaining a wider index.

Those details can reverse a decision that looks obvious in the cold-page model. The transferable question is still the same: what work does this path add, and what page reads does it avoid?

Common Mistakes

• Assuming every index makes every query faster. A low-selectivity, non-covering index can add work before reading nearly the whole table.
• Using a hash index for a range because the bucket numbers look ordered. Bucket identity carries no global key order.
• Treating a RID as the row value. A RID tells the engine where the row lives; following it may require a heap-page read.
• Calling an index “covering” without naming the query. Coverage depends on the predicate and projected columns.
• Counting one heap read per matching row. Multiple RIDs on the same page share one page fetch in this model.
• Reading the displayed page totals as PostgreSQL or MySQL constants. They belong to the authored teaching layout.

A Note on Simplification

This lesson counts cold logical page reads over a tiny, two-level B+ tree, fixed-size hash buckets, and an unclustered heap. It omits buffer-pool residency, page cache, prefetch, visibility checks, MVCC, locks, compression, overflow bucket chains, tree height changes, statistics uncertainty, write amplification, and engine-specific page layouts. Real optimizers compare estimated CPU, I/O, caching, correlation, and cardinality costs. The model isolates one question: which physical pages must this access path touch to return the same logical rows?