Indexes
- Lesson 10 of 40
- 12 min
- Beginner
- 11 steps
An index turns a scan of millions of rows into a handful of reads. You will see how a B-tree works, what it costs to keep up to date and when it does nothing at all.
- Query p95
- 1 ms
- Rows read
- 1
- Writes per insert
- 3
- Indexes
- 2
- request
- response
- slow request
Step 1 of 11
Problem
Looking up one user takes two seconds
To log in, the app looks the user up by email. With 50 million rows (example figures), the query takes over two seconds and gets worse as the table grows.
With nothing to guide it, the database runs a full table scan: it reads every page of the table and checks row after row. Watch the slow request crawl towards the table.
Step 2 of 11
Concept
What a phone book does
Nobody finds a name in a phone book by reading it page by page. Because it is sorted, you open it in the middle, check whether the name comes before or after, and drop the other half. Then you repeat.
Halving 50 million again and again leaves a single entry after about 26 steps, because 2 to the power of 26 is already more than 67 million.
Step 3 of 11
Solution
Create an index
CREATE INDEX ON users (email) builds a B-tree: a small structure of sorted keys. The root says which branch holds your email and the leaf points to the exact page where the row lives.
A handful of hops instead of fifty million rows (the drawing squeezes the tree into two levels): the lookup drops to about 2 ms. In exchange, every INSERT now writes to two places; you will see it in two steps.
What changed
- B-tree index on email
- Rows read: 50,000,000 → 1
- p95: 2.3 s → 2 ms
- Writes per insert: 1 → 2
Step 4 of 11
Technique
Why a B-tree stays so short
Each tree node fills one disk page with hundreds of keys, so every level multiplies the rows it can reach by hundreds.
With 500 keys per node (example value), 3 levels already cover 125 million rows: our 50 million fit with room to spare. The top levels are used so often that they usually stay in memory.
Step 5 of 11
Trade-off
Every index makes writes more expensive
When someone signs up, the new row goes into the table and also into every index, which has to stay sorted. Watch both writes: one lands in the table and the other walks down the tree to its leaf.
Indexes also take disk and memory. Index what you query, not everything there is.
What changed
- INSERT writes to the table and the index
- Writes per insert: 2 (1 table + 1 index)
Step 6 of 11
Technique
Composite indexes: order matters
An index can span several columns, such as (country, city). It is sorted by country first and, within each country, by city: just like a list sorted by surname and then by first name.
It serves lookups by country, or by country and city. A query on city alone cannot use it and falls back to a full scan: over two seconds again.
What changed
- Composite index (country, city)
- City-only query → full scan
- Writes per insert: 2 → 3
Step 7 of 11
Problem
Case: queries the index cannot answer
You are asked for every user on one domain: WHERE email LIKE '%@example.com'. The index is sorted by the start of each email and this pattern says nothing about the start, so the whole table has to be scanned.
Functions do the same: WHERE LOWER(email) = … cannot use a plain index on email, because the index stores the values exactly as they were written.
What changed
- Query with a leading wildcard
- Index ignored → full scan
Step 8 of 11
Problem
Case: the index nobody uses
Support wants every user in one country: WHERE country = 'MX'. You add an index on country… and the database ignores it, because in this example 40% of the rows match.
Following the index would mean jumping to a different table page for each of 20 million rows: slower than reading the table from start to end. An index pays off when it is selective, that is, when it narrows the search to a small fraction of the rows.
What changed
- Index on country
- 40% of rows match → full scan anyway
- Writes per insert: 3 → 4, for no gain
Step 9 of 11
Technique
Ask the database: EXPLAIN
No need to guess. Put EXPLAIN in front of a query and the database shows its plan: which index it will use and how many rows it expects to read.
«Index Scan» over a few rows is good news. «Seq Scan» over a big table is the warning sign. EXPLAIN ANALYZE actually runs the query and adds the real timings.
What changed
- Query plan in sight
- Index on country dropped
- Writes per insert: 4 → 3
Step 10 of 11
Technique
Covering indexes: skip the table
The login screen only needs the user's id and name. If the index stores those columns too, the database answers from the index alone and never visits the table pages.
That is an index that covers the query (a covering index). Watch: lookups now end at the leaf and no longer reach the table; in this example p95 drops to 1 ms.
What changed
- Index includes id and name
- Table reads for this query
- p95: 2 ms → 1 ms
Step 11 of 11
Summary
Recap
Without an index, finding one row means scanning the whole table.
A B-tree index reaches any row in a handful of page reads.
Every index adds work to every write: index what you query.
A composite index is used from its leftmost column.
Leading wildcards, functions and low selectivity defeat an index; check with EXPLAIN.
← → step · R replay · Space pause
You will learn
- What scanning the whole table costs (covered)
- How a B-tree index finds a row (covered)
- What every write pays for having indexes (covered)
- Composite indexes and the order of their columns (covered)
- When an index does not help and how to check (covered)