Indexes

A customer opens their order history and waits long enough to wonder whether the page is broken. Behind it is one query, SELECT * FROM orders WHERE customer_id = 4217, which returns the nine orders that customer has placed. To find them, the database read all two million rows in the table, checked each one’s customer_id, and threw 1,999,991 away. It will do the same for the next customer.

Nothing is wrong with the query or the server. The database has no way to know where customer 4217’s rows are, so the only correct plan is to look at all of them. An index gives it a way: a separate structure, sorted by the column you search on and kept up to date on every write, that leads straight to the matching rows. It is the index at the back of a printed book: terms in order, each with its pages, so nobody reads the book to find one word.

The full scan

Without an index, filtering on customer_id is a full table scan: read every page of the table, test every row, keep the matches. A page is the fixed-size block a database reads and writes (8 KB by default in PostgreSQL, 16 KB in MySQL’s InnoDB). At 100 orders to a page, two million orders is 20,000 pages, and the scan reads all of them to return nine rows.

That is O(n) where n is the size of the table, not the size of the answer. A customer with nine orders costs as much to find as one with nine thousand, and both get slower as the table grows. Nor can the scan stop at nine: nothing tells it there is not a tenth on the last page.

Sorted, shallow and wide

Almost every index you will create is a B-tree. Its leaves hold the indexed values in sorted order, each with a way to reach its row, and each leaf page is linked to the next. Above them sit branch pages whose entries are boundaries (keys below this one are in that child), and above those, one root page. A lookup starts at the root, picks the child whose range holds the value, reads it, and repeats until it reaches a leaf: one page per level.

There are few levels because each page is wide. Say 500 entries to a page. Then 1,000,000 keys fill 2,000 leaves, those need 4 branch pages, and those fit under one root: three page reads per lookup. Three levels at that width hold up to 125 million keys (500 × 500 × 500), and a fourth holds 62.5 billion. A binary tree needs 20 levels for the same million keys, since 2¹⁹ is 524,288 and 2²⁰ is 1,048,576. Fetching a page is the expensive step, and comparing against a few hundred keys once it is in memory is cheap, so the tree spends comparisons to save fetches. The root and branches, read by every lookup, tend to stay cached.

The scene draws a small table the way InnoDB stores every table: a B-tree on the primary key with the rows themselves in the leaves, twenty orders to a page. PostgreSQL keeps rows in a separate heap, so its lookups read one more page to fetch the row. Each page is labelled with the ids beneath it and has two children, so the tree fits on a phone. Three queries use the tree; the fourth searches customer_id, which has no index.

Four pages against three looks like a close race, and at eighty rows it is. The badges show which number grows: a lookup pays one page per level, a scan one per page of table. At the opening’s two million orders, 100 to a leaf and 500 entries to a branch page, the tree is 20,000 leaves under 40 branch pages under one root. A lookup by id still reads three pages; the scan reads 20,000.

The range did something a hash table cannot. It descended once, to where 35 would sit, then read sideways along the leaves, because neighbouring keys sit on neighbouring pages. A hash table finds one exact key in O(1) by scattering keys on purpose, so it has no idea where 36 is relative to 35, and that rules out ranges such as BETWEEN and rows returned already sorted for an ORDER BY. It is why PostgreSQL’s CREATE INDEX builds a B-tree unless told otherwise, and why its hash indexes serve equality alone.

Composite indexes and the leftmost prefix

An index can cover several columns, and it sorts by them in the order you list them. An index on (customer_id, created_at) is sorted by customer and, inside each customer, by date: (4216, 2026-03-02), then customer 4217’s nine orders from (4217, 2025-11-30) to (4217, 2026-05-01), then (4218, 2025-08-09).

So customer 4217’s entries form one run, in date order. WHERE customer_id = 4217 descends to the start of the run and reads it; adding AND created_at >= '2026-01-01' descends to the first matching date inside it; ORDER BY created_at DESC LIMIT 20 reads the run backwards and stops after twenty, with no sort. But the index cannot take WHERE created_at >= '2026-01-01' straight to its rows, because this year’s orders are spread through every customer’s run, the way customer 9’s orders were spread across the scene’s pages. An index serves a query that pins down a leftmost prefix of its columns, not one that skips the first.

