Skip to content
System Design Lab
Design to Scale

Database Indexing

Why the same query gets slower every day as a table grows, how a B-tree index turns a full scan into a few page reads — and why every extra index makes writes pay.

Beginner 4 min read· Updated 2026-11-18

What you will learn

  • Explain the difference between a sequential scan and an index lookup.
  • Predict how query time grows with table size with and without an index.
  • Weigh the write cost of every index against the reads it speeds up.
  • Use EXPLAIN to check what the database actually does.

Overview

Finding a topic in a 1,000-page book by reading every page takes forever; the index at the back sends you to page 412 in seconds. A database index is the same idea: a sorted structure that points to the rows you want, so the database does not have to read them all.

Without an index, WHERE customer_id = ? makes the database read every row (a sequential scan), so the cost grows linearly with the table. A B-tree index keeps the column sorted in a shallow tree; a lookup walks a handful of levels, so the cost grows with log₂(rows) — 20 levels for a million rows, 30 for a billion.

Run it

In A the table grows with every order and each lookup scans it: watch Average read climb until the database saturates — with the same code and the same traffic. B adds one index. C has twelve: reads are fast, but look at Average write.

Loading simulation…

What an index costs

No indexOne indexMany indexes
Lookup by columnScan every rowWalk ~20 tree levelsWalk ~20 tree levels
Insert / updateWrite the rowRow + 1 index entryRow + N index entries
Disk and memoryTable only+ index sizeIndexes can outgrow the table
Grows with tableLinearlyLogarithmicallyLogarithmically (reads), linearly in N (writes)

In practice

Find the scan, add the right index, confirm
EXPLAIN ANALYZE SELECT id, total FROM orders WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20;
-- Seq Scan on orders  (rows=1,800,000)  Filter: customer_id = 42   ← reads everything

-- One composite index serves the filter AND the sort; CONCURRENTLY avoids locking writes.
CREATE INDEX CONCURRENTLY idx_orders_customer_created ON orders (customer_id, created_at DESC);

EXPLAIN ANALYZE SELECT id, total FROM orders WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20;
-- Index Scan using idx_orders_customer_created  (rows=20)   ← reads 20 rows

-- Find indexes nobody uses (they still slow every write):
SELECT relname, indexrelname, idx_scan FROM pg_stat_user_indexes WHERE idx_scan = 0;
  • Composite indexes: column order matters — equality columns first, then range or sort columns. (customer_id, created_at) serves WHERE customer_id = ? ORDER BY created_at, not WHERE created_at > ? alone.
  • Covering indexes (INCLUDE (total)) answer the query from the index without touching the table.
  • Selectivity: an index on a column with two values (is_active) rarely helps; the planner will scan anyway.

Trade-offs

BenefitsCosts
ReadsLookups stay fast as the table grows by orders of magnitude.Only queries that match the index's leading columns benefit.
WritesOne well-chosen index costs little.Every index is updated on every insert and update — write-heavy tables suffer.
ResourcesHot index pages stay in memory.Indexes use disk and buffer cache; bloated indexes need maintenance.

Production considerations

  • Index for your top queries by total time (pg_stat_statements), not for every column.
  • Create indexes concurrently on live tables, and drop unused ones.
  • Re-check plans after big data changes: a plan that was fine at 10k rows may scan at 10M.
  • Load-test with production-sized data — small test tables hide missing indexes.

Further reading

Related topics