9. Indexes
The picture to keep in your head
Every question below is answered twice: first in a book, so you can picture it, then in the system, so you know exactly how it works. Each answer ends with a memory code to lock it in.
The picture to keep in your head
You want to find where a 600-page textbook talks about "caching". You could read every page until you find it. Or you could turn to the index at the back: an alphabetical list of words, each with the page numbers where it appears. "Caching: 212, 340." Two seconds instead of two hours.
The index isn't the book. It's a separate, sorted list that tells you where to look. It takes extra pages to print, and every time the book is revised, the index has to be updated too.
That's a database index, almost exactly.
Our running example: the bookstore's orders table, now with millions of rows. Two everyday queries: the "My orders" page (WHERE user_id = ?, newest first) and login (WHERE email = ?).
| In a book | In the system |
|---|---|
| The pages | The table's rows |
| Reading every page | A full table scan |
| The index at the back | An index on a column |
| "Caching: p. 212" | Index entry: value → row location |
| Alphabetical order | The index is kept sorted |
| An index by surname, then first name | A composite (multi-column) index |
| Reprinting the index after every edit | The write cost of indexes |
Figure: the index doesn't hold the story; it holds a sorted list that tells you exactly where to look.