Learn the theory
How Database Indexes Work (B-Tree): how it works
5 min read · Updated
Without an index a database answers a query the only way it can: by reading every row. An index is a separate, sorted structure — usually a B-tree — that lets it jump straight to the matching rows, the way a book's index saves you from reading every page. It is the single most effective performance tool in SQL, and understanding it explains why some queries fly while others crawl.
In short
- No index → sequential scan: cost grows linearly with table size.
- A B-tree index finds a row in about log(N) page reads — roughly 3–4 even for hundreds of millions of rows.
- Indexes are sorted, so they also serve ranges,
ORDER BYand prefix searches (LIKE 'Ma%'). - A composite index
(a, b)helps queries that filter ona, or onaandb— the leftmost prefix — but not onbalone. - Indexes aren't free: every write must update them, and the planner ignores them when a query matches a large share of the table.
Full table scan vs index lookup
A table is stored as unordered pages of rows. To find email = 'rhea@mail.com' with no index the database must read and test every row (a sequential scan). With an index on email it descends a tree that is sorted by email, reads a few small pages and follows a pointer to the single matching row.
EXPLAIN SELECT * FROM users WHERE email = 'rhea@mail.com';
-- Seq Scan on users (no index: reads every row)
-- Index Scan using idx_email (reads ~3 index pages + 1 row)How a B-tree works
A B-tree (strictly a B+tree in most databases) keeps keys sorted in fixed-size pages:
- The root and internal nodes hold separator keys that say “keys below X are in the left child, the rest in the right”.
- The leaf nodes hold the actual keys in order, each with a pointer to its table row.
- Leaves are linked to their neighbours, so a range scan finds the start once and then just walks sideways.
- The tree stays balanced: every leaf is the same distance from the root, so every lookup costs the same.
Because each page holds hundreds of keys, the tree is extremely wide and shallow: about 200 keys per page means 4 levels cover 1.6 billion rows. That is why index lookups barely slow down as tables grow.
Ranges, ORDER BY and LIKE
BETWEEN,<,>: descend to the lower bound, then follow leaf links until the upper bound.ORDER BY indexed_col: the data is already sorted, so no sort step is needed.LIKE 'Ma%': a prefix is a range ('Ma'to'Mb'), so the index works.LIKE '%an'orLIKE '%an%': the beginning is unknown, so the sorted order is useless and the database falls back to scanning.
Composite indexes and the leftmost-prefix rule
An index on (country, age) is sorted by country first, then by age within each country. It's like a phone book sorted by last name, then first name: great for “last name = Smith and first name > M”, useless for “first name = Anna”.
| Query filters on | Uses index (country, age)? |
|---|---|
country = 'IN' | Yes (leading column) |
country = 'IN' AND age > 40 | Yes (both columns) |
age > 40 only | No — it skips the leading column |
country > 'A' AND age = 30 | Partly: only the range on country narrows the scan |
Put equality columns first and the range column last, and order columns by how often queries filter on them.
Covering indexes (index-only scans)
Normally the index finds the row's location and the database then fetches the row from the table (a heap fetch), which is extra random I/O. If the index contains every column the query needs, the database can answer from the index alone: an index-only scan.
CREATE INDEX idx_country_age ON users (country, age);
SELECT country, age FROM users WHERE country = 'IN' AND age > 40;
-- Index Only Scan using idx_country_age (table never touched)When the planner ignores your index
- Low selectivity. If a filter matches a big fraction of rows (say 30%+), hopping between index and table for each one is slower than one sequential scan.
WHERE country = 'IN'on a column with four values often scans. - Tiny tables. Reading the whole table is cheaper than opening an index.
- Stale statistics. The planner estimates row counts from statistics; run
ANALYZEafter big changes. - Type mismatches and functions that make the column not directly comparable.
Frequently asked questions
- What is a database index?
- A separate sorted data structure (usually a B-tree) that maps column values to row locations, letting the database find rows without scanning the whole table.
- Why is a B-tree used for indexes?
- It's balanced, keeps keys sorted, and is shaped to match disk pages: each node holds many keys, so the tree is only a few levels deep and every lookup, range scan and ordered read needs very few page reads.
- What is the leftmost-prefix rule?
- A composite index on (a, b, c) can be used for conditions on a, on a and b, or on a, b and c — but not for conditions on b or c alone — because the index is sorted by a first.
- Why doesn't LIKE '%text' use an index?
- A B-tree is sorted by the beginning of the value. With a leading wildcard the database can't know where to start in the sorted order, so it must examine every row. Use full-text search or a trigram index instead.
- What is a covering index?
- An index that includes all columns a query needs, so the database can answer from the index alone (an index-only scan) without reading the table.
- Why would the database not use my index?
- Common reasons: the query matches a large part of the table, the table is tiny, the condition applies a function to the indexed column, the leading column of a composite index isn't filtered, or statistics are out of date.