System designCore10 min

Database indexing

An index turns "read every row" into "read five pages". It is the single biggest lever on database speed, and also a cost on every write, a copy to store, and a promise the query planner may decide not to keep. This page covers how indexes work, which queries they serve, and when they don't.

1 · The problem

Without an index, finding one parcel means reading all 200 million

A parcel-delivery company keeps every parcel in one table: 200 million rows of about 200 bytes each, with a tracking number, the customer, when it was created, its status and the address. A customer types TRK-88213 into the tracking page.

Databases read and write in fixed-size pages, usually 8 KB, so about 40 rows fit on each page and the table fills 200,000,000 ÷ 40 = 5 million pages. With no index, the only way to find TRK-88213 is a full table scan: read every page and check every row. Even from memory that is a lot of work for one row, and the tracking page is opened thousands of times a minute.

An index is a separate structure that stores the values of one or more columns in sorted order, each with a pointer to its row. The usual kind is a B-tree: a shallow tree of pages, where each page holds hundreds of sorted keys and points to the pages below it.

Four index pages and one table page: 5 page reads instead of 5 million. The upper levels are read so often that they almost always sit in memory.

2 · How it works

A sorted index answers equality, ranges and order

Why only four levels? If each index page holds about 300 entries, every extra level multiplies the reach by 300: three levels cover 300³ = 27 million rows, four cover 300⁴ = 8.1 billion. The tree grows with the logarithm of the table:

Levels = the smallest whole number L with 300^L ≥ rows; 6 on the axis means a million rows, 9 a billion. Each new level arrives only after 300 times more rows. Real fan-out depends on key size; it is usually in the hundreds.

Because the keys are sorted, a B-tree serves much more than exact matches:

Query on tracking_no	Uses the B-tree?	Why
`= 'TRK-88213'`	Yes	Walk down to one key
`BETWEEN 'TRK-88000' AND 'TRK-88999'`	Yes	Walk to the first key, then read along the leaves
`LIKE 'TRK-882%'`	Yes	A fixed prefix is a range
`ORDER BY tracking_no LIMIT 50`	Yes	The leaves are already in order
`LIKE '%8213'`	No	Without the first characters there is no place to start

A hash index stores a hash of each key instead. It answers only exact matches: no ranges, no prefixes, no ordering. B-trees are the default almost everywhere because they do all of these. Search inside text, like the last row, needs a different structure altogether (Search & inverted indexes).

3 · Composite indexes

Column order decides which queries a composite index serves

The busiest query on the customer app is "my parcels, newest first":

WHERE customer_id = 7731 ORDER BY created_at DESC LIMIT 20

An index on customer_id alone finds the customer's 400 parcels, then sorts them. A composite index on (customer_id, created_at) sorts entries by customer, and by time within each customer, so the 20 newest are simply the last 20 entries of that customer's stretch: no sort at all.

The column order matters. Think of a phone book sorted by last name, then first name: it finds every "Okafor" and "Okafor, Ada", but it can't find every "Ada". The rule is the leftmost prefix: an index on (a, b, c) can look up a, a and b, or a, b and c, but not b or c alone.

Query	Index (customer_id, created_at)?
`customer_id = 7731`	Yes
`customer_id = 7731 AND created_at > '2026-09-01'`	Yes: equality first, then the range
`customer_id = 7731 ORDER BY created_at DESC`	Yes, and no sort is needed
`created_at > '2026-09-01'` (all customers)	No: created_at isn't the leading column

So put columns compared with = first and the one used for a range or a sort last. Don't add columns just in case: each one makes the index bigger, and indexes of more than three columns rarely help unless the queries are very uniform.

4 · Covering indexes

An index that holds every column a query needs skips the table

The tracking page needs only two things: the status and the last update time. With an index on tracking_no, the database still follows the pointer to the table page for those two columns. Add them to the index as extra, non-searchable payload, and the lookup never touches the table. That is a covering index, and the plan is an index-only scan:

Indexes for the parcel table

sql

-- tracking page: one lookup, answered from the index alone
CREATE UNIQUE INDEX parcels_tracking
  ON parcels (tracking_no) INCLUDE (status, updated_at);

-- "my parcels, newest first"
CREATE INDEX parcels_customer_recent
  ON parcels (customer_id, created_at);

Two caveats. Every included column makes the index larger and slower to update, so include only small columns used by hot queries. And in PostgreSQL, an index-only scan still checks the table for rows that changed recently, so it pays off most on data that doesn't change often.

