Database fundamentals

Almost always a B+ tree: a shallow, wide, sorted structure whose leaf nodes hold the indexed values in order along with pointers back to the rows. Shallow and wide is the whole point, because each level is one disk page, so finding a value among a hundred million rows takes three or four page reads rather than a scan. The structure being sorted is what makes range queries, prefix matches and ORDER BY on the indexed column cheap as well as equality lookups.

A hash index answers equality in one step and cannot answer anything else — no ranges, no sorting, no prefix matching, no "greater than". A B+ tree gives up a little equality speed to keep the data ordered, and ordering is what most real queries need. The leaves are also linked, so once you have found the start of a range you walk sideways through the leaf pages rather than descending the tree again for each row.

The property that matters is that depth grows logarithmically with a very large base, so the tree is almost flat even at enormous row counts.

Each page is one disk read and holds a few hundred keys, so the fan-out per level is in the hundreds rather than two.

fan-out 300, rows addressed per level
  depth 1        300
  depth 2     90,000
  depth 3 27,000,000
  depth 4  8.1 billion

So a lookup in a 27-million-row table is three page reads, and the upper
levels are almost always already in memory — often one physical read.

Two consequences follow. Adding rows barely deepens the tree, which is why index performance degrades gracefully rather than falling off a cliff — the thing that actually degrades is cache residency once the index stops fitting in memory. And the dotted links between leaves are what make ranges cheap: having descended once to find the start, the engine walks sideways through leaf pages instead of re-descending for every row, so returning ten thousand rows in a range costs barely more than finding the first one.

A clustered index determines the physical order of the rows, so the table is the index and there can be only one. A non-clustered index is a separate structure holding the key plus a reference back to the row. The consequence is that a non-clustered lookup usually costs an extra step to fetch the row — the bookmark or heap lookup — and that step is why the optimiser sometimes prefers a full scan over an index it could have used.

An index on (a, b) is sorted by a first, then by b within each value of a, exactly like a phone book sorted by surname then forename.

INDEX (customer_id, created_at)

  customer_id | created_at
  ------------+------------
  1001        | 2026-01-04     <- sorted by customer, then date within customer
  1001        | 2026-03-19
  1001        | 2026-07-02
  1002        | 2026-02-11
  1002        | 2026-06-30

Now three queries against it:

-- Uses the index fully. Seeks to customer 1001, then walks the date range.
WHERE customer_id = 1001 AND created_at > '2026-02-01';

-- Uses the index. A leading-column-only predicate is a clean prefix.
WHERE customer_id = 1001;

-- Cannot seek. Dates are only ordered *within* a customer, so rows for
-- 2026-06-30 are scattered across the whole index.
WHERE created_at > '2026-06-01';

This is the leftmost prefix rule: an index on (a, b, c) serves predicates on a, on a, b, and on a, b, c, but not on b alone or c alone. Trying to find a surname when you only know the forename means reading the entire book.

Two refinements worth offering unprompted. The first is that the last usable column may be a range — a = ? AND b > ? seeks fine, but a > ? AND b = ? stops seeking at a, because once you are scanning a range of a the ordering of b no longer helps. The second is that the rule kills duplicate indexes: if you have (a, b) you do not also need (a), and noticing that in a review removes write cost for free.

An index containing every column a query needs, so the database answers from the index alone and never touches the table. That removes the row lookup entirely, which on a query returning many rows is often the difference between fast and unusable. Most engines let you append non-key columns for exactly this purpose, which keeps them out of the sorted key — cheaper to maintain — while still making the index self-sufficient for that query.

Because the index stores the column's values, not the function's results. Once you write WHERE lower(email) = 'x' or WHERE year(created_at) = 2026, the database cannot use the sorted order of email or created_at, so it evaluates the function for every row. The fixes are to rewrite the predicate as a range — created_at >= '2026-01-01' AND created_at < '2027-01-01' — or to create an index on the expression itself where the engine supports it.

Because an index only pays for itself when it eliminates most of the table. An index on a boolean matching half the rows means the engine would do a lookup for every second row, which is more random I/O than reading the table sequentially, so the optimiser correctly ignores it. The exception is a skewed distribution — a status where 0.1% of rows are failed — and a partial index covering only those rows is both small and genuinely selective.

Storage, memory, and write amplification. Every insert, delete and update to an indexed column must maintain every affected index, so a table with eight indexes does roughly nine writes per row change, and each one competes for the same buffer cache the table wanted. That is why the correct number of indexes is the smallest set covering the queries you actually run, and why finding unused indexes is one of the cheapest performance wins available.