Database Indexes Explained

Card Catalog Index

A database index allows a query to efficiently retrieve data from a database.  Indexes are related to specific tables and consist of one or more keys.  A table can have more than one index built from it.  The keys are a fancy term for the values we want to look up in the index.  The keys are based on the tables’ columns.  By comparing keys to the index it is possible to find one or more database records with the same value.

Since an index drastically speeds up data retrieval, it is essential the correct indexes are defined for each table.  Missing indexes won’t be noticed for small databases, but rest assured, once your tables grow in size, queries will take much longer.

The power of a Database Index

I was once working on a database where a series of operations took about eight days to complete.  By looking at the longest running queries and running them through a query plan generator we realized the database could benefit from a new index.  The optimizer estimated the query cost would drop from 300,000 operations to 30!  We implemented the index and took the entire operation from eight days to two hours.  Needless to say, we were very happy to get the performance boost.

What about an Example?

For this example consider the index in the back of a book.  It’s pretty simple to use.  Just scan for the subject you’re interested in, note, and flip to those pages in your book.

The keys for this index are the subject words we reference.  The index entries consist of the key and page number.  The keys are in alphabetical order, which makes really easy for us to scan the index, find an entry, note the pages, and then flip the book to the correct pages.

Consider an alternative.  A book with no index may have the subject words listed at the bottom of each page.  With this type of system, to find a subject you’re interested in you would have to flip through the entire book.  This makes looking up subjects really slow!

Only until you got to the very end of the book would you know you have seen every page about the subject.

The power of the index is that is allows you to more or less directly access the book’s pages you’re interested in seeing.  Practically speaking, this saves hours of page flipping!

Deck of Cards

Consider that you have a deck of 52 cards: four suits, Ace through King.  If the deck is shuffled into random order, and I asked you to pick out the 8 of hearts, to do so you would individually flip through each card until you found it.  On average you would have to go through half the deck, which is 26 cards.

Example of a database index using cards

Now, instead, consider that we separated the cards into four piles by suit, each pile randomly shuffled.  Now if I asked you to pick out the 8 of hearts you would first select the hearts pile, which would take on average two to find, and then flip through the 13 cards. On average if would take seven flips to find, thus nine total.  This is seventeen flips (26-9) faster than just scanning the whole deck.

We could take it one step further and split the individual piles into two groups (one Ace through 6, the other 7 through King).  In this case the average search would decrease to 6.

This is the power of an index.  By segregating and sorting our data on keys, we can use a piling method to drastically reduce the number of flips it takes to find our data.

B+ Tree Indexes are used by Databases

The structure that is used to store a database index is called a B+ Tree.  A B+ Tree works similar to the card sorting strategy we talked about earlier.  In a B+ Tree the key values are separated into many smaller piles.  As the name implies, the piles, technically called nodes, are connected in tree like fashion.  What makes a B+ Tree sizzle, is that for each pile in the tree, it is very easy and quick to do a comparison with the value you are finding and branch on to the next pile.  Each pile drastically reduces the number of items you need to scan; actually exponentially so.

In this way, by walking down the nodes, doing comparisons along the way we can avoid scanning thousands of records, in just a few easy node scans.  Hopefully this diagram helps to illustrate the idea…

SQL Index

In the example above consider you need to retrieve the record corresponding to the key value 15.  To do so the following comparisons are made:

  1.  It determined that 15 is less than 40, so we traverse the “To Values < 40” branch.
  2. Since 15 is greater than 10, but less than 30, we traverse the “To Values >= 10 and < 16 branch”

With a B+ Tree Structure it is possible to have thousands of records represented in a tree that has relatively few levels within its branches.  As the number of lookups are directly related to the height of the tree, it is imperative to ensure all the branches are of equal height.  This spreads out the data across the entire tree, making it more efficient to look up data within any range.

Since data is constantly updated in a database, it’s important for the B+ Tree to keep its balance.  Each time records are added, removed, or keys updates, special algorithms shift data and key values from block to block to ensure no one part of the tree is more than one level higher than the other.

Truly studying a B+ Tree is very technical and mathematical.  If you are interested in the gritty detail, I would start with the Wikipedia article.  I an actual example, each node (dark blue) would contain many key values (light blue).  In fact each node is the size of a block of disk, which is traditionally the smallest amount of data that can be read from a hard drive.

