What a Database Index Actually Does — B-trees, Lookup Cost, and the Price of Writes

Infrastructure Performance Database Backend
4 min read

Indexes kept appearing as the prescription in When the Database Slows Down and the API diagnosis. This time the index itself is the subject: how it turns a 4-million-row scan into a handful of accesses and what it costs in return, from mechanics to working rules. Examples assume the relational default, the B-tree index.

Without an index — every lookup is a census #

The only way to find WHERE email = '...' in an unindexed table is to read every row from first to last and compare — a full scan. A million rows means a million comparisons and reading every disk page the table occupies. Double the data, double the cost: slowdown in direct proportion to growth.

An index changes the structure: it’s a separate, sorted data structure — like the index at the back of a book — maintaining “value → location” in value order. A lookup searches this index first, then jumps to the exact spot in the table.

The B-tree — why this structure in particular #

For fast search over sorted data, binary search comes to mind — but a database lives on disk with constant inserts and deletes. The B-tree fits that world.

  • Wide and shallow — one node maps to one disk page, and a page holds hundreds of keys, so the tree fans out hundreds of ways. A million rows or a billion, the height stays around 3–4 levels. Lookup cost changes from “proportional to rows” to “the tree’s height — effectively constant.” That is the essence of the index effect.
  • Stays sorted — leaf nodes link in value order, so beyond equality lookups, range queries (BETWEEN, >, ORDER BY, prefix LIKE 'kim%') find a start point and read sideways.
  • Survives churn — full pages split and the tree rebalances; no sorted-array-style mass shifting on every insert.

Where a full scan of a million-row table reads thousands of pages, a B-tree lookup reads 3–4. The “threshold crossing” from the database post follows from the same structure: the day the table outgrows the cache, a full scan becomes thousands of disk reads — the index lookup is still a few.

Composite indexes — column order is everything #

A composite index (team_id, created_at) is “sorted by team_id, then created_at within equal values” — a phone book sorted by (last name, first name), and the same rules apply.

  • WHERE team_id = 3 AND created_at > ... — used perfectly.
  • WHERE team_id = 3 — the leading column alone works (finding by last name only).
  • WHERE created_at > ... — cannot use it. Like searching a phone book knowing only the first name.

Hence the base rule for column order: frequent equality conditions first, ranges last. Also worth remembering: with an (A, B) index, a separate (A) index is usually redundant.

One step further is the covering index: if every column the query needs lives in the index, the jump to the table disappears entirely (index-only scan) — one more level shaved off your hottest list queries.

Not free — the index’s invoice #

If indexes were free wins, you’d index every column. The reasons you don’t:

  • A tax on every write — INSERT adds an entry to every index; UPDATE rewrites every index containing a changed column; DELETE likewise. An INSERT into a table with ten indexes is one table write plus ten index writes. Over-indexing a write-heavy table is itself a performance problem.
  • Storage — indexes consume disk and cache memory; systems where indexes outweigh the table are not rare.
  • Low cardinality pays little — columns with few distinct values (gender, boolean status) still leave half the table after narrowing, so the optimizer rationally ignores the index and scans.

The working rule compresses to: index columns that recur in WHERE, JOIN, and ORDER BY and hold diverse values. Then verify periodically that each index is actually used (every engine exposes usage stats) and still pays against the write load. An unused index is pure tax.

Indexed but not used — the last gate #

The cases where an index exists but the optimizer won’t touch it (transformed columns, implicit casts, stale statistics) were covered in the database post. The verdict tool is always EXPLAIN, and the ORM-side view is in Django Advanced #3. The point worth repeating here: “I added an index” and “the query uses the index” are two different statements.

Summary #

  • An index is a separate structure keeping “value → location” sorted, converting lookup cost from row-proportional to tree height (3–4 levels).
  • B-trees are wide and shallow for disk, and stay sorted — covering ranges and ORDER BY too.
  • In composite indexes, column order is everything: equality first, range last; conditions missing the leading column can’t use it.
  • Indexes tax every write and eat storage. Index recurring, diverse-valued columns only, and drop the unused ones.
  • Adding the index isn’t the end — EXPLAIN confirms the query actually takes it. That’s one full cycle.
X