5 · The catch

An index that matches too many rows is slower than reading everything

Operations wants every parcel currently in_transit, about 5% of the table, and adds an index on status. The database ignores it and scans the table. It is right to. Each matching row may sit on a different page, so the index costs one scattered page read per row, while a scan reads pages in order, which is cheaper per page. PostgreSQL's planner assumes, by default, that a scattered read costs 4 times a sequential one:

Index scan: matched rows × 4
Full scan: 5 million pages × 1

Planner's default model on the 200-million-row table. The lines cross at 5,000,000 ÷ (200,000,000 × 4) = 0.625% of rows. In transit, at 5%, would cost 40 million: the scan wins easily.

The crossover moves in practice: rows stored in index order share pages, caches make scattered reads cheaper, and planners can sort page fetches before reading. The principle holds.

What matters is selectivity, the share of rows a condition matches, and it depends on the value, not just the column:

status = 'in_transit' matches 10 million rows: the index is useless.
status = 'exception' matches 40,000 rows, 0.02%: about 160,000 in cost units against 5 million, so the same index is used.

This is why "don't index columns with few distinct values" is only half right. It is the common values that defeat the index; the rare ones are often exactly what you want it for.

6 · The price

Every index makes every write a little slower

An index is a second copy of some of the data, kept in sync by the database on every change. A new parcel with five indexes on the table means six structures updated: the table and each index. Changing an indexed column means removing the old entry and adding a new one. The costs add up:

Cost	What it means for the parcel table
Write work	Each insert, update or delete touches every affected index
Storage and memory	Each index takes disk space and competes for cache with the table
Building one	In PostgreSQL, a plain CREATE INDEX blocks writes until it finishes; build it concurrently on a live table
Unused indexes	Pay all of the above for nothing; find and drop them

Distributed databases add one more cost. In DynamoDB, a global secondary index is a separate copy of the data, partitioned by a different key, updated asynchronously: normally within a fraction of a second, but a read from the index can briefly miss a write the table already has. If the index can't keep up with the table's writes, the table's writes are slowed down too.

How an index is laid out on disk, and why some databases trade B-trees for log-structured designs that make writes cheaper, is the subject of Storage engines: B-trees, LSM trees & WAL.

7 · In practice

Index the queries you run, then check the plan

Indexes follow queries, not columns. List the hot queries, design an index for each, and then confirm with the database's EXPLAIN that it is actually used. The usual reasons it isn't:

The query	Why the index is skipped	Fix
`WHERE lower(email) = 'ada@x.example'`	The index holds email, not lower(email)	An index on the expression lower(email)
`WHERE address LIKE '%Main St%'`	No fixed prefix to start from	A full-text index (Search & inverted indexes)
`WHERE status = 'in_transit'`	Matches too many rows	Nothing: the scan is the right plan; or index a narrower question
`WHERE created_at > …` on (customer_id, created_at)	Not the leading column	Another index led by created_at, if the query is hot

A checklist:

Start from the slowest frequent queries, not from the schema.
Order composite columns: equality first, then the range or sort column.
Cover the hottest lookups with small included columns.
Check selectivity: an index helps when a condition matches a small share of rows.
Count the indexes on write-heavy tables, and drop the ones nothing uses.
Build indexes on live tables without blocking writes, and read the plan after every change.

Check yourself

5 questions

1. The parcels table has an index on (customer_id, created_at). Which query can't use it to find rows?

2. Operations adds an index on status, but the query for status = 'in_transit' (5% of 200 million rows) still scans the whole table. Why?

3. The table has an index on email, but WHERE lower(email) = 'ada@x.example' scans the table. What fixes it?

4. A B-tree with about 300 entries per page has 4 levels at 200 million rows. Roughly how many levels will it have at 2 billion rows?

5. Inserts into the parcels table have slowed down since the team added several indexes. What is the most likely reason?

Takeaways

Remember this

An index is a sorted copy of some columns with pointers to rows; a B-tree finds one row in a handful of page reads instead of scanning millions.
B-trees serve equality, ranges, prefixes and ordering; leading wildcards and functions on the column defeat them.
A composite index serves its leftmost prefix: put equality columns first and the range or sort column last.
An index helps only when the condition matches a small share of rows; it is the common values that make it useless.
Every index costs every write, storage and memory, so index the queries you run and drop the rest.