Database Indexes Explained: B-Tree, Composite and Covering
An index trades write speed and space for read speed. Learn the B-tree, the composite index, the covering index and the query plan.
By Velloreth
What an index is
An index is a sorted structure that maps a column value to the rows that contain it.
Without an index, a query with a WHERE clause reads every row, which is a full table scan.
With an index, the database seeks to the value and reads only the matching rows.
The trade-off: the index uses space and it must be updated on every write.
The B-tree
The default index type in most databases is a B-tree, which is a balanced tree.
The properties:
- The values are sorted, so a range query is efficient
- The tree is balanced, so a lookup is a fixed number of steps
- A lookup is O(log n)
What a B-tree supports:
| Operation | Supported |
|---|---|
= | yes |
<, >, BETWEEN | yes |
ORDER BY | yes, if the order matches |
LIKE 'abc%' | yes, a prefix |
LIKE '%abc' | no, a leading wildcard |
IS NULL | yes |
Other index types:
| Type | Use |
|---|---|
| Hash | equality only |
| GIN | a full-text or array search |
| GiST | a geometric or range search |
| BRIN | a large, naturally ordered table |
The composite index
An index on more than one column.
CREATE INDEX idx_users_name ON users (last_name, first_name);
The order matters. The index is sorted by last_name, then by first_name within each last_name.
The leftmost prefix rule:
| Query | Uses the index |
|---|---|
WHERE last_name = 'Smith' | yes |
WHERE last_name = 'Smith' AND first_name = 'A' | yes |
WHERE first_name = 'A' | no |
The rule: the index can be used for a prefix of the columns, from the left.
The design consequence: put the column that is used alone first, and the one that is only used with it second.
A range breaks the prefix. WHERE a = 1 AND b > 2 AND c = 3 uses the index for a and b, and c is filtered after.
The covering index
An index that contains every column a query needs.
-- The query
SELECT email, created_at FROM users WHERE last_name = 'Smith';
-- The covering index
CREATE INDEX idx_users_cover ON users (last_name, email, created_at);
The database answers from the index alone, so it does not read the table.
Why it is faster: it avoids the extra lookup, which is a random read per row.
Why it is larger: it stores more columns.
A covering index is the strongest optimisation for a hot read query, and it is the one to reach for when a query is already using an index and is still slow.
Selectivity
Selectivity is how many distinct values a column has.
A high selectivity — a unique id — is a good index candidate, because a lookup returns one row.
A low selectivity — a boolean, a status with three values — is a poor candidate, because a lookup returns a large fraction of the table and a scan is cheaper.
The rule of thumb: an index is useful when a query returns a small fraction of the rows, roughly under 5 to 10 percent.
A partial index indexes only the rows that matter.
CREATE INDEX idx_orders_pending ON orders (created_at)
WHERE status = 'pending';
A partial index is smaller and faster, and it is ideal for a query that always filters on the same condition.
Reading the query plan
The plan is the truth. A guess about which index is used is often wrong.
EXPLAIN ANALYZE
SELECT * FROM users WHERE last_name = 'Smith';
What to look for:
| Term | Meaning |
|---|---|
Seq Scan | a full table scan |
Index Scan | an index lookup, then the table |
Index Only Scan | a covering index, no table read |
Bitmap Heap Scan | an index, then a batched table read |
Nested Loop | a join that reads the inner table per row |
Hash Join | a join that builds a hash table |
EXPLAIN ANALYZE runs the query and reports the actual time and rows, which is more useful than the estimate.
A large difference between the estimated and the actual rows is a sign of a stale statistic.
Why an index is not used
A function on the column.
-- The index on email is not used
WHERE lower(email) = 'a@b.com'
-- The fix: an expression index
CREATE INDEX idx_users_email_lower ON users (lower(email));
A leading wildcard.
WHERE name LIKE '%smith' -- not used
WHERE name LIKE 'smith%' -- used
A type mismatch. A string compared to an integer column, or a varchar compared to a text with a different collation.
A low selectivity. The planner decides a scan is cheaper.
A stale statistic. Run ANALYZE to refresh.
An OR across different columns. It may not use either index.
A cast. WHERE id = '123' on an integer column may prevent the index use in some databases.
The cost
Every index slows a write. An insert updates every index on the table.
Every index uses space. A large table with many indexes can be larger than the data.
A redundant index is a cost with no benefit. An index on (a) is redundant if (a, b) exists, because the leftmost prefix covers it.
A review: list the indexes, and for each one find the query that uses it. An index with no query is a candidate for removal.
Common mistakes
An index on every column. Slow writes and wasted space.
A composite index in the wrong order. The leftmost prefix rule is not satisfied.
A function on the indexed column. The index is not used.
A leading wildcard. The index is not used.
A low-selectivity index. A scan is cheaper.
No EXPLAIN. The index is assumed to be used.
A redundant index. A cost with no benefit.
An index added without a measurement. The query may not be the bottleneck.
A missing index on a foreign key. A join and a cascade delete are slow.
A quotable summary
An index is a sorted structure that lets the database find rows without scanning the table, and it trades space and write speed for read speed. A composite index follows the leftmost prefix rule, so the column order matters, and a covering index contains every column a query needs so the table is not read. Read the query plan with EXPLAIN ANALYZE, because a function on the column, a leading wildcard or a low selectivity prevents the index from being used.
Related reading
For the related topics, see database-sharding-basics and cap-theorem-explained. For the broader context, json-vs-yaml-vs-toml and api-error-responses-guide.