The whole course ▾

System Design · Lesson 10 of 39 · Week 3

Database indexes: how lookups stay fast

Updated 22 Oct 2026 · By Akshay, software engineer, India · 6 min read

QuickBite has 300 million orders, and one customer's order history now takes seconds to load. Today: database indexes.

Got a doubt? Ask in the comments under the video.Subscribe

QuickBite in this lesson

Finding one order among QuickBite's 300 million.

QuickBite is the food delivery app we grow through the course, from one server to millions of orders.

One order in 300 million

One order in 300 million
Customer
App server
Orders DB
300 million rows
GET /history
customer 7's orders
60 GB scanned
waits tens of seconds

Last week, caches and a CDN took most of the reads off QuickBite's database. But every cache miss still lands on it, and this morning one page got painfully slow.

A customer opens their history tab. The app server runs one simple query against the orders DB: every order where the customer ID is seven, newest first. QuickBite has taken three hundred million orders so far, and this customer has placed twelve of them. Twelve rows. How long can that take?

Here's the problem. The database has no idea where customer seven's orders are, so it does the only thing it can: read every row and check it. That's called a full table scan. Three hundred million rows of about two hundred bytes each is sixty gigabytes, read to find twelve rows. That takes tens of seconds, and fifty customers opening the page at once would queue up behind each other for minutes.

The index

The index
IN ONE LINE
Anindexisasortedcopyofone
column,withpointersbacktothe
rows.
One order in 300 million
Customer
App server
Orders DB
300 million rows
GET /history
customer 7's orders
60 GB scanned
waits tens of seconds
Index
customer_id, sorted
find 7
1
12 row
addresses
2
12 orders
3

The fix is an idea you already use with any thick textbook. You don't read every page to find a topic. You turn to the index at the back.

A database index works the same way. It's a separate structure the database keeps beside the table, holding just one column, customer ID, in sorted order, and next to each value, the addresses of the matching rows. Now the query becomes: look up seven in the index, get twelve row addresses, and read exactly those twelve rows. Twelve reads, instead of three hundred million.

So, in one line: an index is a sorted copy of one column, with pointers back to the rows. Making one is a single command: create index on orders, customer ID. The database fills it once, and from then on it updates the index on every insert, automatically. Which, as you'll see, isn't free.

Inside: the B-tree

Inside: the B-tree
Root page
which range?
Branch page
a narrower
range
Leaf page
7 -> row
addresses
Table rows
12 orders
pick a
range
1
narrower
2
fetch rows
3
Why it's fast
One page holds about 500 entries
500 × 500 × 500 = 125 million
4 levels: tens of billions
~ 4 page reads, not 300M rows
THE BONUS
Leavesarekeptin
order,sorangesare
fasttoo:"ordersfrom
thelasthour".

But sorted how, so that finding seven among three hundred million entries is instant? Almost every relational database uses the same shape: the B-tree.

A B-tree is a tree of pages, each a small block of about eight kilobytes. The root page holds a few hundred dividing values: customers below this one, go here; between these two, go there. Each points to a branch page with a narrower range, and so on, down to a leaf page, which holds the actual customer IDs, in order, each with the addresses of its rows. Then the database fetches the table rows.

Here's why that's fast. One page holds around five hundred entries. Three levels of five hundred give five hundred times five hundred times five hundred: a hundred and twenty-five million. Four levels reach tens of billions. So finding any customer takes about four page reads, and the top levels are used so often that they stay in memory. From sixty gigabytes scanned to a handful of page reads: about a millisecond.

And there's a bonus. The leaves are kept in order, each linked to the next, so once the database finds where a range starts, it just walks along. Orders from the last hour, prices between two numbers, names starting with S: all fast. A hash table can find one key just as quickly, but it can't do ranges.

Two columns, one order

Two columns, one order
Index on (customer, time)
customer = 7
customer = 7, newest first
customer = 7, last month
Can't use it
All orders placed today
Every order over ₹1,000

