Skip to content
Velloreth
Programming 6 min read

Database Indexing Explained With Examples

An index trades write speed and space for read speed. Learn how a B-tree works, when an index is used, and the common mistakes.

By

What an index is

An index is a sorted structure that lets the database find rows without scanning the whole table.

Without an index, a query that filters on a column reads every row: a full table scan. With an index, the database looks up the value in the sorted structure and jumps to the matching rows.

The trade: an index speeds up a read and slows down a write, because every insert, update, and delete must also update the index. It also takes space.

The B-tree

The default index type in most databases is a B-tree: a balanced tree that keeps the keys sorted.

A lookup is logarithmic. A million rows is about 20 comparisons.

A range scan is efficient, because the keys are sorted, so WHERE created_at > '2026-01-01' walks the tree once and then reads sequentially.

An insert is logarithmic, and the tree rebalances as needed.

Other index types:

  • Hash — for an equality lookup only, not a range.
  • GIN — for a full-text search or an array containment.
  • GiST — for a geometric or a range type.
  • BRIN — for a very large table with a natural order, such as a time series.

Creating an index

CREATE INDEX idx_users_email ON users (email);
CREATE UNIQUE INDEX idx_users_email ON users (email);
CREATE INDEX idx_orders_user_created ON orders (user_id, created_at DESC);

A unique index enforces uniqueness as well as speeding up the lookup.

A partial index covers only the rows that match a condition, which is smaller and faster.

CREATE INDEX idx_orders_pending ON orders (created_at)
WHERE status = 'pending';

This is useful when a query only ever looks at a small subset, such as the pending orders.

Composite indexes

An index on several columns is usable for a query that filters on a prefix of the columns, in order.

CREATE INDEX idx_orders_user_created ON orders (user_id, created_at);
QueryUses the index?
WHERE user_id = 1Yes
WHERE user_id = 1 AND created_at > '2026-01-01'Yes
WHERE created_at > '2026-01-01'No

The order matters. The index is sorted by user_id first, then created_at, so a query that does not constrain user_id cannot use the sort.

The rule: put the equality columns first and the range column last. An index on (user_id, created_at) serves both an equality on user_id and a range on created_at.

Covering indexes

An index that contains every column a query needs lets the database answer from the index alone, without reading the table.

CREATE INDEX idx_orders_covering ON orders (user_id) INCLUDE (total, status);

The INCLUDE columns are stored in the index but not part of the sort key. The query reads the index and never touches the table, which is the fastest case.

Why an index is not used

A function on the column.

-- Does not use the index on email
WHERE LOWER(email) = 'a@b.com'

-- Fix: an index on the expression
CREATE INDEX idx_users_email_lower ON users (LOWER(email));

A type mismatch. Comparing a string column to a number forces a cast, which prevents the index from being used.

A leading wildcard.

-- Does not use the index
WHERE name LIKE '%smith'

-- Uses the index
WHERE name LIKE 'smith%'

Low selectivity. A column with few distinct values, such as a boolean, is a poor index candidate: the index does not narrow the result enough to be worth it.

A query that returns most of the table. If the query matches 80% of the rows, a full scan is faster than an index lookup plus a row fetch.

A stale statistic. The query planner uses statistics to choose a plan. If the statistics are stale, the plan may be wrong. Run ANALYZE after a large change.

Reading a query plan

Use EXPLAIN to see whether a query uses an index.

EXPLAIN ANALYZE
SELECT * FROM orders WHERE user_id = 1 AND created_at > '2026-01-01';

EXPLAIN shows the plan. EXPLAIN ANALYZE runs the query and shows the actual timings.

What to look for:

  • Seq Scan — a full table scan. A problem on a large table.
  • Index Scan — the index is used, and the table is read for the remaining columns.
  • Index Only Scan — the index covers the query. The fastest case.
  • Nested Loop — a join that reads one row at a time. Fine for a small set, slow for a large one.
  • Hash Join — a join that builds a hash table. Good for a large set.

The estimated rows versus the actual rows is the key comparison: a large difference means the statistics are stale, and the planner is choosing a plan based on a wrong assumption.

Indexes and writes

Every index must be updated on every write.

An insert adds an entry to every index on the table.

An update to an indexed column updates the index. An update to a non-indexed column does not.

A delete removes the entry.

The implication: a table with ten indexes has ten structures to maintain on every write. An unused index is a pure cost.

Find the unused indexes. Most databases expose index usage statistics.

SELECT indexrelname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0;

An index with zero scans since the last reset is a candidate for removal.

Practical guidance

  • Index the columns you filter and join on.
  • Use a composite index with the equality columns first.
  • Use a covering index for a hot query.
  • Avoid a function on an indexed column, or index the expression.
  • Avoid a leading wildcard.
  • Use EXPLAIN ANALYZE rather than guessing.
  • Run ANALYZE after a large change.
  • Remove an unused index.
  • Remember every index slows a write.

For the related guides, see sql-joins-explained and database-normalization-explained. For the broader context, caching-strategies-explained and sql-vs-nosql-databases.

Quotable summary

An index is a sorted structure that lets the database find rows without scanning the whole table, and it trades write speed and space for read speed, because every insert, update, and delete must also update the index. A composite index is usable for a query that filters on a prefix of its columns in order, so an index on (user_id, created_at) helps a query on user_id and on both, but not on created_at alone. A function on an indexed column prevents the index from being used unless the index is on the expression, and a leading wildcard in a LIKE has the same effect. Use EXPLAIN ANALYZE to see whether a query uses an index rather than guessing, and remove an index with zero scans, because an unused index is a pure cost.

Frequently asked questions

What is a B-tree index?
A balanced tree that keeps the keys sorted, so a lookup, an insert, and a range scan are all logarithmic. It is the default index type in most databases.
Why is my index not being used?
Common causes are a function on the column, a type mismatch, a leading wildcard in a LIKE, a low selectivity column, or a query that returns most of the table.
What is a composite index?
An index on several columns. It is usable for a query that filters on a prefix of the columns in order, so an index on (a, b) helps a query on a and on a and b, but not on b alone.
What is a covering index?
An index that contains every column a query needs, so the database can answer from the index alone without reading the table. It is the fastest case.
How many indexes should a table have?
As few as the queries need. Each index slows down every write and takes space, so an unused index is a cost with no benefit.
What is the difference between a clustered and a non-clustered index?
A clustered index determines the physical order of the rows, and there is one per table. A non-clustered index is a separate structure that points to the rows, and there can be many.