This is a pretty complicated subject.  I hope I’ve made it easy to understand.  I would really like to know.  Please leave a comment.

Remember!  I want to remind you all that if you have other questions you want answered, then post a comment or tweet me.  I’m here to help you.

Kris Wenzel

Kris Wenzel has been working with databases over the past 28 years as a developer, analyst, and DBA.He has a BSE in Computer Engineering from the University of Michigan and a MBA from the University of Notre Dame.Kris has written hundreds of blog articles and many online courses. He loves helping others learn SQL.

  • Alan says:

    Thank you so much for the example with the book index! It really helped solidify the concept of indexes in my mind. It’s a lot clearer now.

  • Justin Time says:

    Since 16 is greater than 10, but less than 30, we traverse the “To Values >= 10 and < 16 branch”

    … 16 is not less than 16, this would fail.

    • Thanks for finding the error in the text. I corrected the scenario to finding 15 rather than 16. That works better with the example.

      • Greg says:

        Good explanation all around, thanks. I don’t understand the diagram though. Why do 16 and 30 show up on the node with the label =10? I’d think neither would be on that node. Where is 15 found and its corresponding record returned? Would be nice to have a little narrative on that to wrap up the example.

        • Greg says:

          My greater than and less than symbols did not show up. My text should say “…on the node with the label greater than or equal to 10 and less than 16”

  • Venkatesh says:

    Hi Kris,

    I really appreciate for your efforts and valuable time doing such a great Hard work regarding SQL Server and Thank you so much for educating us.

    Can you please have a post in Ranking Functions and Cursors,Derived tables if possible.

    Thanks in Advance.

  • Sandeep Chitta says:

    Very clearly explained!

  • Mehmet says:

    Thank you very much for this great explained article.

  • Angelique says:

    Thanks – I’ve been trying to get my head around database indexing and now it’s all 100% clear. The card sorting is a great example!

  • Michael Nabil says:

    Thanks for the explanation and example , the article is very useful , examples which you have used served the subject well

  • Anonymous says:

    Who wrote this? Give this person a cookie.

  • Anonymous says:

    Very well explained. I am just wondering about the multikey indexes. How the B+ tree is maintained for them. I was trying out a few multikey indexes in mongodb, so could you please explain more about the multikey indexes.
    Thanks :)

  • Braidy says:

    Thanks for this article! The cards example is different than anything I have heard before; it really makes sense! Question: In the diagram, are the light blue boxes (the key values) representing indices added to the database? I understand the logic behind the flow of finding the correct number, but am still unsure where the index/indices are represented. I would love to dive more into what the code looks like directing the query to the index. Is that something that would be written in ActiveRecord somewhere?

  • Thanks!

    I’m glad you like the card idea. Yes, the blue boxes represent index entries.

  • Daniel Nicholas says:

    Our developer put in several new indexes on various tables and brought a 4.5 hour batch file down to 45 minutes. I need to see how that’s done in MS SQL so I can work the same magic.

  • Emil Johansen says:

    Awesome explanation. Thanks a bunch!
    As others have pointed out the book analogy is spot on.

    After reading stories like Daniel’s “Our developer put in several new indexes on various tables and brought a 4.5 hour batch file down to 45 minutes.” it would be awesome to see a real life example of index engineering.


    • When I’m working with slow queries, I usually look to see if the query is using indexes and if not why.

      I use the query plan to help with this.

      When the database is yours, don’t trust the designers to have thought out the indexes. You’ll be surprised that only created those the primary key, leaving other queries hanging in the wind… :)

  • Yash says:

    Good explanation. Thanks.

  • Akanksha Singh says:

    Loved it. Thank you!

  • Marcus says:

    Hey Kris,

    thanks a lot for this article. It is very practical and makes clear to me how indexing in databases work. Very well written!

    There is only one thing I don’t get in the last illustration. The path says “To values >= 10 And =10 And < 31"?

    Thanks again for your work and explanation.


  • Petr says:

    Thank you for this article – very helpful to give the whole “index” subject a meaning that actually makes sense! Both examples are great, actually both put into picture explain it much clearer than giving out only one.

  • >