Skip to content
Velloreth
Technology 6 min read

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

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:

OperationSupported
=yes
<, >, BETWEENyes
ORDER BYyes, if the order matches
LIKE 'abc%'yes, a prefix
LIKE '%abc'no, a leading wildcard
IS NULLyes

Other index types:

TypeUse
Hashequality only
GINa full-text or array search
GiSTa geometric or range search
BRINa 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:

QueryUses 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:

TermMeaning
Seq Scana full table scan
Index Scanan index lookup, then the table
Index Only Scana covering index, no table read
Bitmap Heap Scanan index, then a batched table read
Nested Loopa join that reads the inner table per row
Hash Joina 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.

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.

Frequently asked questions

What is a database index?
It is a separate data structure, usually a B-tree, that maps the values of one or more columns to the rows that contain them. The database uses it to find the matching rows without reading the whole table. It trades space and write speed for read speed.
What is a composite index?
It is an index on more than one column, such as (last_name, first_name). The order matters: the index can be used for a query on the first column, or the first and second, but not the second alone. This is the leftmost prefix rule.
What is a covering index?
It is an index that contains every column a query needs, so the database answers the query from the index alone and does not read the table. It is faster because it avoids the extra lookup, and it is larger because it stores more columns.
Why is my index not used?
The common reasons are a function on the column, such as WHERE lower(email) = ..., a leading wildcard in a LIKE, a type mismatch between the column and the value, a low selectivity where a scan is cheaper, and a stale statistic. Read the query plan to see what the database actually did.
How many indexes should a table have?
As few as the queries need. Each index slows every insert, update and delete, and it uses space. A table with ten indexes is a table with slow writes. Review the indexes periodically and drop the ones no query uses.
What is the difference between a clustered and a non-clustered index?
A clustered index determines the physical order of the rows, so there is only one per table. A non-clustered index is a separate structure that points at the rows, and there can be many. In Postgres the table is a heap and the primary key index is separate; in MySQL InnoDB the primary key is clustered.