How does a database find data
If a library has only ten books, you can scan them one by one and find what you want quickly. But what if it has millions of books? Checking them one at a time would take all day. A database is no different. At first it finds things by scanning the whole table row by row, but once the data grows to hundreds of millions of records, that becomes far too slow. So it builds an index in advance and jumps straight to the right spot.
At first, it scans row by row
In the last lesson we said a database organizes information into rows, like a table. The simplest way to find something in it is to start at the top row and go down one row at a time, checking each one.
When you reach a matching row, you stop. Going through from start to end in order like this is called a full scan.
Tap the value you want to find. It scans down one cell at a time and counts how many it checked before reaching it.
A value near the top was found in just a few checks, while a value near the bottom was reached only after passing everything above it. If the value is at the very end, you end up looking at every row.
When there are only a few rows, this is fast enough and causes no trouble. So what happens when the rows become very many?
When data grows, scanning slows down
A real database has an enormous number of rows; millions or even hundreds of millions are common. To find the last value with a full scan, it has to look at every one of those rows.
So if the number of rows doubles, the number of checks doubles too. The cost of finding grows right along with the number of rows: that is the limit of a full scan.
Tap to increase the number of records. The bar shows how the checks needed to find the last value by full scan climb steeply.
The more you increased the count, the longer the bar grew. Something trivial in a small table becomes a heavy burden in a large one.
As long as you scan from start to end every time, this cost cannot be avoided. Is there a way to go straight to the spot without scanning? Luckily, there is a clever one.
Building an index to jump straight there
Picture the index at the back of a book. The words are sorted alphabetically, with page numbers written beside them. Instead of leafing through the whole book, you find the word in the index and open straight to that page.
A database can build a list like this in advance too. It is called an index.
Tap a label in the sorted index. Without scanning the table, you jump straight to that row in one or two steps.
Using the index, you went straight there without scanning the table. Even a value at the very end took only one or two steps.
The secret is that the index is kept neatly sorted in advance. In a sorted list you can look at the middle, decide whether the value you want is in the front half or the back half, throw away the other half, and repeat. Done that way, even among a million items you find the one you want in about twenty steps.
Comparing full scan and index
Let's set the two methods side by side and compare them at the same number of records. A full scan has to check as many times as there are rows. An index uses the sorting and finishes in very few checks.
Even with the same number of records, the results are worlds apart. So for fields you search often, building an index pays off.
Choose a count and run both searches. Compare side by side how many checks the full scan and the index took to find the same value.
The more you increased the count, the more the full-scan bar shot up, while the index bar stayed almost flat. It is exactly this gap that makes indexes shine on large data.
Of course an index is not free. It needs extra space, and every time a new row comes in, the index has to be updated so it stays sorted. Still, for fields you search often, it is well worth it.
Summary
In short: the simplest way to find something is a full scan, going through every row from the start. With little data, that is enough.
But once the data grows to hundreds of millions of records, the cost of scanning climbs steeply. So an index is built in advance, and you jump straight there in one or two steps. For the same number of records, an index looks at far fewer.
Tap the key points in order to review. (scan row by row → data explodes → jump with an index → full scan vs index)
Now you know why a database moves from full scans to indexes. So how is an index actually built?
Besides a sorted list, there are methods such as hashing and trees. The next lesson looks first at hashing, which calculates a spot straight from a single label.