How a database finds things inside it

At first, it scans row by row

Earlier we learned a database
is tidied into rows, like a table.
The simplest way to find something
inside it is this.
Start from the top row and go down,
one row at a time, checking each one.
When you meet a matching row, you stop.
Looking through from the start to the end
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 to reach it.

A value near the top
was found in just a few checks.
But a value near the bottom
was reached only after passing all above it.
If the value is at the very end,
you end up looking at every row.
When there are few rows, even this
is fast enough and causes no trouble.
So what happens when rows grow very many?

When data explodes, scanning gets slow

A real database
has an enormous number of rows.
Millions, even hundreds of millions, are common.
To find the last value, a full scan
must look at every one of those rows.
So if the rows double,
the number of checks doubles too.
As the rows grow,
the cost of finding grows right along.
This is the limit of a full scan.

Click to grow the row count. The bar shows how the checks to find the last value by full scan climb steeply.

The more you grow the count,
the longer the bar shot up.
What was trivial in a small table
becomes a heavy burden in a big one.
As long as you scan from start to end each time,
this cost cannot be avoided.
So is there a way to go straight
to the spot without scanning at all?
Luckily, there is a clever way.

Build an index and jump straight

Picture the index at the back of a book.
The words are sorted in order,
with the page number written beside each.
Instead of flipping the whole book,
you point to a word in the index
and open straight to that page.
A database can build such a list
ahead of time too.
We call it an index.

Tap a label in the sorted index. Without scanning the table, you jump straight to that row in a click or two.

Pointing to the index,
you went straight there without scanning the table.
Even a value at the very end
took just a click or two.
The secret is that the index
is kept neatly sorted ahead of time.
When it is sorted, you can quickly narrow
and point to roughly where it is.
The need to look at everything is gone.

Compare full scan and index

Let's put the two methods side by side
and compare them at the same count.
A full scan must check
as many times as there are rows.
An index uses the sorting
and finishes in very few checks.
Even at the same count, the result
is a world apart.
So for data you search often,
it pays to build an index.

Pick a count and run both searches. Compare side by side how many checks the full scan and the index each took to find the same value.

The more you grew the count,
the full scan bar shot up,
but the index bar stayed almost flat.
It is exactly this gap
that makes an index shine on big data.
Of course an index is not free.
It takes effort to build it ahead
and to keep it sorted.
Still, if you search often, it earns its keep.

Let's wrap up

Gathered on one line, it is this.
The simplest find is a full scan,
that is, scanning all rows from the start.
If the data is small, it is enough.
But once it explodes to hundreds of millions,
the cost of scanning climbs steeply.
So we build an index ahead of time
and jump straight there in a click or two.
For the same count, the 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 a full scan
to an index.
But how is that index
actually built?
Beyond a sorted list,
there are ways like a hash and a tree.
Let's follow those clever index structures
one by one in the next lessons.