What is a database index
Say you are looking for one word in a thick book. Reading from the first page to the last would take far too long. That is why books have an index at the back: each word is listed with a page number, so you can turn straight to that page. A database is the same. When there is a lot of data, scanning from the start is too slow, so it builds a lookup list called an index in advance.
Books have an index at the back
In the previous lessons we saw how a database finds the row it wants, and how hashing and balanced trees find things quickly. Now it is time to see how those tools are used inside a database.
When there is a great deal of data, scanning from start to end is slow, just like hunting for a word in a thick book from the first page. That is why books have an index at the back, with page numbers written next to the words.
Tap scan the text from the start and jump with the index to compare. It counts how many steps each takes.
Jumping with the index found the word in far fewer steps. A database index is exactly this kind of lookup list: you choose one column of a table and write down, in advance, each value paired with the position of its row.
But there are different kinds of index, because finding one exact value and finding a range call for different methods.
A hash index for exact values
Sometimes you want to find exactly one value, such as "Kim Chulsoo." In that case, a hash index works well.
The hashing we saw earlier takes the name and calculates the spot number straight away, so instead of scanning row after row, you jump to that spot in one go. It is like remembering your locker number and opening that locker directly.
Tap a name, and the hash calculates its spot number and jumps there in one step.
One name led straight to its spot. A hash index is very fast at finding an exact value like this.
But it has a weak point. Because hashing scatters values regardless of their size, it cannot search a range such as "ages 20 to 30." For that, you need a different index.
A tree index for ranges
Sometimes you want to search a range, such as "ages 20 to 30." In that case, a tree index works well. A tree index is built from a balanced tree like the one in the last lesson, so it keeps the values sorted from smallest to largest.
Once you find the starting value, you can sweep along from there and go through the values in the range in order, much like a dictionary arranged alphabetically. In fact, most databases use this tree index by default.
Tap to set the range to search. The sorted tree index finds the starting value and sweeps through the range.
Because the values are sorted, the range ran on side by side. A hash pinpoints a single spot, while a tree sweeps along a line.
So the right index depends on what you search for most often: a hash if you look up exact values a lot, a tree if you search ranges a lot. But an index is not free.
An index is not free
An index does not only bring benefits. First, it takes up extra space: because the lookup list is written down separately, it needs that much more storage.
Second, when the data changes, the index has to be updated too. Every time a row is added or deleted, the lookup list must be fixed as well, so writing becomes slower by that much. That is why creating indexes without thinking can do more harm than good.
Add or delete a row. Each time the data changes, the index is updated to match, and the space it uses grows.
Each time you changed the data, the index moved along with it and took up more and more space. That is why indexes are created only on the columns you search often.
You weigh the benefit of speed against the cost of space and of keeping the index up to date. Choose well, and searching becomes much faster.
Summary
In short: an index is a lookup list, like the index at the back of a book, that lets you jump straight to the spot you want. A hash index pinpoints a single exact value in one step, and a tree index, being sorted, is good for sweeping through a range.
But indexes take up extra space and have to be updated whenever the data changes. That is why they are created only on the columns you search often.
Tap the key points in order to review. (the index in a book → hash for exact values → tree for ranges → not free)
Now you know how an index makes searching fast. So far we have handled data lined up in rows of a table.
But sometimes the connections between pieces of data matter most, as with friendships or subway lines. The next lesson introduces data stored as points joined by lines: the graph.