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.
Table of contents
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.
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…
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:
- It determined that 15 is less than 40, so we traverse the “To Values < 40” branch.
- 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 >>
Thank you this is very informative.
Thank you for the explanation there!
Thank you for the informative blog, now I know and understand indexing.
Great introductory explanation, thanks so much! This is exactly what I needed.
I’m glad I was able to help. Thanks for reading the blog.
Thank you :) very well explained and now I know
It’s really well explained and more clear in my mind now.
Very easy to understand. Straight to the point, and not overly technical. Thank you very much.
Well explained, thank you.
This is the very best explanation I’ve read on this topic
Because you asked – yes, you managed to explain it in a very clear way! Thank you :)
I love to be you student.
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.
Got it, thanks!
Very nice, helped me understand indexes a bit more! Thanks!
This was a very concise and easy to digest blog post!
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)
nice post, thank you
Thank you, it’s a nice post
Nice post. Simple to understand for any beginner. Thanks Kris
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
Very understandable article on the subject! This really helped me – thanks! :)
I was looking for a high-level explanation of how indexes work and this article was very helpful!
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?
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 :)
Thanks so much!!! Great explanation.
Hahaha that was a nice pun. B+ trees even though far from heaps do have a similar structure from outside.
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.
My understanding is that the Oracle CONNECT BY clause has since been replaced by with the functions found withing Recursive Common Table Expressions.
Thanks Kris. You have explained it in a very easy way. Keep it up!
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.
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
Thank you for the beautiful example. Great examples.
You’re welcome! I’m glad you liked the site and examples.
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.
So much informative content, God bless you Sir…
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.
Loved it. Thank you!
I’m glad you liked the example. If there are other topics that you find vexing, let me know. I can write another article.
Good explanation. Thanks.
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… :)
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.
I’m glad you like the card idea. Yes, the blue boxes represent index entries.
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?
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.
Who wrote this? Give this person a cookie.
Thanks for the explanation and example , the article is very useful , examples which you have used served the subject well
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!
Thank you very much for this great explained article.
Very clearly explained!
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.
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.
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.
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”
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.
I’m glad the article helped out. Are there other DB related areas that you would like see articles about?
Let me know.
Yes indeed, that was the ice breaker, the aha moment. Great article, thanks.