Indexes: making lookups fast

A book has an index at the back

Earlier we saw how a database
finds the row it wants.
But when there is a lot of data,
scanning from start to end is slow.
It is just like hunting for a word
in a thick book from the first page.
So a book has an index at the back.
A page number sits beside each word,
so you can jump straight to that page.

Compare scanning the text from the start with jumping via the index. How many steps does each take?

Jumping with the index
found it in far fewer steps.
A database's index
is exactly this lookup.
It is a map built ahead of time
so data is found fast.
But indexes come in kinds.
Finding one exact value
and finding a range are different.

For an exact value, a hash index

Sometimes you want to find
just one exact value, like "Kim".
For that, a hash index is good.
A hash takes the name
and computes a slot number at once.
So without scanning row by row
it jumps to that slot in one step.
It is like knowing a locker number
and opening exactly that one.

Tap a name and the hash computes a slot number, jumping to that box in one step.

With just one name
it found the spot at once.
A hash index is this fast
at finding an exact value.
But it has a weak point.
A hash scatters the values,
so finding by a range,
like "from age 20 to 30",
it does poorly. Then another index is needed.

For a range, a tree index

Sometimes you want to find
by a range, like "from age 20 to 30".
For that, a tree index is good.
A tree index keeps the values
sorted from smallest to largest.
So once you find the start value
you can run right along beside it,
scanning the values in the range in order.
It is like a dictionary in alphabetical order.

Tap to set the range to find. The sorted tree index finds the start value and sweeps along the range.

Because it is sorted,
the range ran on smoothly to the side.
A hash pinpoints one spot,
a tree sweeps along a line.
So the right index depends
on what you look up often.
Lots of exact values, use a hash;
lots of ranges, use a tree.
But an index is not free.

An index is not free

An index has downsides too.
First, it takes extra space.
Since the lookup is written separately,
it uses that much more room.
Second, when the data changes
the index must change with it.
If you add or delete a row,
the lookup has to be updated to stay correct.
So making too many blindly is a loss.

Add or delete a row. Each time the data changes, the index updates too, and the space it uses grows.

Every time the data changed
the index moved along with it.
And it took up more and more space.
So we make an index
only for values we look up often.
We weigh the gain of speed
against the cost of space and updates
on a balance.
Chosen well, lookups get far faster.

Let's wrap up

Gathered on one line, it is this.
An index, like the back-of-book lookup,
is a map that lets you jump fast.
A hash index pinpoints one exact value
in a single step,
and a tree index, being sorted,
is good for sweeping a range.
But it uses extra space
and must be updated when the data changes.

Tap the key points in order to review. (back-of-book lookup -> hash for exact -> tree for range -> not free)

Now you know how an index
makes lookups fast.
We have seen how to find data quickly,
so next we turn to handling
data safely.
What happens when many people
touch the same data at once?
Let's work through that tricky problem
together in the next lesson.