Back to the history tab. Regular customers have hundreds of orders, and the page shows only the newest twenty.

So you build one index on two columns: customer ID first, then order time. Inside, it's sorted like a phone book: by customer, and within each customer, by time. The page's query, customer seven, newest first, becomes: jump to customer seven, start at the newest entry, read twenty, stop. Customer seven's orders from last month work too: that's one range inside customer seven's part.

But here's the rule people forget. This index can't answer all orders placed today, by anyone. Think of a phone book sorted by surname, then first name. Finding every Sharma is easy, and Priya Sharma too. Finding everyone called Priya means reading the whole book. That's the leftmost prefix rule: an index helps only when the query uses its first column. And every order over a thousand rupees needs its own index, on the amount.

The price of an index

The price of an index
What every index costs
Every insert writes every index
Disk, and memory to stay fast
Updates move entries in the tree
B-tree: edit in place
Each write edits pages in place
Small writes all over the disk
Slows as writes pile up
LSM tree: write, then merge
New writes batched in memory
One sorted file, written in one go
Built for heavy writes

So why not index every column? Because an index is a promise the database has to keep on every single write.

Every insert into orders must also go into every index on orders: with five indexes, one new order is six writes. Each index takes disk, and memory, to stay fast. And every update to an indexed column moves its entry inside the tree. For tables that are read far more than written, like menus, that's a bargain. For tables written constantly, it's a tax.

Some data is written far more than it's read, like QuickBite's rider locations, arriving every few seconds from every rider. For data like that there's another design. A B-tree edits pages in place, scattered across the disk. An LSM tree, a log-structured merge tree, collects new writes in memory, writes them out as one sorted file in a single go, and merges those files in the background. Writes get very cheap, reads may check a few files, and that's how Cassandra and RocksDB work. Postgres and MySQL use B-trees.

In the interview

In the interview
SAY THIS IN THE INTERVIEW
Indexthecolumnsyour
queriesfilterandsort
by:here,(customer_id,
created_at).
Follow-ups to expect
->
Why not index every column?
->
Which column goes first?
->
It's write-heavy. Now what?
THE COMMON MISTAKE
Drawingadatabase
boxwithnoword
abouthowitwillbe
read.

Indexes come up in almost every design interview, usually the moment you write down your data model.

When you draw a table, say which index it needs, and why: orders get an index on customer ID and created at, because the history tab filters by customer and sorts by time. One sentence, and the interviewer knows you've thought past the boxes.

Then expect these. Why not index every column? Because each one slows every write and takes memory. Which column goes first in a two-column index? The one every query filters on exactly, then the one you sort or range over. And what if the data is write-heavy? Fewer indexes, or a store built on LSM trees, and say what that costs on reads.

The common mistake is drawing a database box and moving on, as if storing the data were the hard part. The hard part is reading it back fast, and indexes are how.

Quick check

Quick check
?
An index on (customer_id,
created_at). Can "all orders
placed today" use it?
No: the query doesn't use
customer_id, the first column.
Leftmost prefix.
?
A table gets 50,000 writes a
second and very few reads.
More indexes, or fewer?
Fewer: every index is another
write. Or a store built on LSM
trees.
Remember
A scan reads everything; an
index jumps
B-trees: a few page reads,
ranges too
Two columns: leftmost first
Quick check

An index on (customer_id, created_at). Can "all orders placed today" use it?

Show the answer

No: the query doesn't use customer_id, the first column. Leftmost prefix.

Quick check

A table gets 50,000 writes a second and very few reads. More indexes, or fewer?

Show the answer

Fewer: every index is another write. Or a store built on LSM trees.

Remember: a full scan reads everything, while an index jumps straight to the rows. B-trees find any row in a few page reads, and handle ranges too. And a two-column index only helps when the query uses its leftmost column. Next: what happens when even a well-indexed database can't keep up with the reads.

Practise with flashcardsYour progress stays on this device.
New System Design videos at 6 pm

Lessons on weekdays, the week's revision on Saturday, a mock interview on Sunday.