Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Setup: Suppose you are teaching an introduction to Databases class, the students are CS students that have a working knowledge of tree structures, how they can speed up searches, and have probably implemented a few in their lifetime.

Question: How would you describe the way in which a database uses indexes to search a table for a set of keys? What structure is a database index most similar to?

Bonus: How does someone write a SQL query where clause to take advantage of the searching capability of the index they design on a given table?

Answers should correspond to all database products as a whole. I'm looking for general tips which allow faster searching on all databases. Plain english descriptions please, no code, Big O searching descriptions are fine. This question might be too specific for this site, I considered asking on StackExchange but since I'm requesting a plain english description of a broad concept I thought this site would be Ok.

share|improve this question
1  
The bonus part would seem to rely on implementation details... right? –  Izkata Apr 9 '13 at 14:34
    
I'm looking for something like, "Your first where clause should narrow down the possible results (i.e., cutting out half of the tree searching)" –  wfoster Apr 9 '13 at 14:36
7  
What are you missing when you look at en.wikipedia.org/wiki/Database_index? (This is not meant as a rethorical question, it's meant literallly). –  Thomas Apr 9 '13 at 14:37
1  
And here: stackoverflow.com/questions/1108/… –  Thomas Apr 9 '13 at 14:42
    
@Thomas that stackoverflow one is good! Maybe this question ought to get closed. –  wfoster Apr 9 '13 at 14:52

6 Answers 6

up vote 30 down vote accepted

Database indexes are modeled after textbook indexes, then made more efficient:

Textbook index

The non-indented parts are the primary part you're searching on, and the indented part underneath some of them further identifies specific topics. Each indentation level is similar to another column on the index.

Taking advantage of indexes is (I think) partially implementation-specific. For example:

  • If you query column food for "chicken", the index will be utilized.
  • For "chick%", I would say it depends on the database/type of index, although all the ones I know of will still use it.
  • Similar rules apply for querying columns food and drink for "chicken" and "water": First it limits results based on the first column in the index, then the second - just as if you used the outer index, then the indented index, in a textbook.
  • Likewise for "chik%" and "wat%"
  • However, "%ken" cannot be searched in an index in the databases I know of, because they index from the front of the word, not the back - same as textbook indexes. So the database will have to scan the whole table.
share|improve this answer
    
Exactly what I'm looking for, thanks for the expansion of your answer. –  wfoster Apr 9 '13 at 15:00
4  
@wfoster: I find it hard to believe that there would be any value in this answer to students who really have "a working knowledge of tree structures, how they can speed up searches, and have probably implemented a few" –  Michael Borgwardt Apr 9 '13 at 15:16
    
OTOH, textbook index does not cover all the data in the textbook, only arbitrary chosen parts. –  vartec Apr 9 '13 at 15:52
1  
Regarding your last point, you can use a k-gram index or similar. I don't know how common that sort of technique is in off-the-shelf database indexes though. –  Karl Bielefeldt Apr 9 '13 at 16:41

I mean, it's most similar to an index. Instead of rummaging through the entire book, you look it up in the index and find the page it's on.

The magic works because the index is organized in an easier-to-search way than the book, i.e. alphabetically.

share|improve this answer
    
What about an index comprised of multiple columns? How does this relate to an index in a book? Would this be like an index of indexes? –  wfoster Apr 9 '13 at 14:37
    
@wfoster I feel like at this point it's better just to explain that as a generalization. "A weakness of a dictionary is it's really hard to look up all the words starting with A that are nouns." But you can do this with multiple-column indices. –  AAA Jul 12 '13 at 20:10

Take a book, any technical book.

Go to the end - where there is an... Index.

Why is it there? Same reason for the DB. So you don't have to search through a whole book for a specific entry.

Think about a dictionary. It is an index of words, sorted alphabetically.

share|improve this answer
    
And also, every time you write a new entry into the dictionary, the index has to be updated. –  nbv4 Apr 9 '13 at 15:03

Assuming that the audience really has "a working knowledge of tree structures, how they can speed up searches" (and thus "plain English" is really not what they need):

A DB index is a B-Tree using the values of one or more columns (tuples in the case of multiple columns) as keys and references to the corresponding records as values.

A B-Tree is a search tree with a very high branching degree that is optimized for data locality and thus still performs well when it's too large to be kept in RAM (and random access becomes extremely expensive).

From this, it should be clear that an index can only help speed up a query when the WHERE clause involves the columns of the index either in an equality condition, a greater/smaller condition or by specicfying a prefix (which uses the columns in the sam order they appear in the index, for multicolumn indexes) - because those are the operations supported by a search tree.

share|improve this answer

It doesn't have to be a b-tree, but many databases do use b-trees to implement their databases. Anything you want to know about how an index works, and what its performance characteristics are, you can find out by studying b-trees.

share|improve this answer

From Use the Index Luke:

A database index is, after all, very much like the index at the end of a book: it occupies its own space, it is highly redundant, and it refers to the actual information stored in a different place.

share|improve this answer
    
What about an index comprised of multiple columns? How does this relate to an index in a book? Would this be like an index of indexes? –  wfoster Apr 9 '13 at 14:37
4  
@wfoster: a metaphor only goes so far, if you try to stretch it, it breaks. –  Joachim Sauer Apr 9 '13 at 14:47
1  
@wfoster: Some book indexes have indented subsections under each index. –  Brian Apr 9 '13 at 15:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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