Database indexes

Pages read with and without an index, and what each index costs a write.

On the roadmap:Beginner · step 4: Databases 101

Starterabout 10 to 15 min6 experiments

Experiments

New here? A few short steps show what happens, one at a time.

Settings

Rows in the table10 million

Indexes on the table1

Keys that fit in one index page200

Rows a range query returns100

What the data is stored on

A table page holds 100 rows here. Costs count pages read, and time uses 0.1 ms a page on this storage.

Index levels

Table pages

100,000

Pages touched per insert

Index space

240 MB

Finding one row by an indexed column reads 5 pages (0.50 ms). Without an index it reads 100,000 (10 s), 20,000 times more. The price: each insert now touches 5 pages and writes 2.

Pages read, on a scale where each step is ten times more

One row by an indexed column
5 pages · 0.50 ms
WHERE id = 42. 4 index levels, then one table page.
One row by a column with no index
100,000 pages · 10 s
WHERE email = '[email protected]'. Nothing to follow, so it reads the whole table.
A range by an indexed column
105 pages · 11 ms
WHERE created BETWEEN … (100 rows). Walk the leaves, then fetch each row's table page.
The same range, answered from the index alone
5 pages · 0.50 ms
SELECT created … (covering index). The index holds every column asked for, so the table is never read.
Names that start with 'abc'
105 pages · 11 ms
WHERE name LIKE 'abc%'. A known start is a range in a sorted index.
Names that contain 'abc'
100,000 pages · 10 s
WHERE name LIKE '%abc%'. No known start, so the order of the index does not help. It reads everything.
Only the second column of an index on (a, b)
100,000 pages · 10 s
WHERE b = 7. The index is sorted by a first. Without a, b is scattered through it.
Sort by a column with no index
200,000 pages · 20 s
ORDER BY score DESC LIMIT 10. Reads everything and sorts it.

In plain words

A database reads its data in pages, each holding many rows. Without an index it must read every page to find a row. A B-tree index is a small sorted tree that finds a row in a handful of page reads, at the cost of extra work on every write.

Why it matters

Indexes are the first thing to try when a query is slow, and the first thing to question when writes are slow. Here the same query is answered with and without an index, for a table from a thousand rows to a billion, and you can see which kinds of query an index helps, which it cannot, and what each index costs.

How real systems do it

The simulation is a simplified model. Here is what production systems add or do.

Most relational databases store indexes as B-trees (or B+ trees). A table with millions of rows usually needs only three or four levels, because each page holds hundreds of keys.
PostgreSQL pages are 8 KB and MySQL's InnoDB pages are 16 KB by default, so a page holds many rows or many index entries.
A composite index on (a, b) can serve a query on a, or on a and b, but not on b alone: the leftmost column comes first. A search such as LIKE '%abc%' cannot use an ordinary B-tree either.
A covering index holds every column a query needs, so the database never reads the table. PostgreSQL calls this an index-only scan. Each extra index slows inserts and updates and takes space.