Step 1 A table is just pages on disk
A table's rows do not float freely — they live in fixed-size pages, and the database reads and writes whole pages at a time. Our demo table has 200 rows packed 8 to a page, for 25 pages total; without an index, finding one row means reading every page in order.
Run a query with no index
No pages read yet.
Step 2 A B-tree keeps keys sorted in a wide, shallow tree
An index is a separate, always-sorted structure: a B-tree. Each node holds a handful of keys; when a node would overflow it splits and pushes a key up, which is why the tree grows wide (many keys per level) long before it grows tall.
Build a B-tree (order 4 — max 3 keys per node)
Empty tree — one root, no keys yet.
Step 3 A lookup walks root to leaf
With an index, the same query no longer touches every page. It compares against a few keys at the root, follows one child pointer, and repeats — a handful of page reads instead of a full scan, however big the table grows.
Run the same query, indexed — over a balanced index of all 200 ids
pages read:
Step 4 Range queries love sorted leaves
Leaf pages are linked to their neighbor in sorted order, so a range scan only descends the tree once, then walks sideways — that leaf walk never touches a page outside the requested range. But this index doesn't cover the query, so every matched row still has to be fetched from the table afterward: widen the range enough and it touches most of the table's own pages anyway, at which point a full scan is cheaper.
Run a range query, indexed
Step 5 Composite indexes and the leftmost prefix
An index on (country, city) is sorted by country first, then city within each country. That means it only helps a query that filters on a leftmost prefix of its columns — country alone, or country-then-city, but not city alone.
Index on (country, city) — 30 rows, 5 countries
| country | city |
|---|
Click a query above to see whether the composite index helps.
Step 6 When indexes are skipped or hurt
Having an index does not guarantee it gets used. The query planner skips it whenever the predicate can't be matched against sorted keys, or when using it would cost more than just reading the table — and every index also taxes every write.
A function on the column
WHERE lower(email) = 'a@b.com'
Low selectivity
WHERE active = 1 (99% of rows are)
Leading wildcard
WHERE name LIKE '%son'
Write cost
Every INSERT also updates every index on the table.
Step 7 Try it for real
These demos are illustrative — to see a real query planner's decision, open /sqllab, create a table with and without an index, and prefix a query with EXPLAIN QUERY PLAN. For the rest of the "how it works" series, see /learn/git.
Step 8 Glossary
| Term | In one sentence |
|---|---|
page | The fixed-size chunk a database reads and writes as one disk unit; a table's rows are packed into many pages. |
heap / table | The table's own storage — rows in no particular order the query planner can rely on, unless the table itself is indexed. |
B-tree | A balanced, sorted tree structure most indexes are built from; every leaf sits at the same depth. |
root / internal / leaf | The top node (root), the middle layers that route a search (internal), and the bottom layer holding the actual keys (leaf). |
fan-out | How many children one node can have; a higher fan-out means a shallower tree for the same number of keys. |
selectivity | The fraction of rows a condition matches; low selectivity (most rows match) makes an index less useful. |
composite index | An index built over more than one column, sorted by the first column, then the next within each group. |
leftmost prefix | The rule that a composite index only helps a query filtering on its columns starting from the first one. |
covering index | An index that already holds every column a query needs, so it never has to visit the table itself. |
query planner | The part of the database that decides, per query, whether an index is worth using or a scan is cheaper. |
full table scan | Reading every page of a table to check each row, because no index narrows the search. |
The whole idea: an index trades a small amount of extra storage and write cost for a sorted shortcut a scan doesn't have — and the planner only takes that shortcut when the query actually lines up with how the index is sorted.