Tags: web-dev concept

Indexing

Date: 2026-08-17

---

A separate sorted structure that lets the database find rows without reading every one. It makes reads dramatically faster and writes slightly slower — and the second half is why “index everything” is not the answer.

---

An index is an auxiliary data structure maintained alongside a table, ordered by one or more columns, that lets the database locate matching rows without a full scan.

WITHOUT INDEX              WITH INDEX
read every row             binary search
1,000,000 comparisons      ~20 comparisons
O(n)                       O(log n)

That’s the same jump as linear versus binary search, because it’s the same mechanism — the index is the sorted copy.

The shape

Nearly every index is a B-tree — a balanced tree kept shallow so any lookup is a handful of disk reads:

                [ M ]
           ┌──────┴──────┐
        [ D  H ]      [ R  W ]
        ┌─┼─┐          ┌─┼─┐
      leaves → row pointers,
               linked in order

The leaves are linked, which is why a B-tree serves range queries (BETWEEN, >, ORDER BY) as well as exact matches — you find the start and walk. A hash index is faster for exact equality and useless for ranges, which is why B-trees are the default.

Composite indexes and the left-prefix rule

An index on several columns is ordered by the first, then the second within that, and so on — like a phone book sorted by surname then first name.

INDEX (customer_id, created_at)

USES THE INDEX
WHERE customer_id = 7
WHERE customer_id = 7 AND created_at > x
WHERE customer_id = 7 ORDER BY created_at

DOES NOT
WHERE created_at > x
  ← no customer_id. You cannot look up
    a first name in a phone book sorted
    by surname

Column order is the whole design decision. (a, b) and (b, a) serve different queries, and getting it wrong produces an index that exists, costs writes, and is never used.

Equality columns first, then range columns, is the rule that gets it right most of the time.

What makes an index useless

• A function on the column — WHERE LOWER(email) = 'x' makes the index on email unusable. Index the expression instead
• A leading wildcard — WHERE name LIKE '%serum' can’t binary-search a suffix
• Type mismatch — WHERE id = '42' against an integer column forces an implicit conversion, and a scan
• Low selectivity — WHERE active = true where 95% are true. A scan is genuinely cheaper, and the planner is right to choose it
• OR across columns often defeats a composite index

The costs

WRITES     every INSERT, UPDATE and DELETE
           must update every affected index
DISK       an index can rival the table's
           own size
PLANNING   more choices to evaluate
MEMORY     indexes compete for cache

A table with twelve indexes has slow writes, and this is the usual state of a table nobody has audited. Unused indexes are pure cost — most databases can report index usage, and dropping the ones with zero reads is free performance.

Covering indexes

An index containing every column a query needs answers it without touching the table at all:

SELECT customer_id, created_at
FROM orders
WHERE customer_id = 7

With INDEX (customer_id, created_at) the index holds both columns, so there is no table lookup at all.

A significant win for hot queries, and worth reaching for when a specific query dominates.

Practical rules

• Index foreign keys. Rarely automatic, and their absence makes joins and cascading deletes slow
• Index what you filter, join and sort by — not what you select
• Measure, don’t assume. EXPLAIN tells you what the planner actually does — Query Planning
• Add indexes for real queries, not anticipated ones
• Creating an index locks the table in some systems. On a large production table, use the concurrent or online variant — Database Migrations
• Every index is a bet that reads matter more than writes here. State the bet, and check it later