Indexes

The problem: one user among 10 million rows

Say your app's users table has 10 million rows, one per user, each about 1 KB. Every sign-in runs a query like this one:

SELECT * FROM users WHERE email = 'ana@x.com';

The rows are stored in sign-up order, so nothing tells the database where ana's row is. Without an index it reads the rows one by one and compares each email: a full table scan. That's 10 million rows × 1 KB, about 10 GB, read to find one user. Even with every row in memory at about 100 ns each, 10 million of them take about a second, and that's one sign-in.

Finding someone who is there reads half the rows on average; an email nobody has reads all of them. A real database without a unique index on email even reads on after a match, since another row could have the same email.

How an index works

A dictionary is easy to search because its words are sorted. An index gives a table the same trick: a second, sorted copy of one column, where each entry points to its row. Here is a small users table, in sign-up order, and its index on email:

id   email        email        id
1    kai@x.com    ana@x.com    7
2    zoe@x.com    bea@x.com    5
3    eva@x.com    eva@x.com    3
4    tom@x.com    ida@x.com    9
5    bea@x.com    kai@x.com    1
6    max@x.com    leo@x.com    8
7    ana@x.com    max@x.com    6
8    leo@x.com    sam@x.com    10
9    ida@x.com    tom@x.com    4
10   sam@x.com    zoe@x.com    2

A scan for ana@x.com reads rows 1 to 7 before it finds her. A binary search in the index checks the middle entry, keeps the half that can still hold the email, and repeats:

looking for   entries checked              then
ana@x.com     kai, bea, ana                read row 7
zoe@x.com     kai, sam, tom, zoe           read row 2
amy@x.com     kai, bea, ana (not there)    nothing to read

Three checks and one row instead of seven rows. For the missing amy@x.com the scan reads all 10 rows, while the search knows after 3 checks that amy would come first, before ana, and isn't there.

Why it scales: halving

Each check leaves at most half of what was left: 10 entries, then 5, then 2, then 1. So a search takes about log₂ n checks, and doubling the table adds just one more:

rows         a scan reads (worst case)   a binary search checks
10           10                          4
1,000        1,000                       10
1 million    1 million                   20
10 million   10 million                  24

2¹⁰ is about 1,000 and 2²⁰ about a million, so 24 halvings cover 10 million.

B-trees: how databases store an index

On disk, each check of a binary search can land somewhere else: up to 24 reads, at about 10 ms each on a spinning disk, a quarter of a second.

So databases store indexes as a B-tree, the default index in PostgreSQL and MySQL. Its nodes are pages of 8 or 16 KB, each holding a few hundred sorted keys, and each key leads to a page below. Say a page holds about 500 keys:

• Level 1, the root: 1 page, leading to up to 500 pages.
• Level 2: up to 500 pages, leading to up to 250,000 pages.
• Level 3: up to 250,000 pages of 500 keys, room for 125 million entries.

Three levels reach any of 10 million emails, and the top two are small enough to stay in memory, so a lookup usually reads a page or two from disk: up to about 20 ms on a spinning disk, about 0.2 ms on an SSD at 100 µs a read. A full page splits in two, which keeps every lookup the same few levels deep. And because the keys stay in order, a B-tree answers ranges and sorting too: "the 20 newest users" reads the last 20 entries of an index on created_at.

The cost: every index slows every write

An index is only useful while it lists every row, in order, so the database updates it on every insert, every delete, and every change to the indexed column. With indexes on email and name, a new user is three writes: the row and one entry in each index, each put in its sorted place. Index all 10 columns and each new user becomes 11 writes where 1 would do.

Indexes take space too. An email index entry is about 30 bytes, a 20-character email plus a pointer to the row, so on 10 million users the index is a few hundred MB: 300 MB before any overhead.

Which columns to index

Index what your busy queries look up or sort by:

• Busy lookups and sorts: a user by username for every mention, the 20 newest users on every home page visit. Without an index each one is a scan.
• The primary key: already indexed by the database. The email index also answers "is this email taken?" at sign-up.
• Rare queries: a nightly report counting users per country can scan once a day. An index would slow every sign-up all day to save it a few seconds.
• Columns with few values: is_active, true for 95% of users, can't narrow 10 million rows down to a few, so the database reads the table instead.

Indexes on two columns

A feed asks for one user's latest posts: WHERE user_id = 7 ORDER BY created_at DESC LIMIT 20. A composite index on (user_id, created_at) sorts its entries by user first, then each user's posts by time, so user 7's entries sit side by side and the database reads the newest 20 and stops.

Column order matters. Like a list sorted by last name, then first name, the index helps queries on its leftmost column: all of user 7's posts, or user 7's posts in a date range. It can't help "every post since Oct 22, from all users": the dates are sorted only inside each user, so those posts are scattered through the whole index. That query needs an index that starts with created_at.

Where indexes show up in design interviews

Indexes belong to the Data step of a design interview, the data model, where the interviewer often asks "what's the access pattern?" Answer in this order:

1. List the busy queries: "a user's latest posts, 2,000 times a second."
2. Pick the tables and their keys: "posts, with post_id as the primary key."
3. Name the index each busy query uses: "(user_id, created_at) for the feed."
4. Say what it costs: "every new post also updates that index."

That answers "how does this query avoid a full scan?" before it's asked, and shows you know indexes trade write speed for read speed.

Common interview questions on indexes

Why not index every column?

Every index adds a write to every insert and takes space: 10 indexes make each new row 11 writes.

What's the difference between a primary key and an index?

The primary key identifies each row, and the database indexes it automatically; MySQL's InnoDB even stores the table in primary-key order. Other indexes are secondary: each entry points to its row.

When does a database scan even though there's an index?

When a query matches a large share of the rows, like is_active = true for 95% of users, jumping from index entries to scattered rows costs more than reading the table in order. The query planner estimates both and picks the cheaper.

B-tree or hash index?

A hash index finds an exact key quickly but keeps no order, so it can't answer ranges or sorting. A B-tree does exact matches in a few page reads and ranges and ORDER BY as well, which is why it's the default.

Summary

• Without an index, finding one row is a full scan: 10 million rows, about 10 GB.
• An index is a sorted copy of a column, each entry pointing to its row.
• Binary search halves at every check: 4 checks for 10 entries, about 24 for 10 million.
• Databases use B-trees: pages of hundreds of keys, 3 levels for 10 million rows.
• Every index slows every write and takes space: index what busy queries look up or sort by.
• In a two-column index the leftmost column comes first.