CS Fundamentals Trainer · Guides

How database indexes work

B-trees, composite index order, covering indexes, reading EXPLAIN, and why the database ignores your index.

15 min read

An index is a second copy of some columns of a table, kept in an order that makes searching fast. Without one, the database reads every row to answer "which orders belong to customer 4242?". With one, it jumps straight to the right place. Almost every performance problem in a relational database ends in one of two sentences: "there is no index for this query" or "there is an index, and the query cannot use it". This guide explains how indexes work well enough to tell which case you are in.

1. The problem an index solves

A table is stored as a pile of pages (blocks of a few kilobytes, 8 KB in PostgreSQL). To find rows matching a condition with no index, the database does a sequential scan: read every page, check every row. The cost grows with the table. A million rows is fine; a hundred million is a minute.

An index makes the cost grow with the logarithm of the table instead. Searching a sorted list by repeatedly halving it is the same idea as binary search, only arranged for disks, where the expensive thing is the number of pages read, not the number of comparisons.

Think of the index at the back of a book. You do not read the whole book to find "mutex"; you look it up alphabetically and go to the listed pages.

2. How a B-tree works

The default index in practically every relational database is a B-tree (strictly, a B+tree in most systems) [1]. It is a tree of pages:

Diagram: A tiny B-tree: find 57 by following one page per level

To find 57: at the root, 57 is between 40 and 80, so go to the middle child; there, it lies between 50 and 60, so go to that leaf; scan it and find 57. Three pages, however large the table.

Why the tree is so shallow

A page holds hundreds of entries, so each level multiplies the reach by hundreds. With about 300 entries per page:

LevelsRows reachable
2300 × 300 = 90 000
3300^3 = 27 million
4300^4 = 8.1 billion

A table with tens of millions of rows needs a lookup of about 3 or 4 page reads. The top levels stay in memory because every query touches them, so in practice the cost is one or two reads from disk. That is why an index lookup takes about the same time on a small table and a huge one.

Writes: keeping it sorted

Inserting a value means finding its leaf and adding it there. If the leaf is full, it is split into two, and a new separator goes up to the parent (which may split in turn). Deleting and updating indexed values touch the index too. This is the price of an index: every insert, update of an indexed column, and delete does extra work in every index of the table.

3. What an index can do for a query

A B-tree keeps values sorted, so it helps with more than "equals":

It does not help with WHERE name LIKE '%ada%' (the match can start anywhere, so the sort order is no use), nor with most calculations done on the column (more in section 7).

4. Seeing it: EXPLAIN

Never guess; ask the database for its plan. In PostgreSQL that is EXPLAIN (and EXPLAIN ANALYZE, which also runs the query and shows real times) [2]. Here is a runnable experiment you can copy. It uses SQLite [6] so that it needs nothing installed (Python includes it), and builds a table of 200 000 orders:

import sqlite3, random

db = sqlite3.connect(":memory:")
db.execute("""CREATE TABLE orders (
  id INTEGER PRIMARY KEY, customer_id INTEGER, status TEXT, created_at TEXT, total REAL)""")
random.seed(1)
db.executemany(
    "INSERT INTO orders (customer_id, status, created_at, total) VALUES (?, ?, ?, ?)",
    [(random.randint(1, 20000), random.choice(["new", "paid", "shipped"]),
      f"2026-{random.randint(1, 10):02d}-{random.randint(1, 28):02d}", random.random() * 100)
     for _ in range(200000)])

query = """SELECT id, total FROM orders
           WHERE customer_id = 4242 AND status = 'paid'
           ORDER BY created_at DESC LIMIT 10"""

def plan():
    for row in db.execute("EXPLAIN QUERY PLAN " + query):
        print("  ", row[3])

print("no index");              plan()
db.execute("CREATE INDEX orders_customer ON orders (customer_id)")
print("index on customer_id");  plan()
db.execute("DROP INDEX orders_customer")
db.execute("CREATE INDEX orders_cust_status_created ON orders (customer_id, status, created_at)")
print("composite index");       plan()

This is the output I got (SQLite 3.45):

no index
   SCAN orders
   USE TEMP B-TREE FOR ORDER BY
index on customer_id
   SEARCH orders USING INDEX orders_customer (customer_id=?)
   USE TEMP B-TREE FOR ORDER BY
composite index
   SEARCH orders USING INDEX orders_cust_status_created (customer_id=? AND status=?)

Three different stories:

  1. SCAN orders: the whole table, and then a sort of whatever matched.
  2. SEARCH ... (customer_id=?): jumps to this customer's rows (about 10 of the 200 000), but still has to filter by status and sort them.
  3. SEARCH ... (customer_id=? AND status=?) with no sort step: the index finds the right rows and delivers them in created_at order, so LIMIT 10 can stop after ten entries.

On my machine the query took about 6.5 ms without an index and 0.09 ms with the composite one. The gap grows with the table: the scan is proportional to the rows, the lookup to the depth of the tree.

In PostgreSQL the same question looks like this (the shape of the output; your numbers will differ):

Limit
  ->  Index Scan Backward using orders_cust_status_created on orders
        Index Cond: ((customer_id = 4242) AND (status = 'paid'::text))

The words to know when reading plans:

5. Composite indexes: column order is everything

An index on (customer_id, status, created_at) is sorted by customer, then within a customer by status, then within a status by date. Like a phone book sorted by last name and then first name, it is excellent for "all the Smiths" and for "John Smith", and useless for "everyone called John" [3].

