Finding one row in a million
A table is, at its simplest, a long list of rows. Ask for the row with id = 43 and a database with no other information has only one option: read the rows one after another until it finds it.
The table: 64 rows
Start. Find the row with id 43. There is no index, so the database has no idea where it is. It starts at the first row.
- Index pages read
- 0
- Rows read
- 0
That is a full table scan. With 64 rows nobody notices. With a hundred million rows it is the difference between an instant page and a timeout.
An index is a second structure, kept next to the table, whose only job is to answer "where is the row with this value?" without reading everything. It is the same idea as the index at the back of a book.
The shape of an index: a B-tree
Most database indexes are B-trees. A B-tree is built from pages. Each page holds a sorted list of entries, and each entry says: values in this range are on that page below.
Start at the root page
There is exactly one. It splits the whole range of values into a few broad slices.
Find the slice containing your value and follow it down
You arrive at a page that splits that slice more finely. Every other slice is skipped, along with everything beneath it.
Repeat until you reach a leaf page
Leaf pages point at the actual rows.
The table: 64 rows
Start. Find the row with id 43, using the index. Every lookup starts at the root page of the tree.
- Index pages read
- 0
- Rows read
- 0
Three pages read instead of 43 rows. And the gap widens fast as the table grows.
Why it stays shallow
The demo's pages hold 4 entries each so that they fit on screen. Real pages hold hundreds. Each level of the tree multiplies the number of rows it can reach by that amount.
Example
100 entries per page
One level reaches 100 rows. Two levels reach 10,000. Three levels reach 1,000,000. Four levels reach 100,000,000.
A hundred times more rows costs one more hop.
That is why a lookup by an indexed column feels instant whether the table has a thousand rows or a billion. The work grows with the number of levels, not the number of rows.
Because the entries are sorted, the same tree also answers range questions. To find every order between two dates, walk down to the first date and then read along the leaf pages until the last.
Same query, different plan
The striking thing about adding an index is what does not change: your query.
SELECT * FROM orders WHERE customer_id = 43; -- reads every row
CREATE INDEX orders_customer_id ON orders (customer_id);
SELECT * FROM orders WHERE customer_id = 43; -- three hopsThe database decides for itself whether to use an index. To see what it chose, put EXPLAIN in front of the query.
The table: 64 rows
Start. Find the row with id 43, using the index. Every lookup starts at the root page of the tree.
- Index pages read
- 0
- Rows read
- 0
What an index costs
Good at
- Lookups and range queries on the indexed column become fast at any table size
- Can also speed up sorting and joining on that column
Where it bites
- Every insert, update and delete must also update each index, so writes get slower
- Each index takes disk space and memory
- An index nobody uses still costs on every write
So the rule is not "index everything". Index the columns you actually search, join or sort by.
When an index is ignored
An index is sorted by the stored value. Anything that hides that order makes it useless for the query.
| Query | Uses the index on the column? | Why |
|---|---|---|
WHERE email = 'a@b.com' | Yes | Exact value: walk straight to it |
WHERE name LIKE 'Ada%' | Yes | All names starting with Ada sit together |
WHERE name LIKE '%son' | No | Names ending in "son" are scattered everywhere |
WHERE LOWER(email) = 'a@b.com' | No | The index stores email, not LOWER(email) |
WHERE active = true when most rows are active | Usually not | Reading most of the table is quicker with a scan |
Key takeaways
- Without an index, finding a row means reading the table from the start.
- A B-tree index is a tree of sorted pages. Each page narrows the search to one slice.
- With hundreds of entries per page, three or four hops reach millions of rows.
- Adding an index changes how a query runs without changing the query.
- Indexes speed up reads and slow down writes, so add them where queries need them.