Database Indexing Explained

A database index is a separate, sorted data structure that maps the values of one or more columns to the rows that contain them, much like the index at the back of a book. Instead of scanning every row, the database walks the index to jump straight to the matching rows. Indexes can turn a query that takes seconds into one that takes milliseconds, but each one costs storage and slows down every insert, update and delete, so the skill is choosing the right ones.

How an index works

Without an index, a query like “find orders for customer 42” forces a full table scan: read every row and check it. With an index on customer_id, the database searches a sorted structure, finds the entries for 42 and follows pointers to just those rows.

The default index type in most relational databases is the B-tree: a shallow, balanced tree of sorted pages. Finding a value takes a handful of page reads even for billions of rows, and because entries are sorted, the same index serves range queries (created_at > …) and ordering (ORDER BY created_at). Our comparison of B-trees and LSM trees explains how the storage engine underneath shapes performance.

Index types

Composite indexes and column order

A composite index covers several columns, such as (customer_id, created_at). Entries are sorted by the first column, then by the second within each first value. That makes it ideal for:

CREATE INDEX idx_orders_customer_created
  ON orders (customer_id, created_at);

SELECT id, total
FROM orders
WHERE customer_id = 42
ORDER BY created_at DESC
LIMIT 20;

The index finds customer 42’s entries, already sorted by date, and reads just 20. It helps far less with WHERE created_at > … alone, because dates are only sorted within each customer. The rule of thumb is to put equality filters first and range or sort columns last, and to design composite indexes around your most frequent queries.

Covering indexes

If an index contains every column a query needs, the database can answer from the index alone, without visiting the table. PostgreSQL calls this an index-only scan and lets you add extra payload columns with INCLUDE; MySQL calls it a covering index. Covering indexes are powerful for hot read paths, but they are bigger, so use them selectively.

Clustered and secondary indexes

In MySQL’s InnoDB engine, the table itself is stored in primary-key order (the clustered index), and secondary indexes store the primary key as their pointer. Lookups through a secondary index therefore take two steps, and a large primary key makes every secondary index bigger. PostgreSQL stores table rows separately (a heap), and every index points into it.

Partial and expression indexes

• Partial indexes cover only rows matching a condition, such as WHERE status = 'pending', keeping them small and fast.
• Expression indexes index a computed value, such as lower(email), so case-insensitive lookups can use an index.

Why a query ignores your index

• A function wraps the column: WHERE lower(email) = … can’t use a plain index on email.
• A leading wildcard: LIKE '%son' can’t use a B-tree’s sorted order.
• Type mismatches force conversions that bypass the index.
• Low selectivity: if a filter matches a large share of the table, a sequential scan is genuinely cheaper, and the planner chooses it.
• Wrong column order in a composite index for this query.
• Stale statistics mislead the planner; run your database’s analyse command after big data changes.

Check with EXPLAIN

Never guess. Run EXPLAIN (or EXPLAIN ANALYZE, which executes the query) to see whether the planner uses an index scan, an index-only scan or a sequential scan, and how many rows it expected versus found. Compare plans before and after adding an index, on realistic data volumes.

The cost of indexes

• Slower writes: every insert, update and delete must update each affected index.
• Storage and memory: indexes compete with data for cache space.
• Maintenance: indexes bloat and fragment over time and occasionally need rebuilding.

Indexes at scale

When one machine can’t hold the data, indexes become per-shard; queries that don’t include the shard key must fan out to every shard, so choose the key with your main access paths in mind (see database sharding). For repeated identical reads, a cache in front of the database often beats yet another index; our caching strategies guide covers the patterns. The choice between relational and NoSQL stores also changes what indexing is available, as our SQL vs NoSQL guide explains.

Frequently asked questions

Should I index every column?

No. Unused indexes slow down writes and waste memory. Index the columns your important queries filter, join and sort on.

Does the primary key have an index?

Yes. Relational databases create a unique index for the primary key automatically, and usually for unique constraints too.

When is a full table scan better?

When a query needs a large fraction of the rows, or the table is small. Reading sequentially can be faster than thousands of random index lookups.