System Design HLD-06.02
Indexes and B-trees
Full scans versus index lookups, how a B-tree finds any row in a few page reads, composite and covering indexes, and what every index costs on writes.
The big idea
Ask a table of 100 million orders for "the orders of customer 42" and, with no help, the database has only one option: read every row and keep the matches. That is a full table scanReading every row of a table to find the ones that match a query. Cost grows with the size of the table., and its cost grows with the table. An indexA separate data structure that keeps a table's values for some columns in sorted order with pointers to the rows, so matching rows can be found without scanning. is a sorted copy of one or more columns with pointers back to the rows, like the index at the back of a book. With it, the database jumps to customer 42 in a handful of reads, whether the table has a thousand rows or a billion.
Indexes are the single most effective performance tool in databases, and the most common cause of slow queries when missing. But they are not free: every index must be updated on every insert, update and delete, and takes disk and memory. Good schema design is choosing the few indexes your real queries need.
Think of a phone book sorted by surname. Finding "Lovelace" takes seconds because you can jump to the L pages. Finding everyone who lives on Elm Street needs a different book, one sorted by street, or a page-by-page read.
How it works
Step 1: The B-tree
Almost every relational database index is a B-treeA balanced tree whose nodes are disk pages holding many sorted keys; every leaf is at the same depth, so any key is found in a few page reads.: a tree whose nodes are disk pages holding many sorted keys and pointers to children. To find a key, start at the root, pick the child whose range contains the key, and repeat down to a leaf:
The power is in the fan-out. Real pages are typically 8 to 16 KB and hold hundreds of keys each, so the tree is very shallow: with about 300 keys per page, three levels cover a million rows and four cover a billion. The top levels are almost always in memory, so a lookup costs one or two disk reads. Because leaves are sorted and linked, range queries (created BETWEEN ..., ORDER BY) just walk neighboring leaves.
Try it
Try this:
- Search for 35. Count the nodes read: one per level.
- Insert 31, 32, 33 and 34. Watch a full node split, pushing its middle key up. Keep inserting until the root splits: the tree grows taller at the top, so every leaf stays at the same depth.
- Press Insert 10 random several times. The key count grows quickly while the height barely moves: that is logarithmic growth.
Step 2: Composite and covering indexes
An index on several columns, (customer_id, status), is sorted by the first column, then by the second within each first value, like a phone book sorted by surname, then first name. That has two consequences:
import math, sqlite3
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE orders (id INTEGER PRIMARY KEY, customer_id INT, status TEXT, total REAL, created TEXT)")
db.executemany("INSERT INTO orders VALUES (?, ?, ?, ?, ?)",
[(i, i % 5000, ["paid", "shipped", "refunded"][i % 3], i % 400, f"2026-{1 + i % 12:02}-01")
for i in range(100_000)])
def plan(sql):
return " | ".join(row[-1] for row in db.execute("EXPLAIN QUERY PLAN " + sql))
q1 = "SELECT * FROM orders WHERE customer_id = 42"
q2 = "SELECT * FROM orders WHERE status = 'paid'"
q3 = "SELECT customer_id, status FROM orders WHERE customer_id = 42 AND status = 'paid'"
print("no index: ", plan(q1))
db.execute("CREATE INDEX idx_cust_status ON orders (customer_id, status)")
print("composite index: ", plan(q1))
print("2nd column only: ", plan(q2))
print("covering the query:", plan(q3))
# Why so few page reads: a B-tree with ~300 keys per page is very shallow.
for rows in (1e6, 1e9):
print(f"{rows:>13,.0f} rows -> about {math.ceil(math.log(rows, 300))} levels to reach any key")Output
no index: SCAN orders
composite index: SEARCH orders USING INDEX idx_cust_status (customer_id=?)
2nd column only: SCAN orders
covering the query: SEARCH orders USING COVERING INDEX idx_cust_status (customer_id=? AND status=?)
1,000,000 rows -> about 3 levels to reach any key
1,000,000,000 rows -> about 4 levels to reach any key - A query on
customer_iduses the index (SEARCH). A query onstatusalone cannot, because status values are scattered across the index (SCAN): the leftmost prefix rule. Put the column you filter on most, usually with equality, first. - When the index contains every column the query needs, the database answers from the index alone without visiting the table: a covering indexAn index that includes every column a query needs, so the query is answered from the index without reading the table rows..
Step 3: The cost of indexes
Every index is another sorted structure to update. A table with six indexes turns one insert into seven writes, and updates to indexed columns move entries around. Indexes also use disk and, more importantly, memory: an index that does not fit in RAM makes every lookup slower. So index for the queries you actually run, check with EXPLAIN, and drop indexes nothing uses.
Going deeper
Selectivity
An index helps most when a query matches a small fraction of rows. An index on status with three possible values may be ignored by the planner, because fetching a third of the table through an index is slower than scanning it. High-selectivity columns (ids, emails, timestamps) make the best indexes.
Other index types
Hash indexes answer only equality but in one step. Full-text indexes power text search ( Inverted indexes and full-text search ). Geospatial indexes handle "near me" queries ( Geospatial indexing ). And log-structured engines organize writes differently from B-trees altogether, in Storage engines: B-tree vs LSM-tree .
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Index a column | Frequent, selective lookups, joins and sorts on that column | Write speed, disk and memory, for every index you add |
| Composite index | Queries filtering on several columns together, in leftmost-prefix order | Queries on later columns alone |
| Covering index | Hot queries that can be answered entirely from the index | Index size, since it stores extra columns |
Common mistakes
- No index on columns used in
WHEREandJOIN, so a small table works in development and times out in production. - Indexing every column "just in case", slowing every write.
- Composite indexes in the wrong order for the queries that use them.
- Wrapping an indexed column in a function (
WHERE lower(email) = ...), which prevents the index from being used unless you index the expression.
Check yourself
-
Why can a B-tree find a key among a billion rows in about four page reads?
Show answer
B. Each page holds hundreds of keys, so the tree is very shallow High fan-out means each level multiplies the reach by hundreds: 300^4 is about 8 billion.
-
You have an index on (customer_id, status). Which query can use it?
Show answer
B. WHERE customer_id = 42 Composite indexes follow the leftmost-prefix rule; status alone is not a prefix.
-
What is a covering index?
Show answer
B. An index that holds all columns a query needs, so the table is not read The query is answered from the index pages alone.
-
A table has 8 indexes. What happens on each insert?
Show answer
B. The table and all 8 indexes must be updated Every index must reflect the new row, so writes cost more as indexes grow.
Recap
- Without an index, a query scans the whole table; an index jumps to matching rows.
- B-trees have huge fan-out, so any key is a few page reads away, and leaves support ranges.
- Composite indexes follow the leftmost-prefix rule; order columns by how you filter.
- Covering indexes answer queries from the index alone.
- Every index costs writes, disk and memory: index for real queries and check with EXPLAIN.