The whole course ▾
System Design · Lesson 10 of 39 · Week 3
Database indexes: how lookups stay fast
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
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
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 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
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
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
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
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
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.
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.
Lessons on weekdays, the week's revision on Saturday, a mock interview on Sunday.