Database Indexing — Algorithmics

A table with ten million rows. WHERE email = 'a@b.com' reads all ten million to find one.

An index is a second, sorted copy of one or more columns, with pointers back to the rows. Finding the email becomes a binary search — about 24 comparisons instead of ten million reads.

Why B-trees and not hash maps

A hash map gives $O(1)$ lookup, better than a tree’s $O(\log n)$ . Databases use trees anyway, for three reasons.

Range queries. WHERE created_at > '2026-01-01' is a scan of adjacent leaf pages in a tree. A hash index cannot answer it at all — hashing deliberately destroys the ordering.

Sorted output for free. ORDER BY over an indexed column needs no sort step.

Disk shape. A B-tree node is one page — 8 kB in Postgres, holding hundreds of keys. A tree over a billion rows is 4–5 levels deep, so a lookup is 4–5 page reads, and the top levels are always in memory. Everything about the structure is designed around the fact that a random disk read is enormously more expensive than a sequential one.

Composite indexes: the leftmost prefix rule

An index on (country, city, name) sorts by country, then city, then name — like a phone book sorted by surname, then first name.

UK · London · Ada

UK · London · Bob

UK · York · Cai

US · Austin · Dee

Which queries can use it?

Query	Uses the index?
`WHERE country = 'UK'`	yes
`WHERE country = 'UK' AND city = 'London'`	yes
`WHERE country = 'UK' AND city = 'London' AND name = 'Ada'`	yes, fully
`WHERE city = 'London'`	no
`WHERE country = 'UK' AND name = 'Ada'`	partly — country only

Column order is therefore a design decision. Equality columns first, then the range column, then anything needed for ordering. A range predicate stops the index being usable for columns after it, for exactly the reason above.

What stops an index being used

A function on the column disables it

WHERE LOWER(email) = 'a@b.com'      -- index on email: not used
WHERE email = 'a@b.com'             -- used
WHERE created_at::date = '2026-01-01'   -- not used
WHERE created_at >= '2026-01-01' AND created_at < '2026-01-02'   -- used

The index stores email, not LOWER(email). Postgres can index the expression if you ask (CREATE INDEX ON users (LOWER(email))), but the plain index is useless here.

Same for implicit type casts, which is why comparing a varchar column to an integer quietly turns into a full scan.

Leading wildcards. LIKE '%son' cannot use a B-tree; LIKE 'John%' can, because it is a prefix range.

Low selectivity. An index on a boolean matching half the table is slower than a scan — random access per row costs more than reading sequentially. The planner knows this and will ignore your index, correctly.

What indexes cost

Every index must be updated on every write, so a table with eight indexes does nine writes per insert. Indexes also consume memory that would otherwise cache data pages.

The practical guidance: index what you filter and join on, drop indexes nothing uses (pg_stat_user_indexes will tell you), and be suspicious of any table with more than about five.

Covering index

If an index contains every column a query needs, the database never reads the table at all — an index-only scan.

CREATE INDEX ON orders (customer_id) INCLUDE (total, created_at);

This is often a 10× improvement for a hot query, and it is the first thing to try after the index itself. The cost is a wider index, which means fewer entries per page and a slightly taller tree.

Read the plan

Stop guessing:

EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'a@b.com';

Seq Scan on a large table with a selective filter means your index is not being used, and the plan usually shows why. Index Scan followed by a large “Rows Removed by Filter” means the index got you close but the predicate is doing the real work — often a sign the column order is wrong.