12

Let's say a table with two columns has 100 quadrillion records. And I want to find a record that has column #2 equal something.

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.

How come the computer doesn't have to read the entire table when the column is indexed? How does it know what the result is without reading the table?

Improve this question
9
  • 18
    For the same reasons that you can find something in a book more quickly by looking in the index. For a more technical explanation, see en.wikipedia.org/wiki/B-tree
    – Robert Harvey
    Mar 20, 2015 at 20:36
  • 8
    You would need at most 57 lookups on a balanced binary tree to find an element out of 100 quadrillion records.
    – user40980
    Mar 20, 2015 at 22:07
  • 1
    You may be confusing doing a lookup with generating the index. The latter is going through the entire table but is done before your query.
    – JB King
    Mar 20, 2015 at 23:06
  • 1
    Sounds like you need a better intuitive example of what an index is
    – Izkata
    Mar 21, 2015 at 1:55
  • 1
    Even in an extremely pessimistic or random case binary searches are vastly less compute-intensive than iterative searches.
    – zxq9
    Mar 21, 2015 at 10:55

5 Answers 5

Reset to default
8

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.

enter image description here

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.

Unsorted Dictionary

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.

Sorted Dictionary

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:

  1. Start with 10,000 pages.
  2. Narrow it down to 5,000 pages.
  3. Then 2,500.
  4. 1,250
  5. 625
  6. 312 (we'll round down if there are any decimal places)
  7. 156
  8. 78
  9. 39
  10. 19
  11. 9
  12. 4
  13. 2
  14. 1

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.

B-Tree

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.

http://en.wikipedia.org/wiki/B-tree

Many database indexes are actually b-trees under the hood.

Pedantry

You said:

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.

Improve this answer
3
  • 1
    It's worth noting that B-trees and Binary Trees do not tend to refer to the same thing, but they do just about the same job. B-trees tend to not be binary trees, having more than 2 children per node, which is suited to the block-access reads we make from storage media (especially hard drives), as we can minimize the number of reads (relatively high latency)
    – VisualMelon
    Mar 21, 2015 at 8:36
  • 1
    but if it's not the computer has to read the entire table so it takes a long time I'd like to add that when you ADD the index, the database has to read the entire table... so in effect, you are doing the work AHEAD of when you need it. A zillion rows takes ~time to sort. Once sorted, it takes almost no time to traverse via methods mentioned above. The database itself is still unsorted. You can either use the index to find the row in the database or you can include extra data with the index.
    – WernerCD
    Mar 21, 2015 at 17:19
  • A minor correction, even if quadrillion is on the 1st page in the unindexed example, you need to read through the entire dictionary barring a special case like a TOP 1 (or a PK on an unindexed column)
    – Akash
    Mar 22, 2015 at 11:09
29

Basically, because an index is ordered, and when searching through an ordered data set, you don't have to search every item to find the element you're looking for; there are faster ways.

Discussing database indexing in detail can become very arcane very quickly, but the simplest way to answer this is that you can use techniques such as a binary search to find the element much more quickly, for reasons that should be intuitively obvious to anyone who's ever played the "I'm thinking of a number between 1 and 100" guessing game. You know how you can always guess the number within 7 guesses, not 100, if your guesses cut the size of the number of values to be "searched" in half each time? Databases do something very similar with indexing.

Improve this answer
2
  • That makes sense. But if the index is just ordered data(a ordered version of the table?), wouldn't it need to be rebuilt every time a new record is added? So after adding 1 record, the entire 100 quadrillion index would need to be reordered. Wouldn't that take a lot of time?
    – user1806244
    Mar 20, 2015 at 23:37
  • 20
    @user1806244 Some data structures(like B-trees) support efficient insertion of an arbitrary element(while maintaining the order).
    – kraskevich
    Mar 20, 2015 at 23:46
11

It is not that the computer knows what the result is without reading the table. It actually does quite a lot of work to find the result, but it is very fast, so it appears instantaneous to you. But yes, certainly, it does not read the entire table.

The way it works is implementation dependent, but a popular simple algorithm which serves for illustration purposes is binary search. It works similarly to how you find a word in a dictionary. Clearly, you don't read the entire dictionary every time you are looking for a word, do you?

What you do is that you open up the dictionary somewhere near the middle, (the algorithm will go to the exact middle, but that's just computers finding precision easier than approximation,) then you read just one word from that page, and see whether the word you are looking for comes before or after the word you read. If it comes before, you ignore the second half of the book, and focus only on the first half; if it comes after, you ignore the first half of the book, and you focus only on the second half: then you open up the page in the middle of the half that you are focusing on, read another word, see if your word comes before or after, and keep repeating these steps, until you have found the right page.

The reason why this works is because the words in the dictionary are sorted. If they were not sorted, we would have to go through the entire dictionary to find a word. What an index does on a database is that it provides a sorted view of the data, so that binary search can be used to find a value.

Using binary search you can find the right page for any word in a thousand-page dictionary with just 10 page lookups, and you can find the right page for any word in a 4-billion page dictionary with just 32 page lookups. As you see, it scales non-linearly, to our advantage, which is sweet.

Improve this answer
2
  • 7
    And, of course, in a real dictionary you'll never start at the middle if you're looking up "zygote". You make an educated guess that based on the distribution of letters, the word will be somewhat near the end, and use that as your initial guess. Computers can do this too, if enough information about the distribution of values is stored in the index.
    – hvd
    Mar 20, 2015 at 22:39
  • @hvd Not just the initial guess. If you have some knowledge about the distribution of the data you can use some form of interpolation to guess the next position and you can obtain O(log(log(n)) running time, which is exponentially better than binary search.
    – Bakuriu
    Mar 21, 2015 at 12:14
4

binary beans

You have a bunch of red jelly beans and a bunch of blue jelly beans.

You put the red jelly beans to the left and the blue ones to the right.

Now in the left-hand-side-world of red jelly beans you separate the ones that have no freckles to the left, the ones that have many freckles to the right.

So now you have something like

                    Root
              Reds/     \ Blues
           /     \
no freckles     freckles

You can keep branching your tree on different attributes and eventually if you want to find a red jelly bean with freckles you only have to take 2 steps, you don't have to pick up every single bean and check, put it back, and grab a new one until you reach a freckled red bean.

No matter how many jelly beans you have, finding a red one or a blue one is very simple.

A tree works a similar way (binary tree, B+tree, trie, etc.) by branching differences in data.

princess hotel

Indexing is just another way of exploiting patterns in data for efficiency.

Say you have a hotel and you put all the VIPs on the top floor, all the princesses on the 3rd floor, all the kings on the 2nd floor, etc.

Then you don't have to search through every room when you want to find a princess, you just go to the 3rd floor. It cuts down your seek time by a lot.

Now imagine doing that with your data.

An index is therefore not all the data, it's just a map that tells you where all the data is. If your data has some nice patterns that can be exploited, then your index will make your searching very efficient.

Improve this answer
3

Others have given more technical answers, so I will provide an analogy—and I realize this analogy may be a bit old fashioned:

How do you look for a number in a phone book?

Do you start at page one reading every name until you find it? Of course not, you split the huge thing in two, check where you're at then split it again and again, until you converge closer and closer to a page likely to contain the listing.

This is possible because we know the information in the phone book has been sorted alphabetically. Thus we are effectively performing the same steps as a binary-search algorithm.

Related concepts hold true for all books. When you open any book you'll often find an "index" within the first few pages that list relevant sections with pointers to data (page numbers).

Creating a database index for a particular table column is the same concept.

Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.