The "index" of a book is not a great metaphor, IMO. A better metaphor is trying to look up a word in a dictionary. Imagine that you want to look up a word in the Oxford English Dictionary (OED), which is a massive dictionary that comprises multiple volumes.
The words in the OED are sorted alphabetically, of course, to make it easy to look up a word. But what if the words were not sorted? What if they were added to the dictionary in random order?
Let's do a thought experiment where we want to look up the word "quadrillion" in this hypothetical, unsorted dictionary, and compare that to looking up the same word in a normal, sorted dictionary.
Let's assume the dictionary has 10,000 pages and there is exactly 1 word on each page.
To find the word "quadrillion" in a dictionary that isn't alphabetically sorted, you would need to start at one end (say page 1). If the word on page 1 is "quadrillion", then congratulations, you're done! Of course, since the dictionary is random, odds are that "quadrillion" is not on the first page, which means you need to check the next page, and then the page after that, etc. until you find "quadrillion".
How many pages do you need to look at (in the worst case) to find the word "quadrillion"? Well, potentially all of them... "quadrillion" could by chance be the very last word in the dictionary, so you'd need to look at all 10,000 pages in the worst case scenario.
This would be an excruciatingly tedious task, and its analogous to a database looking at every single row of a table.
Fortunately, dictionaries are sorted alphabetically, which is why we can look up a word in minutes, not weeks. We all know how to find a word in the dictionary, but pretend for a moment that you had to write an algorithm to do it. How would that algorithm work?
- Open the dictionary up to the middle page (5,000) and read the word on that page: "mellifluous".
- This word is higher (alphabetically) than quadrillion, so we know that quadrillion must be somewhere between pages 5,001 and 10,000.
- Next, we go to to page 7,500, which is the midpoint of 5,001 and 10,000.
- The word on this page is "sacrosanct". This is lower than "quadrillion", so now we know quadrillion is between pages 5,001 and 7,500.
- Now we flip to 6,250, which is the midpoint of 5,001 and 7,500.
- We can repeat this process of dividing the remaining pages in half and figuring out which half the word is in until, eventually, we'll open to the page that contains "quadrillion", and we're done!
How efficient is this compared to the unsorted dictionary algorithm? We still probably had to look at a lot of pages, right?
We can compute the efficiency by noticing that at each step we are eliminating half of the pages. So by counting the number of pages that are left, we can count how many steps it takes to get to any word:
- Start with 10,000 pages.
- Narrow it down to 5,000 pages.
- Then 2,500.
- 312 (we'll round down if there are any decimal places)
By the time we get to 1 page remaining, we know with certainty that we've either found the word we were looking for, or it doesn't exist in the dictionary. We can count the number of steps and see that we only had to look at 14 pages — in the worst case — to find any word. That's a huge improvement over looking at all 10,000 pages!
More generally, the worst-case lookup time is
log2(n), where n is the number of pages in the dictionary. (Try computing it yourself to see if your answer agrees with mine.) This is a very desirable property for an algorithm, because the
log function grows very slowly. If the dictionary had a billion pages instead of 10k, it would still only take 30 steps to find any given word in it! (Again, try computing it yourself.)
This is analogous to the database using an index to find a row in a table.
A B-tree is a data structure that allows us to use an algorithm similar to the one we use to find a word in a sorted dictionary. This is a very important data structure in fundamental computer science.
Many database indexes are actually b-trees under the hood.
If column #2 is indexed it returns the result immediately, but if it's not the computer has to read the entire table so it takes a long time
The "immediately" part isn't really true. It's still an iterative algorithm that takes longer to run the more items that need to be looked at. It's such an efficient algorithm that the results might feel immediate, but it's important to note that it's not a constant time algorithm.