An index is a sorted structure the database can walk instead of reading every row. Grow the table, change the query, and watch rows-examined either stay flat or climb with the table — then look at what the index costs you on every write.
depth 6
Full table scan
4,096
rows examined
Index lookup
1
rows examined
Rows examined, index vs scan4096× fewer
Indexes: Paying on Write to Stop Reading Everything
The single biggest lever on query performance, and the easiest one to disable by accident.
Quick Context
Without an index, finding the rows that match a condition means reading every row and testing it — a full table scan, and its cost grows in a straight line with the size of the table. That is perfectly fine on ten thousand rows and ruinous on ten million.
An index is a second structure, kept sorted on one or more columns, that the database can descend instead. Its cost grows with the logarithm of the table size, which is why the same query stays fast as the table grows by three orders of magnitude in the lab above.
Why a B-tree
Almost every relational index is a B-tree: a balanced tree whose nodes are disk pages holding many keys each. Every leaf sits at the same depth, so every lookup costs the same. Because a page holds hundreds of keys, the tree is astonishingly shallow — with a fanout of a few hundred, three or four levels is enough for hundreds of millions of rows.
The tree drawn above uses a fanout of 4 so that it fits on a screen. The depth it reports is the honest depth for that fanout; the readout beside it converts to a realistic fanout of 200, which is closer to what a real page holds.
Leaf pages are also linked to their neighbours, which is what makes a range query cheap: descend once, then walk sideways. It is also why an index can satisfy an ORDER BY with no sort at all — the leaves are already in order.
The queries an index cannot help
An index is sorted by the value of the column. Anything that destroys that ordering makes it useless — the term for a condition an index can serve is sargable.
A leading wildcard.LIKE 'Sha%' is a prefix, so it is a contiguous range of the index. LIKE '%son' is not: rows ending in "son" are scattered all over the sorted order, so the engine reads everything.
A function on the column.LOWER(email) = '...' asks about a value the index does not store. The fix is an expression index on LOWER(email), or storing the normalised value in its own column.
Arithmetic on the column.WHERE salary * 12 > 100000 is not sargable; WHERE salary > 100000 / 12 is exactly the same question and is.
An implicit type cast. Comparing an indexed integer column to a string, or a varchar to a number, can silently force a cast on the column side and cost you the index.
Composite indexes and the leftmost rule
An index on (a, b) is sorted by a first and by b only within equal values of a. So it serves WHERE a = ? and WHERE a = ? AND b = ?, but not WHERE b = ? alone — the b values are scattered. Column order in a composite index is a design decision, not a formality.
If an index happens to contain every column a query needs, the engine can answer from the index alone without touching the table at all. That is a covering index, and it is often the difference between fast and very fast.
What it costs
Every index is a copy of some of your data that has to be kept correct. An INSERT writes the row once and then updates every index on the table; an UPDATE touches the indexes whose columns changed; a DELETE removes the entry from all of them. Eight indexes turn one write into nine, which is what the write-cost readout is showing.
They also take space, and they can be ignored: when a condition matches a large fraction of the table, the planner will often choose a scan anyway, because reading the table in order beats jumping to scattered rows one at a time. An index on a column with only a handful of distinct values — a boolean, a status flag — is usually not worth having for that reason.
Index the columns you filter, join and sort on. Then check with EXPLAIN, which tells you what the planner actually chose rather than what you hoped it would.
Interactive Exploration Guide
Grow the table. With the equality query and the index on, drag Table Rows from 16 to a million. Rows examined by the scan tracks the table exactly; rows examined by the index stays at 1, and the tree gains a level roughly every time the table quadruples.
Turn the index off. Uncheck Index On That Column. The same query now reads every row — this is the identical query text with a thousand-fold difference in work.
Try a range. Switch to the BETWEEN query. The index still descends once, then walks the leaves sideways, so it examines about 5% of the table instead of all of it.
Break it with a wildcard. Compare LIKE 'Sha%' with LIKE '%son'. The prefix is a contiguous slice of the sorted order; the suffix is not, and rows examined jumps back to the whole table with the index still sitting there unused.
Break it with a function. The LOWER(email) query does the same thing for the same reason.
Sort without sorting. The ORDER BY query reads 10 rows through the index and none of the sort work; without the index it reads the whole table and then sorts it.
Now pay for it. Push Indexes On This Table to 8. One INSERT becomes nine writes. This is why "just add an index" is a trade rather than a free win.
Key Takeaway
An index turns a linear scan into a logarithmic descent of a B-tree, which is why an indexed lookup barely notices a table growing a thousand-fold while a scan grows with it exactly. It works only while the query preserves the index's sort order, so a leading wildcard, a function or arithmetic on the column, or an implicit cast will quietly cost you the index and leave the query text looking innocent. A composite index reads left to right, and one that contains every column a query needs can answer it without touching the table. The price is paid on every write and in disk space, so index the columns you filter, join and sort on, and confirm with EXPLAIN rather than assumption.
Predict, then reveal
About to run: Grow the table. Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Recall check
0 of 3
Say the answer out loud before you reveal it — recalling it is what makes it stick, and rereading it is not.
Without scrolling back — what is the one-line takeaway from this module?
An index turns a linear scan into a logarithmic descent of a B-tree, which is why an indexed lookup barely notices a table growing a thousand-fold while a scan grows with it exactly. It works only while the query preserves the index's sort order, so a leading wildcard, a function or arithmetic on the column, or an implicit cast will quietly cost you the index and leave the query text looking innocent.
What does this module say about “Quick Context”?
Without an index, finding the rows that match a condition means reading every row and testing it — a full table scan, and its cost grows in a straight line with the size of the table. That is perfectly fine on ten thousand rows and ruinous on ten million.
What does this module say about “Why a B-tree”?
Almost every relational index is a B-tree: a balanced tree whose nodes are disk pages holding many keys each. Every leaf sits at the same depth, so every lookup costs the same. Because a page holds hundreds of keys, the tree is astonishingly shallow — with a fanout of a few hundred, three or four levels is enough for hundreds of millions of rows.
Cheat sheet
Indexes and Query Performance
An index is a sorted structure the database can walk instead of reading every row. Grow the table, change the query, and watch rows-examined either stay flat or climb with the table — then look at what the index costs you on every write.