Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Databases and Storage Fundamentals

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.

Intermediate 14 min Last reviewed

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:

A B-tree search for key 42 The root page holds keys 40 and 80. Searching for 42, the path goes to the middle child, which holds 50 and 65, then to its leftmost leaf, which contains 41, 42 and 47 and points to the row. [ 10 | 25 ] keys < 40 [ 41 42 47 ] leaf: row pointers [ 52 58 61 ] leaf [ 66 70 77 ] leaf [ 50 | 65 ] 40 to 79 [ 90 | 95 ] keys >= 80 [ 40 | 80 ] root page Figure 1. Looking up 42: the root says 40 to 80 is the middle branch, that page says below 50 is the left leaf, and the leaf points to the row. Three page reads, and real pages hold hundreds of keys, not two or three.

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

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. Search for 35. Count the nodes read: one per level.
  2. 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.
  3. 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:

indexes.pyruns with python3 (standard library sqlite3)
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_id uses the index (SEARCH). A query on status alone 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

OptionWins whenLoses 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 WHERE and JOIN, 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

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

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

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

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

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy