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.
Overview
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.
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.
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 (last_name, first_name) is sorted by surname, and within each surname by first name — exactly like a phone book.
That means it helps with:
WHERE last_name = 'Smith' — seek straight there.
WHERE last_name = 'Smith' AND first_name = 'John' — ideal, both columns used.
ORDER BY last_name, first_name — already in that order, no sort needed.
And it does not help with WHERE first_name = 'John' alone. A phone book cannot find every John without reading all of it, and neither can the index. This is the leftmost prefix rule, and it is the single most useful thing to know about composite indexes.
Practical consequences:
Column order matters enormously. Put the column used in equality conditions first, and the one used for ranges or sorting after it.
One composite index on (a, b, c) also serves queries on (a) and (a, b), so three separate single-column indexes are often the wrong choice.
A covering index — one that includes every column the query needs — lets the engine answer entirely from the index without touching the table at all. INCLUDE in PostgreSQL and SQL Server adds columns for this purpose without making them part of the sort order.
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.
The index at the back of a book
Without an index, finding every mention of "photosynthesis" in a 900-page textbook means reading all 900 pages. With one, you look up the word in a short alphabetical list and jump to pages 214 and 655.
A database index is the same bargain, with the same costs. It takes extra space. It has to be kept up to date whenever the content changes. And it only helps for the things it was built on — an index of topics does nothing if you want to find every page with a diagram.
Concretely: on a table of 10 million orders, WHERE customer_id = 8412 without an index reads all 10 million rows. With a B-tree index on customer_id, the engine makes about three or four jumps down the tree and lands on the matching entries. The difference is not a percentage — it is seconds against milliseconds.
What an index cannot do for you
Indexes have a specific shape, and queries that do not fit it get no benefit:
Low selectivity. An index on a status column with two values, where 90% of rows are 'active', is useless for finding active rows. The planner will correctly ignore it, because reading most of the table via an index is slower than scanning it directly.
Functions on the column.WHERE LOWER(email) = 'a@b.com' cannot use an index on email. Index the expression instead.
Leading wildcards.LIKE '%son' has no prefix to seek to. Trailing wildcards are fine.
Type mismatches. Comparing an integer column to a quoted string can force a conversion that disables the index.
OR across different columns often prevents a single index from being used, though some engines can combine two index scans.
The rule underneath all of these: an index is an ordered structure, and it only helps when the query can be expressed as "seek to a position in that order, then read forward".
Watching the plan change
An index is a sorted copy of one or more columns, and the way to know whether it is being used is to ask the database rather than to reason about it. EXPLAIN QUERY PLAN gives a direct answer, and it changes as you create and drop indexes underneath it.
query.sqlSQLite
-- Before any index: the planner has no choice but to read every row.
EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE status = 'shipped';
-- Now give it one, and ask again.
CREATE INDEX idx_orders_status ON orders(status);
EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE status = 'shipped';
-- "SCAN orders" became "SEARCH orders USING INDEX". That is the whole
-- observable difference, and it is the only reliable way to tell -- on
-- six rows the timings are identical noise.
--
-- An index has to match the query. This one does not:
EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE discount > 0;
-- And an index on the wrong column order is nearly useless. A composite
-- index is sorted by its first column, then its second -- like a phone
-- book sorted by surname then forename, which cannot help you find
-- everyone called James.
CREATE INDEX idx_items_order_product ON order_items(order_id, product_id);
EXPLAIN QUERY PLAN
SELECT * FROM order_items WHERE order_id = 101;
EXPLAIN QUERY PLAN
SELECT * FROM order_items WHERE product_id = 3;
-- The first uses the index. The second cannot, because product_id is
-- the second column and there is no way to jump into the middle of a
-- sort you do not have the prefix for.
--
-- Indexes are not free: every INSERT, UPDATE and DELETE must maintain
-- them, and they occupy space. The cost is paid on every write to buy
-- speed on some reads, which is why "add an index" is a decision rather
-- than a default.
DROP INDEX idx_orders_status;
EXPLAIN QUERY PLAN
SELECT * FROM orders WHERE status = 'shipped';
Result
Try it yourself
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.
In one line
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.
What indexes cost
Nothing about an index is free, and the costs land on writes:
Storage. Typically 10–20% of the table size per index, sometimes far more for wide composite indexes.
Insert, update and delete speed. Every index must be updated whenever the indexed data changes. A table with eight indexes does nine writes for every logical write.
Planning time and instability. More indexes means more options for the planner to consider, and more chances for it to choose a bad one on a mis-estimated query.
Maintenance. Indexes fragment as data changes and occasionally need rebuilding.
This is why the answer to "should I add an index?" is never automatically yes. On a write-heavy table — an event log, a queue — a careful minimum is right. On a read-heavy reporting table, generous indexing usually pays.
Finding the indexes you do not need is easy and rarely done: every major database exposes usage statistics (pg_stat_user_indexes in PostgreSQL, sys.dm_db_index_usage_stats in SQL Server). An index with zero scans since the last restart is pure cost. Duplicate indexes — one on (a) and another on (a, b) — are a common find too, and the narrower one is usually redundant.
The types beyond B-tree
Type
Good at
Available in
B-tree
Equality, ranges, sorting — the default
Everywhere
Hash
Equality only, slightly faster
PostgreSQL, MySQL (memory tables)
GIN / inverted
Arrays, JSON keys, full-text search
PostgreSQL, Elasticsearch-style engines
GiST / R-tree
Geometric and geographic queries
PostgreSQL, MySQL spatial
Bitmap
Low-cardinality columns in analytics
Oracle, column stores
Partial / filtered
A subset of rows, e.g. WHERE active
PostgreSQL, SQL Server
Partial indexes are underused and often the neatest fix for the low-selectivity problem: index only the 2% of rows where status = 'pending', and the index stays tiny while serving exactly the query that needed it.
A note on primary keys: they are indexed automatically. Foreign keys usually are not — and an unindexed foreign key makes both joins and cascading deletes slow. That is one of the most common missing indexes in real schemas.
Questions people ask
How many indexes is too many? There is no fixed number, but past five or six on a write-heavy table the cost usually shows. Measure write throughput before and after.
Should every foreign key have an index? Nearly always yes, unless the child table is tiny or never joined.
Why is my index not being used? Common causes: the condition wraps the column in a function, the column type does not match, the table is small enough that scanning is cheaper, or the statistics are stale. EXPLAIN tells you; ANALYZE fixes the last one.
Do indexes help ORDER BY? Yes — an index already in the requested order lets the engine skip the sort entirely, which on large result sets is a bigger win than the filtering.
Does an index help COUNT(*)? Sometimes, if a small index can be scanned instead of the whole table. Exact counts on huge tables are expensive regardless; approximate counts from statistics are often good enough.
Should I index a boolean column? Rarely on its own. As part of a composite index, or as a partial index on the rare value, yes.
Recap in one screen
An index is an ordered copy of some columns that lets the engine seek instead of scan.
It helps equality, ranges, sorting and joins — not functions on the column, leading wildcards, or low-selectivity filters.
Composite indexes work left to right; column order is a design decision, not a detail.
Every index slows writes and costs storage, so audit for unused and duplicate ones.
Index your foreign keys, consider partial indexes for skewed data, and let EXPLAIN settle arguments.
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 4
Say the answer out loud before you reveal it — recalling it is what makes it stick, and rereading it is not.
What is meant by “Storage” here?
Typically 10–20% of the table size per index, sometimes far more for wide composite indexes.
What is meant by “Insert, update and delete speed” here?
Every index must be updated whenever the indexed data changes. A table with eight indexes does nine writes for every logical write.
What is meant by “Planning time and instability” here?
More indexes means more options for the planner to consider, and more chances for it to choose a bad one on a mis-estimated query.
What is meant by “Maintenance” here?
Indexes fragment as data changes and occasionally need rebuilding.
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.
The Ubiquitous B-TreeComer, ACM Computing Surveys 1979
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.