QueryCan use the index well?
WHERE customer_id = 4242Yes: the leading column
WHERE customer_id = 4242 AND status = 'paid'Yes: the first two columns
WHERE customer_id = 4242 AND status = 'paid' ORDER BY created_atYes, and no sort needed
WHERE customer_id = 4242 AND created_at > '2026-06-01'Partly: finds the customer, then must filter the dates inside it
WHERE status = 'paid'Poorly: the leading column is missing, so it cannot seek
WHERE status = 'paid' AND created_at > '2026-06-01'Poorly, for the same reason

(Recent PostgreSQL versions can sometimes "skip" over a missing leading column when it has few distinct values. It helps in some cases, but do not design around it.)

A rule of thumb for the order

  1. Equality columns first (=), the most selective or most commonly used first.
  2. Then the column used for a range or for sorting (>, BETWEEN, ORDER BY).
  3. Columns after a range column are used only for filtering inside the range, not for seeking.

Design indexes from your real queries, not from the table. List the ten queries that matter most; an index that serves three of them beats three narrow indexes. One composite index on (a, b) also serves queries on a alone, so a separate index on a is redundant, and costs every write.

6. Covering indexes and index-only scans

Normally the index finds the row and the database then visits the table to read the other columns. If the index itself contains every column the query needs, the visit is unnecessary: an index-only scan. In my SQLite test, adding total to the index changed the plan to USING COVERING INDEX.

PostgreSQL lets you add columns to an index without making them part of its sort order, with INCLUDE:

CREATE INDEX orders_customer_covering
  ON orders (customer_id, created_at)
  INCLUDE (total);

A covering index is faster for hot queries, but it is bigger, and it costs more on every write, so use it for a few important queries only. In PostgreSQL an index-only scan also needs the table's visibility map to be up to date, which VACUUM maintains; on a table that changes constantly, the saving can shrink [4].

7. Why the database ignores your index

You created the index, and the plan still shows a sequential scan. The usual reasons:

When you suspect a problem, do not trust the plan alone: EXPLAIN ANALYZE shows the estimated and the actual number of rows for every step. A big gap between them is the clue.

8. Special kinds of indexes

TypeGood forExample
B-treeEquality, ranges, sorting. The defaultAlmost everything
HashEquality onlyRarely worth it over a B-tree
GINValues that contain many itemsFull-text search, jsonb, arrays
GiST / SP-GiSTGeometry, nearest neighbour, rangesMaps, "find within 5 km"
BRINHuge tables whose values follow their physical orderTime-series logs, very small index

9. What indexes cost

Indexes are not free, and a table with fifteen of them is a smell.

Find the ones nobody uses. In PostgreSQL, pg_stat_user_indexes.idx_scan counts how often each index was used since statistics were last reset. An index with zero scans over weeks (and that is not enforcing a unique constraint) is a candidate for removal. Create indexes on big live tables with CREATE INDEX CONCURRENTLY, so writes are not blocked while it builds.

10. Pagination: where indexes meet product design

Showing page 5,000 of a list with OFFSET is slow, even with an index, because the database must walk past all the skipped rows:

-- slow for deep pages: reads and throws away 100 000 rows
SELECT * FROM orders WHERE customer_id = 4242 ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 100000;

-- fast at any depth: seek to where the previous page ended
SELECT * FROM orders
WHERE customer_id = 4242 AND (created_at, id) < ('2026-06-01 10:00', 9812)
ORDER BY created_at DESC, id DESC
LIMIT 20;

The second form is keyset pagination: the client sends back the last (created_at, id) it saw, and the query seeks to it using the index on (customer_id, created_at, id). The id breaks ties, so no row is skipped or repeated. The price is that you cannot jump to "page 5,000", which for feeds and infinite scroll nobody needs [3].

11. Questions interviewers like to add

"Should I index every column?"

No. Index what you filter, join, and sort by, in the order your queries use, and measure. Every index slows writes and takes space.

"How do you find which index to add?"

Start from the slow query log or pg_stat_statements for the queries that take the most total time. Run EXPLAIN ANALYZE. Add the index. Run EXPLAIN ANALYZE again and compare the numbers, not just the plan.

"Primary key: UUID or integer?"

A random UUID inserts into random places in the tree, which causes many page splits and makes the index larger and slower to maintain than sequential integers or time-ordered ids (such as UUID version 7). Random ids also spread the working set over all pages rather than the recent ones. Choose on needs (global uniqueness, hiding counts), and know the cost.

"Why does my query get slow only sometimes?"

The plan can change with the parameters (a customer with 3 orders and one with 3 million need different plans), with stale statistics, or when the index no longer fits in memory.

12. Things to mention in an interview

Quick recap

  1. Without an index, a query reads the whole table. A B-tree reduces it to about 3 or 4 page reads, even for billions of rows.
  2. The tree is sorted, so it serves equality, ranges, sorting, min and max.
  3. In a composite index, the column order decides which queries it can serve: leading columns first, equality before range.
  4. A covering index (INCLUDE) can answer a query without visiting the table.
  5. Functions on the column, wildcards at the start, type mismatches, and low selectivity make the planner skip the index.
  6. Each index costs writes, space and maintenance. Measure and prune.
  7. Use EXPLAIN ANALYZE before and after every change.

Sources

  1. Bayer and McCreight, Organization and maintenance of large ordered indexes, Acta Informatica, 1972. The original B-tree paper.
  2. PostgreSQL documentation, Using EXPLAIN.
  3. Markus Winand, Use The Index, Luke. A free book on SQL indexing for developers; covers composite index order and keyset pagination ("no offset").
  4. PostgreSQL documentation, Index-Only Scans and Covering Indexes.
  5. PostgreSQL documentation, Partial Indexes and Multicolumn Indexes.
  6. SQLite documentation, EXPLAIN QUERY PLAN. The tool used for the experiment above.

Practise this topic: SQL & Databases

More guides