Index Lookup Costs Lab (Interactive)
Trace primary-key, double-lookup, and covering-index reads across a growing B+Tree. Grow the table exponentially, change the query shape, and count the exact B+Tree descents, heap fetches, and write tax each index type charges per read.
Clustered · Secondary · Covering — Count the Page Reads
Same table, three physical access paths; every double-lookup is a real second descent down the B+Tree.
Leaf pages physically store the full row in PK order — one descent returns everything.
How It Works Under the Hood
Every read pays in page reads. A primary-key lookup descends the clustered B+Tree once and the leaf holds the row itself. A secondary index makes you pay twice — descend the index tree, then fetch the row by PK pointer from the clustered leaf. A covering index copies the requested columns into its own leaves, enabling index-only scans that skip the table trip. But each secondary index stores the PK per entry and is maintained on every write, so index count becomes a write-amplification tax.
Core Architectural Principles
- B+Tree height grows logarithmically in fanout, so even hundred-million-row tables resolve in 3–4 page reads.
- Secondary indexes store PK pointers, forcing a double-lookup into the clustered index for any non-covered column.
- Covering indexes with INCLUDE enable index-only scans but multiply write cost by the number of trees maintained per mutation.
Read execution plans with a cost model in your head: distinguish index-only scan, index scan, and heap fetch, and justify a covering index on hot read paths where random heap pages dominate latency. Warn that extra index count taxes write-heavy tables, and offer partial indexes to cut both RAM and write cost when a WHERE predicate is highly selective.
More covering indexes make reads single-descent affairs but charge every INSERT and UPDATE a maintenance round through each tree.