How Database Indexes Work — A Practical Guide

1. What an Index Actually Is: B+ Trees Without the Math

An index is a separate, sorted data structure that maps column values to row locations. Postgres, MySQL, and SQL Server all use the same family of structure for the default index type: a B+ tree. You do not need the algorithms to use it well, but you do need one mental picture.

Think of the index on the back of a textbook. It does not duplicate the book — it lists terms in alphabetical order and points to page numbers. To find "normalization" you do not read every page; you jump to the N section and read a few lines. A B+ tree works the same way, with three kinds of pages:

• Root page — one page, always in memory after the first read. It tells you which branch to follow.
• Interior pages — the branches. Each holds separator keys and pointers to finer-grained pages.
• Leaf pages — the sorted list of key/value entries. They are also linked to each other, left to right, which is what makes range scans cheap.

The important property is fanout: a single 16 KB page holds hundreds of keys. With roughly 500 keys per page, three levels address 500 × 500 × 500 = 125 million entries. That is why a lookup on a 50-million-row table is still 3–4 page reads — the top two levels are usually already cached, so a real seek often costs a single disk read. A full table scan on the same table reads all 50 million rows.

Sorted order buys you three things at once: equality lookups become a short descent, range conditions (>, BETWEEN, LIKE 'abc%') become "seek to the start, then walk the linked leaf pages", and ORDER BY on the indexed column can be satisfied for free because the data is already in that order.

A table to work with

The rest of this article uses this table. It is small enough to paste into a scratch schema, but pretend it holds five million rows — that assumption is what makes the plans interesting.

CREATE TABLE orders (
  id          BIGINT        NOT NULL,
  customer_id BIGINT        NOT NULL,
  status      VARCHAR(20)   NOT NULL,
  created_at  DATETIME      NOT NULL,
  total       DECIMAL(10,2) NOT NULL,
  PRIMARY KEY (id)
);

INSERT INTO orders (id, customer_id, status, created_at, total) VALUES
  (1, 42, 'pending', '2026-01-05 09:12:00', 129.90),
  (2, 42, 'shipped', '2026-01-06 11:40:00',  59.00),
  (3, 77, 'pending', '2026-02-01 08:03:00', 310.50),
  (4, 42, 'pending', '2026-02-14 17:25:00',  18.75);

-- No index on customer_id yet: this scans every row.
SELECT id, status, total FROM orders WHERE customer_id = 42;

-- Now it descends the tree instead.
CREATE INDEX idx_orders_customer ON orders (customer_id);
SELECT id, status, total FROM orders WHERE customer_id = 42;

Both queries return the same rows. The first reads the whole table; the second reads a handful of index pages and then fetches the matching rows. On a large table that is the difference between tens of milliseconds and tens of seconds.

2. Clustered vs Secondary Indexes

Not all indexes are equal, and the distinction that matters most is whether the index is the table or merely points at it.

A clustered index stores the full row inside its leaf pages. InnoDB (the default MySQL engine) builds the clustered index on the PRIMARY KEY, which means the table data is physically ordered by primary key. There can only be one, because rows can only be sorted one way. In the table above, PRIMARY KEY (id) is the clustered index — a lookup by id walks one tree and is done.

A secondary index stores only the indexed columns plus a pointer back to the row. In InnoDB that pointer is the primary key value. So this query does two traversals, not one:

CREATE INDEX idx_orders_status ON orders (status);

-- Step 1: seek 'pending' in idx_orders_status -> get primary key ids
-- Step 2: for each id, seek the clustered index to fetch the rest of the row
SELECT status, total FROM orders WHERE status = 'pending';

That second traversal is called a bookmark or row lookup, and it is why a query returning 100,000 matching rows can be slower with an index than without one: the optimizer may decide the random-access lookups cost more than a sequential scan and abandon your index on purpose. This is a real decision, not a bug.

One practical consequence: because every secondary index in InnoDB carries the primary key, a wide or random primary key (say, a 36-character UUID) inflates every index on the table and turns sequential inserts into page splits scattered across the tree. An BIGINT AUTO_INCREMENT primary key keeps inserts at the right edge of the clustered index, appending instead of splitting.

3. Composite Indexes and the Leftmost Prefix Rule

A composite (multi-column) index sorts entries by the first column, then by the second within equal first values, and so on — exactly like a phone book sorted by last name, then first name. Everything about how it can be used follows from that one fact.

The leftmost prefix rule: an index on (a, b, c) can be used for queries filtering on a, on a, b, or on a, b, c. It cannot be used for queries filtering only on b, only on c, or on b, c — you cannot find "all the Johns" in a phone book sorted by last name.

