Indexing
Adda's login page starts timing out, and Shuvo finds the database reading every row to find one. Finding a needle in millions by checking each straw is hopeless — an index is the book's table of contents for your data.
The problem
Fahim texts at 9pm: "login is spinning." He is the canary again — but this time it is not just him. Adda's users table has crossed 50 million rows, and the login page is timing out for everyone. Shuvo pulls up the query and it looks trivial — WHERE email = ? — but Postgres is reading every single row to find the one that matches, because email is not indexed.
That is a full table scan: 50 million comparisons for one login. At a few hundred logins per second, the disk and CPU are pinned and everything else queues behind it. The data is fine. The problem is that the database has no faster way to find things than looking at all of them.
A first attempt
Tanvir's instinct is "add more hardware" — the reflex that worked back in Part 1 until it didn't. A bigger machine reads rows faster, so the scan finishes sooner. But it only pushes the wall further out. A scan is still O(n), so doubling Adda's users doubles the work no matter how fast the box.
The real cost is the algorithm, Shuvo says. Searching an unordered list is linear. If instead the data were sorted by email, you could binary-search it in O(log n) — about 26 comparisons for 50 million rows instead of 50 million. But you cannot keep the table itself sorted by every column you query. You need a separate, sorted structure that points back into the table.
The insight
Build a secondary sorted structure keyed by the column you search, and let it point at the rows. That is an index.
The workhorse is the B-tree (really a B+ tree): a wide, shallow, balanced tree that stays sorted as you insert and delete. Because each node holds hundreds of keys, the tree is only 3–4 levels deep even for billions of rows, so a lookup is a handful of disk reads instead of a full scan. Range queries (created_at BETWEEN …) work too, because siblings are linked in sorted order.
A hash index is the other shape: it maps a key straight to a location in O(1), unbeatable for exact-match lookups — but it cannot do ranges or sorting, because a hash throws ordering away.
How it works
The index stores keys in sorted order
Instead of scanning the table, the database walks a B-tree keyed on email. Each step discards most of the remaining keys, so it reaches the leaf in O(log n).
The leaf points back to the row
The leaf holds a pointer (a row id or the primary key) to the actual row on disk. One more read fetches the full record. This second hop is why indexes are not free reads.
A covering index skips the second hop
If the index already contains every column the query needs, the database answers straight from the index and never touches the table. That turns two reads into one.
Composite indexes follow the leftmost-prefix rule
An index on (country, city) helps queries filtering by country, or country AND city, but not by city alone — because the keys are sorted by country first. Order the columns to match your most common filters.
Every write must update every index
Inserting a row means inserting into the table and into each index that covers it, keeping every B-tree balanced. More indexes means slower writes and more storage.
Concrete numbers
On Adda's 50 million rows, a full scan reads all 50M rows; a B-tree lookup touches roughly log₂(50,000,000) ≈ 26 keys, in practice 3–4 disk pages because each node is wide. That is the difference between a login that takes seconds and one that takes under a millisecond — and Fahim's spinner disappears the moment Shuvo adds the index.
The write cost is real. Each additional index typically adds 10–20% to insert time and its own storage — an index can be 20–40% of the size of the column it covers. A table with eight indexes can spend more time maintaining indexes than writing the row itself. That is why Adda's write-heavy tables (the likes stream) carry few indexes and read-heavy tables (profiles) carry many.
When to use it
The trade-off
An index makes reads fast and writes slower. You are spending write throughput and disk to buy read latency. Index the columns you filter, join, and sort on — and resist indexing everything, because unused indexes cost you on every insert while helping no query.
Watch for low selectivity
An index on a column with few distinct values (a boolean is_active, a status with three states) barely helps — half the table still matches, so the planner may scan anyway. Indexes pay off when a lookup eliminates most of the rows.
Practice
Recap
- A full scan is
O(n); an index turns lookups intoO(log n)(B-tree) orO(1)(hash). - B-trees also serve ranges and sorts; hash indexes only serve exact matches.
- Every index speeds reads but slows writes and costs storage — index deliberately.
SQL vs NoSQL
Choosing the store whose access patterns your indexes will serve.
Sharding
When one machine's indexes are no longer enough.
Caching Fundamentals
The other way to make repeated reads fast.
In an interview
When asked to make a slow query fast, say "what does the query filter and sort on?" and propose an index that matches — then immediately name the cost: slower writes and more storage. Mentioning covering indexes, composite key order, and selectivity signals you understand indexes as a trade, not a magic switch.
How is this guide?
Last updated on
SQL vs NoSQL
Adda's data model is finally firming up, and Ria has to answer the question she has dodged for months — which database? Shuvo joins to make her answer it on purpose.
Replication
Adda's one database reboots at 2am and takes the whole app down with it. Replication keeps copies alive and reads fast — at the price of keeping them in sync.