Do You Want to Learn SQL?

Take our free eight day course, where I'll teach you in simple to understand English all you need to get started learning SQL.


Free Beginners SQL Course!

Database Indexes Explained




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.

It is essential the correct indexes are defined for each table, since an index drastically speeds up data retrieval.  You won’t notice missing indexes for small databases. But you’ll notice your queries taking longer for larger databases.

The power of Database Indexes

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 a performance boost.

Indexing within a Book

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 to this index are the subject words we reference.  The index entries consist of the key and page numbers.  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 it allows you to more or less direct access to the book’s pages you’re interested in seeing.  Practically speaking, this saves hours of page-flipping!

Indexing Example Using a Deck of Cards

Consider that you have a deck of 52 cards: four suits, Ace through King.  If the deck is shuffled into a 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 it 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+ Trees – Index Structures 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 a 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”

Power of B+ Tree Structures

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 is 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 a 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.

Read More: Database Normalization – in Easy to Understand English >>

72 responses to “Database Indexes Explained”
  1. jeanne

    Thank you this is very informative.

  2. Somit

    Thank you for the explanation there!

  3. […] Database Indexes Explained […]

  4. […] to be able to write SQL queries, use the explain and understand how they work and why you need index‘s. Well, and look at the heaps of […]

  5. […] then as you make changes it keeps making updates to those indexes. Here’s a great article on database indexing. But in short, indexing is just a way for a system or database to quickly access data on the fly, […]

  6. phumelele

    Thank you for the informative blog, now I know and understand indexing.

  7. Jekaterina

    Great introductory explanation, thanks so much! This is exactly what I needed.

    1. I’m glad I was able to help. Thanks for reading the blog.

  8. Luciana Aguiar Corrêa

    Great explanation!!

  9. Dey

    Thank you :) very well explained and now I know

  10. Dany

    It’s really well explained and more clear in my mind now.

  11. Cjoe

    Very easy to understand. Straight to the point, and not overly technical. Thank you very much.

  12. Bubba

    Well explained, thank you.

  13. Israel

    This is the very best explanation I’ve read on this topic

  14. Amit

    Because you asked – yes, you managed to explain it in a very clear way! Thank you :)

  15. Daniel agbuke

    I love to be you student.

  16. Julie

    THANK YOU!! I LOVE examples that are common and easy to relate and understand. The book index and deck of cards combined with the visual “tree” was awesome.

  17. Got it, thanks!

  18. Ola

    Very nice, helped me understand indexes a bit more! Thanks!

  19. derek

    This was a very concise and easy to digest blog post!

    1. Thanks!

  20. Manjunath

    Thanks Kris. Easiest to understand yet crisp and clear write up and helped me.
    Could you please share your thoughts on db schema designs, do’s/don’ts, must have tools (especially opensource)

  21. Yuki

    nice post, thank you

  22. Muhammed Said Cakir

    Thank you, it’s a nice post

  23. Vijay

    Nice post. Simple to understand for any beginner. Thanks Kris

  24. Mike

    Awesome post, thank you very much, Kris. I’m doing Imtiaz Ahmad’s Intro to SQL course, and we just got into indexing. It seems like a critical topic to understand

  25. Joseph Simpson

    Great post!

  26. Bridget

    Very understandable article on the subject! This really helped me – thanks! :)

  27. Karthik

    I was looking for a high-level explanation of how indexes work and this article was very helpful!

  28. Guest

    I was looking for a article with a simple, clear description of why indexing is important and how they work … this is definitely what I was looking for. Now, do you have any advice on not creating too many indexes (especially unnecessary), as maintenance can negatively impact performance?

  29. Angie

    Thank you! Great explanation. I am converting from relational to big data indexed database as an analyst and I am trying to gain a deeper understanding. Feel like I am back at data 101 :)

  30. Serena

    Thanks so much!!! Great explanation.

    1. My pleasure!

      1. asd

  31. Deanna

    Thanks heaps!

    1. Mehul Garg

      Hahaha that was a nice pun. B+ trees even though far from heaps do have a similar structure from outside.

  32. Mano

    Hi Kris. Nicely done to let us understand indexes easily.
    It would be much helpful if you could help on connect_by and level used in (hierarchical) queries. I do not find a clear explanation on this anywhere.

    Thanks in advance.

    1. Hi,

      My understanding is that the Oracle CONNECT BY clause has since been replaced by with the functions found withing Recursive Common Table Expressions.

  33. Ahmed Shihab

    Thank you!!!

    1. My pleasure!

  34. Keshav

    Thanks Kris. You have explained it in a very easy way. Keep it up!

    1. Thank Keshav, If there are other topics that you would like to know about, please let me know. I’ll do my best to explain them to you.


  35. Faizer

    Thanks Kris..It is really helpful to understand the concepts in beginner level..can you guide the pathway to go into deeper and get thorough in indexes

  36. Aziz Jivani

    Thank you for the beautiful example. Great examples.

    1. You’re welcome! I’m glad you liked the site and examples.

  37. Petr

    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.

    1. Sharif Hossain

      So much informative content, God bless you Sir…

  38. Marcus

    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.


  39. Akanksha Singh

    Loved it. Thank you!

    1. Hi Ankanksha,

      I’m glad you liked the example. If there are other topics that you find vexing, let me know. I can write another article.


  40. Yash

    Good explanation. Thanks.

  41. Emil Johansen

    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.


    1. 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… :)

  42. Daniel Nicholas

    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.

  43. Thanks!

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

  44. Braidy

    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?

  45. Anonymous

    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 :)

  46. Anonymous

    Who wrote this? Give this person a cookie.

  47. Michael Nabil

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

  48. Angelique

    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!

  49. Mehmet

    Thank you very much for this great explained article.

  50. Sandeep Chitta

    Very clearly explained!

    1. Thanks!

  51. Venkatesh

    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.

  52. Justin Time

    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.

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

      1. Greg

        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.

        1. Greg

          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”

  53. Alan

    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.

    1. I’m glad the article helped out. Are there other DB related areas that you would like see articles about?

      Let me know.

    2. Emmanuel Evbuomwan

      Yes indeed, that was the ice breaker, the aha moment. Great article, thanks.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

More from the blog

MySQL PostgreSQL SQLite SQL Server