CREATE INDEX idx_orders_cust_status_created
  ON orders (customer_id, status, created_at);

Here is the same index tested against six realistic queries:

There is a subtler case that bites people in production:

-- Index (customer_id, status, created_at)
-- Uses customer_id for the seek, then evaluates created_at as a filter
-- on every row of that customer. The created_at ordering is NOT usable
-- for the range, because status was skipped.
SELECT id, total
FROM orders
WHERE customer_id = 42
  AND created_at >= '2026-01-01';

-- Uses all three columns for the seek AND returns rows already in
-- created_at order, so no sort step is needed.
SELECT id, total
FROM orders
WHERE customer_id = 42
  AND status = 'pending'
  AND created_at >= '2026-01-01'
ORDER BY created_at;

That is why the ordering rule for composite index columns is: equality columns first, then the range or sort column last. Once a column is used with a range operator, the index can no longer be used to constrain anything to its right — the walk has become a scan segment. Put the range column first and every equality column after it becomes a filter instead of a seek.

Among equality columns, order matters less for the "all of them present" query, but it matters a lot for the partial queries. If your application constantly filters WHERE customer_id = ? alone, customer_id must be first. If two single-column queries are equally common, you may need two indexes — a composite index cannot serve both leading columns.

4. Covering Indexes: Answering a Query from the Index Alone

If a secondary index already contains every column a query reads, the database never has to visit the table. The index pages alone answer it. This is called a covering index (or an index-only scan), and it is often the single biggest win available for read-heavy workloads.

-- Index on (customer_id, status) only
CREATE INDEX idx_orders_cust_status ON orders (customer_id, status);

-- total is NOT in the index, so each match needs a row lookup
SELECT status, total
FROM orders
WHERE customer_id = 42 AND status = 'pending';

-- Add total to the index: now it covers the query
CREATE INDEX idx_orders_cust_status_total
  ON orders (customer_id, status, total);

SELECT status, total
FROM orders
WHERE customer_id = 42 AND status = 'pending';   -- index-only scan

PostgreSQL spells the intent out with an INCLUDE clause, which appends payload columns without making them part of the sort key:

-- PostgreSQL: keep the key narrow, carry total along for the ride
CREATE INDEX idx_orders_cust_status
  ON orders (customer_id, status)
  INCLUDE (total);

The tradeoff is honest: a covering index is wider, so it takes more space and costs more on every write. Add total to an index only when a frequent query needs exactly that shape — and prefer copying a narrow column over dragging a TEXT or JSON column into the index.

5. When SQL Index Optimization Fails: Four Ways the Optimizer Ignores You

You created the index. The query did not get faster. In the overwhelming majority of cases one of these four patterns is responsible — and in every one of them the fix is to make the indexed column appear alone on the left side of the comparison.

5.1 A function wraps the indexed column

-- BAD: created_at is buried inside YEAR(), so the index on it is unusable
SELECT id, total FROM orders WHERE YEAR(created_at) = 2026;

-- GOOD: rewrite as a range on the bare column -> index range scan
SELECT id, total
FROM orders
WHERE created_at >= '2026-01-01'
  AND created_at <  '2027-01-01';

If the business genuinely needs the expression, index the expression instead of the column. PostgreSQL supports this directly; MySQL 8 supports functional indexes:

-- PostgreSQL expression index
CREATE INDEX idx_orders_year ON orders ((EXTRACT(YEAR FROM created_at)));

-- MySQL 8 functional index
CREATE INDEX idx_orders_year ON orders ((YEAR(created_at)));

5.2 Implicit type conversion

This is the nastiest one, because the query looks completely correct. A VARCHAR column compared against an unquoted number forces the database to convert the column side, not the literal side — and a converted column cannot be looked up in an index.

CREATE TABLE customers (
  id    BIGINT      NOT NULL,
  phone VARCHAR(20) NOT NULL,
  PRIMARY KEY (id),
  INDEX idx_phone (phone)
);

-- BAD: no quotes -> MySQL converts every phone value to a number.
-- Full scan. Every row re-typed before comparison.
SELECT id FROM customers WHERE phone = 13800138000;

-- GOOD: compare string to string -> index seek
SELECT id FROM customers WHERE phone = '13800138000';

Watch for the same trap on DATETIME versus DATE, and on BIGINT columns compared to string literals in languages that silently pass IDs as strings. If you apply a collation in the query that differs from the column's, the index is bypassed too.

5.3 LIKE with a leading wildcard

-- BAD: leading % can match anywhere -> full scan, nothing to seek to
SELECT id FROM orders WHERE status LIKE '%pend%';

-- GOOD: anchored prefix -> the tree can seek to 'pend' and walk forward
SELECT id FROM orders WHERE status LIKE 'pend%';

