CS Fundamentals Trainer · Guides

How database indexes work

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

20 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.

Where the row itself lives

So far an index entry "points to the row". How depends on the database.

This changes some advice. In InnoDB a wide primary key (a 36-character UUID string) is copied into every secondary index and makes them all bigger, and a random primary key scatters inserts through the table itself, not only through an index. The "covering index" idea works especially well there, because it skips the second walk.

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 also runs the query and shows real row counts and times [3].

Careful: EXPLAIN ANALYZE really executes the statement. On an UPDATE, INSERT or DELETE the change happens. Wrap it: BEGIN; EXPLAIN ANALYZE UPDATE ...; ROLLBACK;. In my test, the update changed 5 rows inside the transaction and none after the ROLLBACK.

An experiment in PostgreSQL

Copy this into psql. It builds 200 000 orders for 20 000 customers, and asks for the ten latest paid orders of one customer:

CREATE TABLE orders (
  id bigserial PRIMARY KEY, customer_id int, status text, created_at date, total numeric(8,2));

INSERT INTO orders (customer_id, status, created_at, total)
SELECT 1 + floor(random() * 20000)::int,
       (ARRAY['new', 'paid', 'shipped'])[1 + floor(random() * 3)::int],
       date '2026-01-01' + floor(random() * 300)::int,
       round((random() * 100)::numeric, 2)
FROM generate_series(1, 200000);
ANALYZE orders;

EXPLAIN (ANALYZE, COSTS OFF)
SELECT id, total FROM orders
WHERE customer_id = 4242 AND status = 'paid'
ORDER BY created_at DESC LIMIT 10;

This is what I got on PostgreSQL 16 (yours will differ in the numbers). Without an index:

 Limit (actual rows=2 loops=1)
   ->  Gather Merge (actual rows=2 loops=1)
         ->  Sort (actual rows=1 loops=2)
               Sort Key: created_at DESC
               ->  Parallel Seq Scan on orders (actual rows=1 loops=2)
                     Filter: ((customer_id = 4242) AND (status = 'paid'::text))
                     Rows Removed by Filter: 99999
 Execution Time: 14.205 ms

After CREATE INDEX orders_cust_status_created ON orders (customer_id, status, created_at); ANALYZE orders;:

 Limit (actual rows=2 loops=1)
   ->  Sort (actual rows=2 loops=1)
         Sort Key: created_at DESC
         ->  Bitmap Heap Scan on orders (actual rows=2 loops=1)
               Recheck Cond: ((customer_id = 4242) AND (status = 'paid'::text))
               ->  Bitmap Index Scan on orders_cust_status_created (actual rows=2 loops=1)
                     Index Cond: ((customer_id = 4242) AND (status = 'paid'::text))
 Execution Time: 0.081 ms

From 14.2 ms to 0.08 ms: the first plan looks at all 200 000 rows (every one of them is read and rejected, "Rows Removed by Filter"), the second at the 2 that match. Only two rows match, so PostgreSQL happily sorts them itself; for a customer with thousands of paid orders it would instead walk the index backwards and stop after ten entries, with no sort at all. Two more plans from the same table:

The same experiment in SQLite

If you only have Python, SQLite [4] needs nothing installed. It builds the same table:

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. (PostgreSQL chose to sort two rows by itself instead; both are fine for so few rows.)

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.

The words to know when reading PostgreSQL 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" [5].

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 order among them hardly changes the cost of one lookup; what it changes is which other queries can reuse the index, because they must use a leading prefix. Put first the column that most of your queries filter on.
  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 [6].

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.

Index your foreign keys

A foreign key (orders.customer_id REFERENCES customers(id)) makes the database check, whenever a customer is deleted or its key changes, that no order still points to it. PostgreSQL indexes the referenced column (the primary key) but does not create an index on the referencing column; MySQL's InnoDB does. Without one, every such check scans the whole child table. In my test (200 000 orders, no index starting with customer_id), deleting a customer who had no orders still took 7.6 ms, because the check scanned the whole orders table, and 0.4 ms after CREATE INDEX ON orders (customer_id); the cost grows with the table, and the same scan slows every join on that column. As a habit, index the foreign key columns, either alone or as the leading column of a composite index.

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 [5].

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. In InnoDB it is worse, because the primary key is the table's own order and is copied into every secondary index (see "Where the row itself lives"); store UUIDs as 16 bytes (BINARY(16)), not as 36 characters. 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. MySQL documentation, Clustered and Secondary Indexes. How InnoDB stores rows and what its secondary indexes contain.
  3. PostgreSQL documentation, Using EXPLAIN.
  4. SQLite documentation, EXPLAIN QUERY PLAN. The tool used for the experiment above.
  5. Markus Winand, Use The Index, Luke. A free book on SQL indexing for developers; covers composite index order and keyset pagination ("no offset").
  6. PostgreSQL documentation, Index-Only Scans and Covering Indexes.
  7. PostgreSQL documentation, Partial Indexes and Multicolumn Indexes.

Practise this topic: Databases

More guides