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:
- Leaf pages hold the indexed values in sorted order, each with a pointer to the table row. Leaves are linked to their neighbours, so walking in order is cheap.
- Inner pages hold separator values and pointers down to the child pages, like signposts at a junction.
- All leaves are at the same depth, so every lookup costs the same number of page reads.
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:
| Levels | Rows reachable |
|---|---|
| 2 | 300 × 300 = 90 000 |
| 3 | 300^3 = 27 million |
| 4 | 300^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.
- PostgreSQL stores table rows in a heap, in no particular order. Every index, including the primary key's, points to a row's physical location. A lookup walks the index, then fetches the row.
- MySQL (InnoDB) and SQL Server (by default, for the primary key) use a clustered index: the table is the B-tree of the primary key, with the full rows in its leaves. A secondary index does not store a row location; it stores the primary key value. A lookup by a secondary index therefore walks two trees: the secondary one to find the primary key, then the primary one to find the row [2].
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":
- Equality:
WHERE email = 'ada@example.com'. - Ranges:
WHERE created_at >= '2026-01-01' AND created_at < '2026-02-01'. Find the start, then read along the leaves. - Prefix matches:
WHERE name LIKE 'Ada%', but only if the index is set up for it. In PostgreSQL the plain index works forLIKEonly on a column with theCcollation; otherwise create it withtext_pattern_ops(section 7 shows the test). In SQLite,LIKEis case-insensitive and does not use an ordinary index by default;GLOB 'Ada*'does. - Sorting:
ORDER BY created_at DESC LIMIT 10can read the last ten entries instead of sorting everything. - Min and max: the first or last leaf entry.
- Joins: the index on the joined column lets the database look up matching rows one by one.
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 ANALYZEreally executes the statement. On anUPDATE,INSERTorDELETEthe change happens. Wrap it:BEGIN; EXPLAIN ANALYZE UPDATE ...; ROLLBACK;. In my test, the update changed 5 rows inside the transaction and none after theROLLBACK.
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:
WHERE status = 'paid'(a third of the table) is still a Seq Scan, 12 ms: the index starts withcustomer_id, so it cannot seek onstatusalone (section 5).- After
CREATE INDEX orders_cover ON orders (customer_id, created_at) INCLUDE (total); VACUUM ANALYZE orders;, the querySELECT created_at, total FROM orders WHERE customer_id = 4242becomes an Index Only Scan withHeap Fetches: 0and 0.04 ms (section 6).
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:
SCAN orders: the whole table, and then a sort of whatever matched.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.SEARCH ... (customer_id=? AND status=?)with no sort step: the index finds the right rows and delivers them increated_atorder, soLIMIT 10can 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:
- Seq Scan: reads the whole table. Fine for small tables or when most rows are needed.
- Index Scan: walks the index, and visits the table for each match.
- Index Only Scan: answers from the index alone, never touching the table (section 6).
- Bitmap Index Scan + Bitmap Heap Scan: collects matching row locations first, then reads the table pages in order. PostgreSQL's choice for "many but not most" rows.
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].
| Query | Can use the index well? |
|---|---|
WHERE customer_id = 4242 | Yes: 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_at | Yes, 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
- 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. - Then the column used for a range or for sorting (
>,BETWEEN,ORDER BY). - 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:
- The condition is not searchable. Wrapping the column in a function hides it:
WHERE lower(email) = 'ada@example.com'cannot use an index onemail. Create an expression index onlower(email), or store the value in a form that does not need the function. The same goes forWHERE created_at::date = '2026-06-01'(use a range on the raw column instead) andWHERE price * 2 > 100(move the arithmetic to the other side:price > 50). - The types differ (this one depends on the database). In MySQL, comparing a string column with a number converts every stored string to a number, so the index cannot be used; in SQL Server, comparing a
varcharcolumn with annvarcharparameter does the same. PostgreSQL is stricter:WHERE status = 5on a text column is rejected withoperator does not exist: text = integer, so you find out at once. Match the type of your parameter to the column's type in any case. - A leading wildcard:
LIKE '%ada'cannot use a B-tree (my test: Seq Scan). And a prefix pattern likeLIKE 'User42%'needs the right index: on a PostgreSQL database with theC.UTF-8collation, the ordinary index onemailwas ignored, and an index created withCREATE INDEX ON users (email text_pattern_ops)was used. - Low selectivity. If the condition matches most of the table, reading the index and then jumping around the table is slower than one sequential read, and the planner is right to scan. There is no fixed threshold, and engines differ. In my PostgreSQL test (200 000 rows, index on the column), a condition matching 5 % of the rows used an Index Scan, 25 % and 33 % used a Bitmap scan, and 95 % used a Seq Scan. Other engines (SQLite, MySQL) draw the line elsewhere. Look at the plan, not at a rule of thumb.
ORacross different columns.WHERE a = 1 OR b = 2needs two indexes combined, or a rewrite asUNION.- Stale statistics. The planner chooses with estimates from table statistics. After a big load, run
ANALYZE(PostgreSQL) so the estimates match reality. - The table is small. Reading three pages is cheaper than using an index. It is not a problem.
- The column order is wrong, as in section 5.
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
- Unique indexes enforce a rule ("one account per e-mail") and are searchable. A
PRIMARY KEYand aUNIQUEconstraint create one. - Partial indexes cover only some rows:
CREATE INDEX ON orders (customer_id) WHERE status = 'new'. They are small and fast when queries look at a known slice, such as "unprocessed jobs" [7]. One limit to know: the planner uses a partial index only when it can prove that the query's condition implies the index's condition.WHERE status = 'new'qualifies;WHERE status = $1in a prepared statement with a generic plan does not, because the value is not known when the plan is made. In my test the generic plan ignored the partial index and used another one. Write the constant into the query, or keep a full index. - Expression indexes index a computed value:
CREATE INDEX ON users (lower(email)). - Other index types exist for other questions:
| Type | Good for | Example |
|---|---|---|
| B-tree | Equality, ranges, sorting. The default | Almost everything |
| Hash | Equality only | Rarely worth it over a B-tree |
| GIN | Values that contain many items | Full-text search, jsonb, arrays |
| GiST / SP-GiST | Geometry, nearest neighbour, ranges | Maps, "find within 5 km" |
| BRIN | Huge tables whose values follow their physical order | Time-series logs, very small index |
- LSM trees (RocksDB, Cassandra, LevelDB) are an alternative structure for write-heavy storage: they collect writes in memory and merge them to disk in sorted batches. Writes are cheaper than in a B-tree, reads may need to check several levels. If a question asks "B-tree or LSM?", the answer is: read-heavy and range queries lean B-tree, write-heavy ingestion leans LSM.
9. What indexes cost
Indexes are not free, and a table with fifteen of them is a smell.
- Slower writes. Each insert and delete updates every index; an update touches the indexes of the columns it changes (and, if the row has to move, all of them; PostgreSQL avoids this for updates that change no indexed column through "heap-only tuples").
- Space. Indexes can easily take as much disk and memory as the table. Memory used by an index is memory not used for data.
- Bloat. After many updates and deletes, pages are half empty; periodic
REINDEX(or concurrent re-creation) fixes it. - Planning and maintenance get more complicated with each one.
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
- A B-tree is shallow and sorted: a lookup reads a handful of pages, and ranges and sorting come for free.
- Composite indexes follow the leftmost-prefix rule; put equality columns first, ranges and sorting after.
- Covering indexes can avoid the table altogether.
- Check with
EXPLAIN; wrapped columns, type mismatches and wildcards stop an index from being used. - Indexes make reads faster and writes slower; remove unused ones.
- Keyset pagination beats
OFFSET.
Quick recap
- 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.
- The tree is sorted, so it serves equality, ranges, sorting, min and max.
- In a composite index, the column order decides which queries it can serve: leading columns first, equality before range.
- A covering index (
INCLUDE) can answer a query without visiting the table. - Functions on the column, wildcards at the start, type mismatches, and low selectivity make the planner skip the index.
- Each index costs writes, space and maintenance. Measure and prune.
- Use
EXPLAIN ANALYZEbefore and after every change.
Sources
- Bayer and McCreight, Organization and maintenance of large ordered indexes, Acta Informatica, 1972. The original B-tree paper.
- MySQL documentation, Clustered and Secondary Indexes. How InnoDB stores rows and what its secondary indexes contain.
- PostgreSQL documentation, Using EXPLAIN.
- SQLite documentation, EXPLAIN QUERY PLAN. The tool used for the experiment above.
- Markus Winand, Use The Index, Luke. A free book on SQL indexing for developers; covers composite index order and keyset pagination ("no offset").
- PostgreSQL documentation, Index-Only Scans and Covering Indexes.
- PostgreSQL documentation, Partial Indexes and Multicolumn Indexes.
Practise this topic: Databases