For genuine substring search, a B+ tree is the wrong tool. Use a full-text index (MySQL FULLTEXT, PostgreSQL tsvector) or PostgreSQL's pg_trgm GIN index, which is built for fuzzy and infix matching.

5.4 OR across different columns

-- BAD: two different columns joined by OR. The optimizer usually
-- cannot use either index and falls back to one full table scan.
SELECT id, total FROM orders
WHERE customer_id = 42 OR status = 'pending';

-- GOOD: split into two index-friendly lookups
SELECT id, total FROM orders WHERE customer_id = 42
UNION
SELECT id, total FROM orders WHERE status = 'pending';

-- Use UNION ALL instead of UNION if duplicates are acceptable:
-- it skips the deduplication sort.

OR on the same column is a different story — that is equivalent to IN and the optimizer handles it as a range. It is only the cross-column OR that breaks index usage, and MySQL's index merge access path may still save it if both columns are indexed separately.

Prove it with EXPLAIN

Never assume — look. Prefix the statement with EXPLAIN and read the access type, the chosen key, the estimated rows, and the extra notes.

-- MySQL 8
EXPLAIN
SELECT id, total FROM orders
WHERE customer_id = 42 AND status = 'pending'\G

-- PostgreSQL, with real timing and buffer counts
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, total FROM orders
WHERE customer_id = 42 AND status = 'pending';

What to look for in the MySQL output:

• type — ALL is a full table scan. ref, range, eq_ref, and const mean an index was used. Anything starting with index_merge is using two indexes together.
• key — which index was chosen. NULL means none.
• rows — the optimizer's estimate of rows examined. A number near your table's total row count plus type = ALL is the signature of a missing index.
• Extra — Using index is a covering index, Using where means rows are being filtered after retrieval, and Using filesort or Using temporary on a large result set is a sorting cost you may be able to index away.

In PostgreSQL the labels differ but the story is the same: Seq Scan is the full scan, Index Scan and Index Only Scan are the good ones, Index Cond shows what the index was able to enforce, and Filter shows conditions applied afterward to discard rows. A long gap between rows removed by filter and the rows returned says your index stops short.

6. The Write-Side Cost: Duplicate, Redundant, and Unused Indexes

Indexes are not free. Every index is a second sorted structure that must stay consistent with the table, so each INSERT, UPDATE, and DELETE pays for all of them. Inserting 10,000 rows into a table with eight indexes is 10,000 row writes plus roughly 80,000 index updates, plus every B+ tree page split that follows. On write-heavy tables — logs, events, telemetry, message queues — a surplus index is a direct tax on throughput.

Two failure modes are common, and both are easy to find.

Duplicate indexes have the same column list under different names, usually created by two different developers or two migrations that never met:

CREATE INDEX idx_orders_customer ON orders (customer_id);
CREATE INDEX idx_orders_customer_v2 ON orders (customer_id);   -- duplicate
CREATE INDEX idx_cust ON orders (customer_id);                 -- duplicate again

Redundant indexes are prefixes of longer ones. Given (customer_id, status), a separate index on (customer_id) can never be used to do anything the longer index cannot — it just costs writes and disk forever:

-- index B makes index A redundant, because A is a leftmost prefix of B
CREATE INDEX idx_a ON orders (customer_id);            -- redundant
CREATE INDEX idx_b ON orders (customer_id, status);    -- supersedes it

Find them with catalog queries instead of reading your migrations:

-- List every index on a table with its columns in order
SELECT index_name, column_name, seq_in_index
FROM information_schema.statistics
WHERE table_name = 'orders'
ORDER BY index_name, seq_in_index;

-- PostgreSQL: indexes that have never been used since the last stats reset
SELECT relname, indexrelname, idx_scan
FROM pg_stat_user_indexes
WHERE schemaname = 'public'
ORDER BY idx_scan ASC, pg_relation_size(indexrelid) DESC;

-- MySQL 8: ready-made redundancy and usage views
SELECT * FROM sys.schema_redundant_indexes
WHERE table_schema = 'shop';

SELECT * FROM sys.schema_unused_indexes;

Treat the unused-index list as evidence, not as an order. Two caveats before you drop anything: statistics reset when the server restarts, so an idx_scan = 0 may just mean "no traffic since Tuesday"; and an index that only serves a quarterly report is still doing its job. Watch for one full business cycle — a month, or at minimum a release cycle — before removing an index that looks idle.

The rule of thumb for write-heavy tables: prefer one composite index over three single-column indexes, keep the list as short as the query workload genuinely demands, and batch writes so index maintenance is amortized. A narrow, well-ordered index beats three convenient ones every time.

FAQ — Database Indexes