Indexing: Types, Structure & Cost

Which index, in what order, at what cost

An index is a sorted, auxiliary copy of some columns that lets the database find rows without scanning the whole table. The core senior skill is not "add an index," it is knowing which index serves a given query, in what column order, and what that index costs you on every write.

Clustered vs secondary

A clustered / primary index determines the physical order of the rows themselves; the table is the index (InnoDB tables are clustered on the primary key). A secondary index is a separate B-tree that maps indexed columns to a row locator (the primary key in InnoDB, or a physical tuple pointer in Postgres, whose tables are unordered "heaps"). This matters because in a heap table, a secondary index match still needs a second read to fetch the row from the heap.

The leftmost-prefix rule

The single most tested idea: an index on (a, b, c) is sorted first by a, then by b within equal a, then by c within equal (a, b). So it can serve queries that use a prefix of those columns: a=?, a=? AND b=?, a=? AND b=? AND c=?. It cannot efficiently serve b=? alone, because b is only sorted within each a group. This is why column order is a design decision, not an alphabetical accident. The rule of thumb: equality-filtered columns first, then the column you sort or range-scan on last, so that after the equality prefix pins a contiguous slice, the sort column is already in order inside that slice and no separate sort step is needed.

Table

A composite index on (user_id, status, created_at) is one sorted entry list: WHERE user_id = 42 AND status = 'active' ORDER BY created_at seeks one contiguous slice, while a lone status filter has no single place to seek.

user_id	status	created_at	why this entry is here
7	active	2026-06-30	different user: outside the slice
42	active	2026-06-01	slice starts: the equality prefix (42, active) pins a contiguous run
42	active	2026-06-09	still inside the run
42	active	2026-06-20	and created_at is already in order, so no separate sort step
42	inactive	2026-04-11	same user, different status: the run has ended
99	active	2026-06-03	status = 'active' alone is scattered across every user_id group

A covering index (index-only scan) is the next lever. If the index contains every column the query needs, in its keys or as included non-key columns (Postgres INCLUDE, SQL Server included columns), the database answers entirely from the index and never touches the table/heap. That removes the second read per row and can turn a slow query fast, at the cost of a wider index.

Selectivity / cardinality decides whether the planner even uses your index. An index on a boolean is_active that is 95% true is nearly useless: matching most of the table via an index (random-ish lookups) is slower than a sequential full scan. High-cardinality columns (user_id, email) are the good candidates. The planner estimates rows returned and picks index versus full scan on cost; a stale statistics estimate is a classic cause of "it stopped using my index."

The cost side

Interview nuance: the cost side is where juniors get exposed. Every index is a second data structure the database must keep in sync on every insert, update, and delete. Ten indexes means one insert becomes eleven B-tree writes plus more WAL and more storage. Write-heavy tables should be deliberately under-indexed. Beyond the default B-tree, know the specialized types: hash (equality only, no ranges), partial (index only rows matching a predicate, e.g. WHERE status='active', keeping it tiny), and GIN/GiST (Postgres inverted/generalized indexes for arrays, JSONB, full-text, and geospatial).

Recap: pick the index by the query, order composite columns as equality-then-sort per the leftmost-prefix rule, make it covering when a hot query justifies the width, and remember every index taxes every write.