Part 2 of 8 · 2 min read
Why an index exists
A scan reads everything. An index is a signpost kept on the side.
Think of a thick phone book without an alphabet. To find one name, the reader starts at page one and reads until the name appears. Now think of a phone book sorted by name. The reader opens near the middle, sees whether the name comes before or after, and narrows down in a few steps.
The book "Designing Data-Intensive Applications" begins with the simplest possible database: a text file where every write adds a line at the end, and every read searches the whole file for the last line with the key. Writing is very fast, since adding to the end of a file is the simplest write. Reading is slow, and gets slower as the file grows. If the number of records doubles, a lookup takes twice as long.
Full scan
A full scan reads every row of a table to find the rows that match a condition.
Example: SELECT * FROM users WHERE email = '[email protected]' with no index reads all rows and tests each one.
The cure, in the book's words, is an additional structure kept on the side that acts as a signpost.
Index
An index is an extra data structure, derived from the table, that lets the database find rows by the value of one or more columns without reading the whole table.
Example: an index on email maps each email to the place where its row is stored.
A worked example. A table has 10 million rows. Suppose the database can read 1 million rows per second in a scan (made up).
- Full scan: 10,000,000 ÷ 1,000,000 = 10 seconds for one lookup.
- Index lookup: the index is a tree (module 4) with a branching factor of several hundred. Three or four page reads reach the row. At 0.1 milliseconds per page read, 4 pages take 0.4 ms, about 25,000 times faster.
- At 200 lookups a second, the scan would need 2,000 seconds of work every second. That is impossible. The index needs 80 milliseconds of work every second.
The book states the central trade-off: well-chosen indexes speed up reads, but every index slows down writes, since the index must be updated each time data is written. This is why databases do not index everything by default. A designer must choose indexes using knowledge of the typical queries.
An index does not change the data. The book notes that adding or dropping an index changes only performance, not the contents.
Read it as
An index trades write time and space for read time. It pays off when reads outnumber writes on that column.
Check yourself:
- If a table doubles in size, what happens to the time of a full scan?
- Why does the book say that every index slows down writes?