"Add an index" is the most common performance advice in software, and it is usually given without saying what the index is. It is a data structure. Knowing which one tells you exactly when it will help and when it will be ignored.
It is a B-tree, and that is because of disks
Almost every general-purpose index is a B-tree (in practice a B+ tree). Binary trees are the textbook answer for sorted lookup, but they are wrong for storage: a binary tree of a million rows is about twenty levels deep, and if each level is a separate disk page that is twenty I/O operations.
A B-tree fixes this by making each node hold many keys — hundreds — so the tree is wide and shallow. A million rows fits in three or four levels. Even on an SSD, where seeks are cheap, the page is still the unit of I/O and reading fewer pages is still faster.
Leaf nodes hold the indexed values in sorted order along with pointers to the actual rows, and are linked to their neighbours, which is what makes range scans (WHERE created_at > ...) efficient: find the start, then walk sideways.
Sorted order explains everything an index can do
Because the index is sorted, it serves:
- equality lookups (
= value) - range queries (
>,<,BETWEEN) - prefix matches (
LIKE 'abc%') ORDER BYon the indexed column, for freeMIN/MAX, which are just the first and last leaf entries
And it explains what an index cannot do. LIKE '%abc' cannot use one, because a sorted structure gives you no way to find entries by their ending. Neither can WHERE UPPER(name) = 'X', because the index stores name, not UPPER(name) — wrap a column in a function and you have thrown the index away. (Both have workarounds: trigram indexes for the first, expression indexes for the second.)
Composite indexes and the leftmost rule
An index on (a, b, c) sorts by a, then by b within equal a, then c. Like a phone book sorted by surname then first name.
This is why it serves queries filtering on a, on a and b, or on all three — but not a query filtering only on b. Asking for everyone called "James" in a book sorted by surname means reading the whole book. Column order in a composite index is a design decision, not a formality, and getting it wrong produces an index the planner correctly refuses to use.
The usual heuristic: equality columns first, range column last. A query with WHERE tenant_id = ? AND created_at > ? wants (tenant_id, created_at). Reverse them and you scan far more of the tree.
Covering indexes
If an index contains every column a query needs, the database can answer from the index alone and never touch the table. Postgres calls this an index-only scan; SQL Server calls it covering. It can be a large win — often several times faster — because it halves the I/O.
The trade is size: a wider index is a bigger index, and bigger indexes fall out of memory sooner.
Indexes are not free
Every index must be updated on every insert, update and delete of its columns. A table with eight indexes does roughly nine writes per insert. Indexes also consume memory that the database would otherwise spend caching data.
So the real rule is not "add indexes" but add the smallest set of indexes that serves your actual query patterns, and remove the ones nothing uses. Most databases will tell you which indexes are never touched; that list is almost always longer than people expect.
How to check rather than guess
EXPLAIN (with ANALYZE, on a real dataset) tells you what the planner actually does. Look for a sequential scan where you expected an index scan, and for a large gap between estimated and actual row counts — that gap usually means stale statistics, and stale statistics make good planners choose badly.
Test on production-shaped data. On a thousand rows the planner will often choose a sequential scan because it genuinely is faster, and you will learn nothing about how the query behaves at ten million.