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.

  • 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

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.
  • 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" 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. 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.

  • 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.
    – djechlin
    Jul 12 '13 at 20:10
  • @wfoster You just write all of those columns in the book index. Normally book indices only have one column, which is the topic. But if you wanted to index the topic and whether it's a noun or verb, you would write "aardvarks noun", "advertising noun", "advertising verb", etc... in the index.
    – user253751
    Mar 21 '15 at 2:20

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.

  • 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.


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.


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.

  • 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. Apr 9 '13 at 14:47
  • 1
    @wfoster: Some book indexes have indented subsections under each index.
    – Brian
    Apr 9 '13 at 15:13

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