Database Indexes Explained: How They Work and When to Use Them

A missing index turns a millisecond query into a ten-second table scan. An over-indexed table makes every insert crawl. Understanding how indexes work — not just that they exist — is what separates developers who guess from developers who measure.

Most SQL developers learn to add an index when a query is slow, and remove it when an interviewer asks about write overhead. Fewer understand why a particular index helps or why the query planner sometimes ignores an existing one. The mental model that makes those questions answerable is the B-tree.

The B-tree: what a database index actually stores

The dominant index structure in relational databases (PostgreSQL, MySQL, SQLite, Oracle, SQL Server) is the B-tree, specifically a variant called the B+ tree. A B+ tree is a balanced tree where all data lives in the leaf nodes, and internal nodes contain only keys used for navigation. The leaves are linked in sorted order, forming a sorted linked list of indexed values.

When you create an index on users.email, the database builds a B+ tree where each leaf entry contains an email address and a pointer (row ID, or in MySQL's InnoDB, the primary key) back to the heap row. The tree is kept balanced so that looking up any value requires the same number of page reads: O(log n), typically three to five disk reads for a table with millions of rows.

For a sequential scan of the full table, the database reads every page anyway — the index adds overhead without benefit. Indexes pay off for selective queries that retrieve a small fraction of rows. The query planner estimates selectivity using column statistics; if the estimate says an index lookup will visit 40% of the table, a sequential scan is usually cheaper because it avoids the random I/O pattern of following row pointers.

How the query planner chooses an index

The query planner (called the optimizer in many databases) generates multiple candidate query plans for every statement, estimates the cost of each in terms of page reads and CPU operations, and executes the cheapest one. For a simple lookup:

EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id = 42;

EXPLAIN ANALYZE in PostgreSQL shows the actual plan chosen, estimated versus actual row counts, and time spent. Common plan nodes include:

• Seq Scan: reads every row in the table. Fast for large fractions of the table; slow for needle-in-haystack lookups.
• Index Scan: traverses the B-tree to find matching rows, then fetches each row from the heap via its pointer. Good for selective predicates; generates random I/O if many rows match.
• Index Only Scan: retrieves all needed columns directly from the index without touching the heap. Only possible if the index contains every column the query references.
• Bitmap Index Scan + Bitmap Heap Scan: collects all matching row IDs into a bitmap, sorts them by physical location, then reads the heap pages in order. Reduces random I/O for moderately selective queries.

If the planner consistently chooses a sequential scan despite an index existing, check the cardinality statistics with ANALYZE (PostgreSQL) or check whether the indexed column appears inside a function call that prevents index use:

-- Index on created_at is NOT used here:
SELECT * FROM events WHERE DATE(created_at) = '2026-01-15';

-- Rewrite to enable index use:
SELECT * FROM events
WHERE created_at >= '2026-01-15'
  AND created_at  < '2026-01-16';

Wrapping a column in a function makes the expression non-sargable: the database cannot map the function output back to a position in the B-tree. Rewriting the predicate as a range query allows the planner to navigate directly to the start of the range and scan forward.

Composite indexes and column order

A composite index covers multiple columns: CREATE INDEX idx_orders_cust_date ON orders (customer_id, created_at). The B-tree sorts rows first by customer_id, then by created_at within each customer_id group. This index supports:

• Queries filtering on customer_id alone (uses the leading prefix).
• Queries filtering on customer_id and created_at together (full composite use).
• Queries filtering on customer_id and sorting by created_at (avoids a sort step).

It does not efficiently support queries that filter on created_at alone, because the index is not sorted by created_at globally — only within each customer_id partition. This is the left-prefix rule: a composite index can be used starting from the leftmost column, and can skip columns on the right, but cannot skip the leading column.

A common interview question asks which index better supports the query WHERE status = 'active' AND created_at > '2026-01-01': (status, created_at) or (created_at, status)? If status has low cardinality (say, three distinct values) and created_at is highly selective, the planner benefits more from (created_at, status) because the leading column prunes most of the B-tree. Put the most selective column first — unless an equality filter on a lower-cardinality column lets you eliminate a sort.

Covering indexes and index-only scans

If an index contains every column referenced by a query (in both the WHERE clause and the SELECT list), the database can satisfy the query entirely from the index without touching the heap. This is an index-only scan and is dramatically faster because heap pages can be scattered across disk while index pages are compact and often cached.

-- Table: events(id, user_id, event_type, created_at, payload)
-- Query:
SELECT user_id, event_type, created_at
FROM events
WHERE user_id = 7 AND created_at > NOW() - INTERVAL '7 days';

-- Covering index (includes all selected columns):
CREATE INDEX idx_events_user_time_cover
ON events (user_id, created_at)
INCLUDE (event_type);   -- PostgreSQL 11+ syntax

The INCLUDE clause adds event_type to the leaf pages without making it part of the sort key. The query now touches zero heap pages. For a reporting query that runs frequently on a large table, a well-designed covering index can reduce execution time by an order of magnitude.

The write overhead cost and how to manage it

Every index that exists on a table must be updated on every insert, update (if the indexed column changes), and delete. For a table with five indexes, an insert touches six data structures: the heap row plus five index trees. Index maintenance is not free, and tables with many writes can spend a substantial fraction of I/O budget maintaining indexes that are rarely queried.

The practical discipline: add indexes to support specific known queries, not speculatively. Use pg_stat_user_indexes in PostgreSQL (or equivalent views in MySQL) to identify indexes that have never been used and drop them. Partial indexes can dramatically reduce maintenance cost for large tables where most queries target a subset of rows:

-- Only indexes rows where status = 'pending' -- much smaller tree
CREATE INDEX idx_jobs_pending
ON jobs (created_at)
WHERE status = 'pending';

If a table is write-heavy and the indexed column is not selective enough to be useful for most queries, the index is pure overhead. Delete it. Indexes are a performance optimization, not a correctness requirement (except for unique constraints and primary keys, which enforce data integrity).

The workflow for index tuning: run EXPLAIN ANALYZE on slow queries, look for sequential scans on large tables, add a targeted index, run again to confirm the plan changed and the actual time dropped. Measure before and after, on realistic data volumes — the query planner behaves differently on a test database with a thousand rows than on production with fifty million.