So put the columns a query tests for equality first, and the one it ranges or sorts over last. Some planners can skip-scan an index whose first column has few distinct values; treat that as a bonus to notice in a plan, not a design.

What an index costs

An index is not free to keep. Every INSERT adds an entry to every index on the table, every DELETE removes one, and an UPDATE to an indexed column moves its entry. A table with five indexes makes six writes per inserted row, and each index takes disk space and a share of the memory the table’s pages compete for. Index the columns your queries filter, join and sort by; an index no query uses is write cost and nothing else.

Having an index does not mean the planner will use it, and two reasons cover most surprises. One is selectivity. If WHERE status = 'delivered' matches 90% of the table, going through the index means fetching nearly every row from its own page, which is more work than reading the table straight through, and the planner, which keeps statistics on each column, picks the scan. An index pays off when a query keeps a small fraction of the rows. The other is a function on the column. An index on email is sorted by email, so WHERE lower(email) = 'kim@example.com' gives the planner nothing to descend by; most engines let you index the expression lower(email) instead. Either way, EXPLAIN shows the plan the database chose, which beats guessing.

Here is the opening’s fix, with queries the new index can and cannot take straight to their rows:

-- The order-history page: one customer's orders, newest first.
SELECT id, total, created_at
FROM orders
WHERE customer_id = 4217
ORDER BY created_at DESC
LIMIT 20;

-- The equality column first, then the column the page sorts by.
CREATE INDEX orders_customer_created
  ON orders (customer_id, created_at);

-- Leftmost prefixes: the index takes both straight to their rows.
SELECT id FROM orders WHERE customer_id = 4217;
SELECT id FROM orders
WHERE customer_id = 4217 AND created_at >= '2026-01-01';

-- Not a prefix: dates are in order only inside each customer's run.
SELECT id FROM orders WHERE created_at >= '2026-01-01';

-- An index on email is sorted by email, not by lower(email)...
CREATE INDEX customers_email ON customers (email);
SELECT id FROM customers WHERE lower(email) = 'kim@example.com';
-- ...so index the expression the query actually compares.
CREATE INDEX customers_email_lower ON customers (lower(email));

One index serves the page and both prefix queries, and the column order is what does it. Reversed, as (created_at, customer_id), it would serve the date-only query instead and make every question about one customer wade through every date. For the page, the database descends to the end of customer 4217’s run, reads up to twenty entries backwards and fetches those rows, sorting nothing.

interface IndexEntry {
  customerId: number;
  createdAt: string; // 'YYYY-MM-DD', so string order is date order
  orderId: number;
}

function ordersSince(
  index: IndexEntry[],
  customerId: number,
  since: string,
): { orderIds: number[]; examined: number } {
  let examined = 0;
  let lo = 0;
  let hi = index.length;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    const entry = index[mid]!;
    examined += 1;
    const before =
      entry.customerId < customerId ||
      (entry.customerId === customerId && entry.createdAt < since);
    if (before) lo = mid + 1;
    else hi = mid;
  }
  const orderIds: number[] = [];
  for (let i = lo; i < index.length; i += 1) {
    examined += 1;
    if (index[i]!.customerId !== customerId) break;
    orderIds.push(index[i]!.orderId);
  }
  return { orderIds, examined };
}

const index: IndexEntry[] = [];
for (let customerId = 1; customerId <= 10_000; customerId += 1) {
  for (let month = 0; month < 10; month += 1) {
    const day = new Date(Date.UTC(2025, 6 + month, 1));
    index.push({
      customerId,
      createdAt: day.toISOString().slice(0, 10),
      orderId: index.length + 1,
    });
  }
}

const { orderIds, examined } = ordersSince(index, 4217, '2026-01-01');
console.log(orderIds, examined); // [ 42167, 42168, 42169, 42170 ] 22