It sounds like this“Computers are so fast that scanning a file for a record is never a problem.”
Thinking computers read so fast that searching a file is never slow
Why it feels right
A computer does billions of things a second, so a thousand records is nothing and a million sounds only a little more. For the test data you start with, it is true: a search over a few hundred rows takes no time you can notice.
Why it’s wrong
A scan checks rows one by one, so the cost grows with the data. At a microsecond a row, a million rows take about half a second on average, and a hundred million take nearly a minute. An index jumps to the row in about twenty steps.
A worked example
A scan has to look at the rows one by one until it finds the one it wants. If it takes a microsecond to check a row, a million rows take a second to scan in the worst case, and half a second on average. A hundred million rows take about fifty seconds on average.
One search per second may be fine. A busy site wants a thousand a second, and then even a million rows means the machine cannot keep up, because every search is reading the whole file.
An index is a sorted structure on the side, like the index in a book. It lets the database find a row in about 20 steps for a million rows, because each step halves what is left: 2 to the power 20 is just over a million. The same 20 steps find one row in a billion with about 30. Databases build and maintain indexes for you, which is the main reason they stay fast as the data grows.
How to catch yourself
- You search a big file line by line and call it good enough.
- You test with a few rows and assume it will scale.
- You think the problem will go away with a faster computer.
What to hold instead
A scan's cost grows with the number of rows, so it gets slow as data grows. An index finds a row in a few steps, about 20 for a million rows, because it halves the search each time.
Where you’ll meet it
- Wondering why a page slows down as data grows.
- Choosing how to store a growing list of records.
- Understanding why databases use indexes.
Questions people ask
- What is a database index?
- A sorted structure kept alongside the data, which lets the database find a row by its key in a handful of steps instead of reading every row. It is like the index at the back of a book.
- Why does searching get slower as data grows?
- Without an index the program has to check rows one by one, so twice as many rows take twice as long. With an index the cost grows only slowly, because each step halves what is left.