Quiz
Warm-up from unit 3: your cache absorbs 90% of reads, but the database is still slow. Which requests is it still serving?
Why a query gets slow
From your SQL course you know SELECT * FROM users WHERE email = 'ada@x.com'. Without help, the database answers this by checking every row in the table, a full table scan. At 1,000 rows nobody notices. At 10 million rows every query does 10 million checks.
An index is a sorted lookup structure the database maintains next to a table, usually a B-tree. Because it is sorted, the database can find a value the way you find a word in a dictionary: jump to the middle, decide left or right, repeat. Each jump halves the search space, so 10 million rows take about log₂(10,000,000) ≈ 24 checks instead of 10 million.
CREATE INDEX idx_users_email ON users(email);
One line, and that query goes from seconds to under a millisecond.
Code exercise · python
Run this comparison of a full scan against a B-tree index on a 10-million-row table. math.log2 counts how many times you can halve the table, math.ceil rounds up.
Code exercise · python
Your turn: the table grew to 1 billion rows. Print the same three lines for the bigger table. Notice the scan cost grew 100x while the index cost barely moved.
Quiz
Indexes make reads faster. What do they cost?