How do database indexes work? And, how do indexes help? Provide a tutorial on database indexes.

Let’s start out our tutorial and explanation of why you would need a database index by going through a very simple example. Suppose that we have a database table called Employee with three columns – Employee_Name, Employee_Age, and Employee_Address. Assume that the Employee table has thousands of rows.

Now, let’s say that we want to run a query to find all the details of any employees who are named ‘Jesus’? So, we decide to run a simple query like this:

SELECT * FROM Employee 
WHERE Employee_Name = 'Jesus'

What would happen without an index on the table?

Once we run that query, what exactly goes on behind the scenes to find employees who are named Jesus? Well, the database software would literally have to look at every single row in the Employee table to see if the Employee_Name for that row is ‘Jesus’. And, because we want every row with the name ‘Jesus’ inside it, we can not just stop looking once we find just one row with the name ‘Jesus’, because there could be other rows with the name Jesus. So, every row up until the last row must be searched – which means thousands of rows in this scenario will have to be examined by the database to find the rows with the name ‘Jesus’. This is what is called a full table scan.

How a database index can help performance

You might be thinking that doing a full table scan sounds inefficient for something so simple – shouldn’t software be smarter? It’s almost like looking through the entire table with the human eye – very slow and not at all sleek. But, as you probably guessed by the title of this article, this is where indexes can help a great deal. The whole point of having an index is to speed up search queries by essentially cutting down the number of records/rows in a table that need to be examined.

What is an index?

So, what is an index? Well, an index is a data structure (most commonly a B- tree) that stores the values for a specific column in a table. An index is created on a column of a table. So, the key points to remember are that an index consists of column values from one table, and that those values are stored in a data structure. The index is a data structure – remember that.

Subscribe to our newsletter for more free interview questions.

What kind of data structure is an index?

B- trees are the most commonly used data structures for indexes. The reason B- trees are the most popular data structure for indexes is due to the fact that they are time efficient – because look-ups, deletions, and insertions can all be done in logarithmic time. And, another major reason B- trees are more commonly used is because the data that is stored inside the B- tree can be sorted. The RDBMS typically determines which data structure is actually used for an index. But, in some scenarios with certain RDBMS’s, you can actually specify which data structure you want your database to use when you create the index itself.

How does a hash table index work?

Hash tables are another data structure that you may see being used as indexes – these indexes are commonly referred to as hash indexes. The reason hash indexes are used is because hash tables are extremely efficient when it comes to just looking up values. So, queries that compare for equality to a string can retrieve values very fast if they use a hash index. For instance, the query we discussed earlier (SELECT * FROM Employee WHERE Employee_Name = ‘Jesus’) could benefit from a hash index created on the Employee_Name column. The way a hash index would work is that the column value will be the key into the hash table and the actual value mapped to that key would just be a pointer to the row data in the table. Since a hash table is basically an associative array, a typical entry would look something like “Jesus => 0x28939″, where 0x28939 is a reference to the table row where Jesus is stored in memory. Looking up a value like “Jesus” in a hash table index and getting back a reference to the row in memory is obviously a lot faster than scanning the table to find all the rows with a value of “Jesus” in the Employee_Name column.

The disadvantages of a hash index

Hash tables are not sorted data structures, and there are many types of queries which hash indexes can not even help with. For instance, suppose you want to find out all of the employees who are less than 40 years old. How could you do that with a hash table index? Well, it’s not possible because a hash table is only good for looking up key value pairs – which means queries that check for equality (like “WHERE name = ‘Jesus'”). What is implied in the key value mapping in a hash table is the concept that the keys of a hash table are not sorted or stored in any particular order. This is why hash indexes are usually not the default type of data structure used by database indexes – because they aren’t as flexible as B- trees when used as the index data structure. Also see: Binary trees versus Hash Tables.

What are some other types of indexes?

Indexes that use a R- tree data structure are commonly used to help with spatial problems. For instance, a query like “Find all of the Starbucks within 2 kilometers of me” would be the type of query that could show enhanced performance if the database table uses a R- tree index.

Another type of index is a bitmap index, which work well on columns that contain Boolean values (like true and false), but many instances of those values – basically columns with low selectivity.

How does an index improve performance?

Because an index is basically a data structure that is used to store column values, looking up those values becomes much faster. And, if an index is using the most commonly used data structure type – a B- tree – then the data structure is also sorted. Having the column values be sorted can be a major performance enhancement – read on to find out why.

Let’s say that we create a B- tree index on the Employee_Name column This means that when we search for employees named “Jesus” using the SQL we showed earlier, then the entire Employee table does not have to be searched to find employees named “Jesus”. Instead, the database will use the index to find employees named Jesus, because the index will presumably be sorted alphabetically by the Employee’s name. And, because it is sorted, it means searching for a name is a lot faster because all names starting with a “J” will be right next to each other in the index! It’s also important to note that the index also stores pointers to the table row so that other column values can be retrieved – read on for more details on that.

What exactly is inside a database index?

So, now you know that a database index is created on a column in a table, and that the index stores the values in that specific column. But, it is important to understand that a database index does not store the values in the other columns of the same table. For example, if we create an index on the Employee_Name column, this means that the Employee_Age and Employee_Address column values are not also stored in the index. If we did just store all the other columns in the index, then it would be just like creating another copy of the entire table – which would take up way too much space and would be very inefficient.

An index also stores a pointer to the table row

So, the question is if the value that we are looking for is found in an index (like ‘Jesus’) , how does it find the other values that are in the same row (like the address of Jesus and his age)? Well, it’s quite simple – database indexes also store pointers to the corresponding rows in the table. A pointer is just a reference to a place in memory where the row data is stored on disk. So, in addition to the column value that is stored in the index, a pointer to the row in the table where that value lives is also stored in the index. This means that one of the values (or nodes) in the index for an Employee_Name could be something like (“Jesus”, 0x82829), where 0x82829 is the address on disk (the pointer) where the row data for “Jesus” is stored. Without that pointer all you would have is a single value, which would be meaningless because you would not be able to retrieve the other values in the same row – like the address and the age of an employee.

How does a database know when to use an index?

When a query like “SELECT * FROM Employee WHERE Employee_Name = ‘Jesus’ ” is run, the database will check to see if there is an index on the column(s) being queried. Assuming the Employee_Name column does have an index created on it, the database will have to decide whether it actually makes sense to use the index to find the values being searched – because there are some scenarios where it is actually less efficient to use the database index, and more efficient just to scan the entire table. Read this article to understand more about those scenarios: Selectivity in SQL.

Can you force the database to use an index on a query?

Generally, you will not tell the database when to actually use an index – that decision will be made by the database itself. Although it is worth noting that in most databases (like Oracle and MySQL), you can actually specify that you want the index to be used.

How to create an index in SQL:

Here’s what the actual SQL would look like to create an index on the Employee_Name column from our example earlier:

CREATE INDEX name_index
ON Employee (Employee_Name)

How to create a multi-column index in SQL:

We could also create an index on two of the columns in the Employee table , as shown in this SQL:

CREATE INDEX name_index
ON Employee (Employee_Name, Employee_Age)

What is a good analogy for a database index?

A very good analogy is to think of a database index as an index in a book. If you have a book about dogs and you are looking for the section on Golden Retrievers, then why would you flip through the entire book – which is the equivalent of a full table scan in database terminology – when you can just go to the index at the back of the book, which will tell you the exact pages where you can find information on Golden Retrievers. Similarly, as a book index contains a page number, a database index contains a pointer to the row containing the value that you are searching for in your SQL.

What is the cost of having a database index?

So, what are some of the disadvantages of having a database index? Well, for one thing it takes up space – and the larger your table, the larger your index. Another performance hit with indexes is the fact that whenever you add, delete, or update rows in the corresponding table, the same operations will have to be done to your index. Remember that an index needs to contain the same up to the minute data as whatever is in the table column(s) that the index covers.

As a general rule, an index should only be created on a table if the data in the indexed column will be queried frequently.

Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.

FOLLOW Varoon Sahgal, Author of ProgrammerInterviewon
  • wolex

    This is a beautiful piece.

  • Nikhil Ponnuru

    veryy nice and intuitive!!

  • John Leonard Javiniar

    What is the advantage of creating a multi-column index over a single column index? Is it just the same with creating multiple single column indexes?

  • crazy

    I am a bit confused between Index and non clustered Index.What is the difference between Index and non clustered Index.They boths seem to be same thing?

  • Shail

    Actually, I was not going to read the article seeing the size of page. But Once I read initial few lines, I couldn’t stop before reading complete article. Nice one.


  • Anonymous

    it is very clear thank you

  • Srinivas

    Excellent Explanation… Thank You.

  • Mai

    excellent explanation!

  • John

    great explanation !!!

  • Adam Zerner

    I think these explanations could really benefit from some accompanying diagrams.

  • Zeetac

    Awesome tutorial on Index. Can crack any developer interview at any level with this knowledge. Must read for interview aspiring candidates. Great Job. The best Article on index read so far. Simple and easy to grassp.

  • Vikram Maduri

    nice article, found what i was looking for…. thank you

  • m6106918

    Thank you! much better than I learned in school :)

  • sqlgeek

    indexing on age will sort the data based on the age. so it will only look into the partition where the age is < 50 and won't look into other partition

  • Marsi

    thank you:) good explanation

  • bala

    Really great explanation. Try to provide all other concepts in sql

  • aditi bhavsar

    Very good article. clearly and well explained.!

  • BSR

    Good one. Thank you.

  • Cool

    Please provide SAS ineterview questions as well

  • ananth

    Clean explanation, you didn’t provide the references for this article.

  • qiao

    best explanation, I wish i have found this site sooner

  • Raul RS

    Very nice explaination

  • Askar Khan

    Good Job thanks

  • JG


  • vishnu

    nice explanation on indexing…thanks

  • Alton Douglas

    it depends on how the index was created
    if (CREATE INDEX …) it will return all/duplicate records
    if (CREATE UNIQUE INDEX …) it will return unique records

  • Shikar

    Nice clear explanation. Better if syntax for B+ index & Hash index given separately.

  • Suraj ambulkar

    Excellent explanation

  • Anurag

    very acute explanation.Love it !!!!!

  • Kriti

    Feels like I am receiving a classroom training from a expert tutor. Each word is so explanatory. Thank you very much for writing these articles. Best explanation so far. Great Job !!!

  • prakash

    if the search on indexed column Employee_name=”jesus” found that there are more than one person’s name is jesus, then how it will work…

  • deepti

    very good explanation. thank you

  • Sourabh

    Its totally Amazing! Thanks a lot!

  • Akki

    Explained very well in simple and easy understandable language. Thanks a lot for this.

  • rodrigopiovezan
  • Henry Le

    it’s great, helped me a lot. Thanks!

  • sumanth

    How to see that index

  • Mahesh

    Good explanation, but my doubt is if we created index on some columns which having 1000 rows in it and then we added more 100 rows in it means now we have 1100 rows….then index need to create again ?

  • Stephen S

    Really nice explanation.

  • N

    So much theory, many things are missing specially efficiency of indexes bases of their types like int, string, date etc

  • Suba

    Good One :) I have learnt the basics of Indexing… and Glad to see ‘Jesus’ in this article… God Bless You :)

  • Suba


  • chetan

    very nice tutorial …thanks much… :)

  • Mansoor

    Very well explanation. In few minutes it helped me revise all my concepts with extreme good explanation. Successful effort

  • Amit Agrawal

    well explain, thanks

  • Hemny Singh

    does index automatically created for primary key ?

  • Emre

    “Jesus” Christ! Very good explanation :)

  • Shekhar Bhabad

    amazing explanation…………..

  • Peter

    Jesus saves in a db?

  • Naveen Kocherla

    Excellent explanation….Keep it up

  • Ryan

    Very good article.
    So, is an index already created on a Primary Key automatically?

  • rinx

    very simplified explanation…thanks

  • Damian

    Something to add, have in mind if you use wildcard % in front of the string that you will look for (example LIKE ‘%Jesus’) index will not help you at all (due to there are not way to predict what can be appear at front, i.e.: Jhon Jesus, Mike Jesus, etc.)

  • Dima V

    Yeah you will have to create an index on age.

  • Sudha Kumari


  • tabide

    More specifically, the most common used data structure for indexing database like mysql is B+ tree. B tree is quite different from B+ tree.

  • [email protected]


  • Kumar

    This article is very good and thanks for provieding this info, also can you please give some details on Cluster and Non-Cluster index like how the non-cluster stores the data with cluster and without cluster index?

  • Guest

    How the database system would come to know that there are only two values in "SEX" column?
    Will it not have to scan at least once to come to know that there are only two possible values in this column?

  • smassey3

    This was the most helpful discussion on index that I have found. Thanks so much.

  • navi kaish

    its too much good discription…… clears my all ambiguaties…….thanks a lot and plz carry on………….the plus point is you use very simple english.its gud work

  • GT

    damn good article!

  • prabha

    very clear explanation

  • varoon10

    Thanks Fariha!

  • varoon10

    THanks Ayush!

  • varoon10

    Thanks Sam!

  • varoon10

    Thanks Vuyani!

  • varoon10

    Thanks Gaurav!

  • varoon10

    Thanks Sajith!

  • varoon10

    Thanks Sajeesh!

  • varoon10

    Thanks Pankaj!

  • Bharath K H

    Simply superb. Never expected it is this much easy to understand concepts. I clearly got it what I wanted . and further looking for PL/SQL interview questions in this knowledge pool.

  • pankaj

    great tute ever seen

  • Sajeesh

    Wow.. simple and very clean explanation. Was very useful. Thanks a lot.

  • Sajith

    Interesting writing style…congrats!!

  • gaurav9936

    beautiful explaination

  • Vuyani Billy Nyathikazi

    wow…clear and easy to understand..thanks

  • apurva

    very nice explanation…i appreciate you to create such a helpful site :)

  • Vijay Kumar Rajput

    wow !!! that is what I was looking….awesome..tutorial. I was searching.some pointers on index.. and could not stop my self to read all page… Language of text is so easy and explanatory… :-) Thanks for posting it.. I m gonna following it..

  • JO GI

    Good job sir…..explanation view is best..

  • Vimal

    Really it clears all my doubts….

  • Jyoti Gupta

    Really very good explanation.. It helped me a lot.. thank you..

  • CM

    Clear and Simple! Thanks

  • Manoj

    Very Cool…. One of the best explanation when i compared to other forums

  • Sam

    Really it is simple to the core and yet gives in detail understanding of the start up required for even a newbie to SQL/ Indexes. Awesome!

  • jimbob

    Thanks that's a great introductory explanation!

  • abc

    Hey great explaination.could you please upload an explaination for Normalization

  • N

    Nice article. Thanks a lot.

  • Kumar Ankit

    Nice explanation !

  • babu

    Very good Explanation….

  • A

    Good explanation but i am confused a bit. please explain me.
    if my query is like this. select * from table where age<50. then how indexing is going to help in this case. do i have to create index on age. or same index Employee_Name (for reference :- Employee_Name="jesus") as explained above can help me.

  • fariha

    great effort. fantastic explanation

  • AJ

    Too good, everything in detail but not boring at all.

  • Hiral

    Very nice explanation.

  • Ayush

    Thanks for your wonderful explanation !!!! The book example said it all

  • Rajneesh Kaundal

    good explanation of index.. Thanks

  • Deepak

    excellent explanation, very impressive……good work, keep it up….

  • Dev

    Good One

  • varoon10

    THanks Raghav! Maybe I will write an e-book or something haha!

  • varoon10

    Thanks Vimal!

  • varoon10

    THanks Stefan!

  • varoon10

    THanks Pritam!

  • varoon10

    Thanks Kevin!

  • varoon10

    THanks Vinoth!

  • varoon10

    THanks Shafeeq!

  • varoon10

    Thanks Azra!

  • varoon10

    Thanks Amit!

  • varoon10

    Thanks Prageeth!

  • varoon10

    Thanks Alex!

  • varoon10

    Thanks Harsh!

  • kevin

    great work

  • Pritam


  • Stefan

    Great work

  • Vimal

    Awesome. Clearly explained article..

  • raghav

    awsome explanation ,you should write ur own book…the way u explain is just amazing!!!

  • Alex

    Excellent job explaining this concept so clearly. Thank-you!

  • Prageeth Jayasinghe

    Really appreciate your great effort.

  • SirAmit Nathani

    very good explanation…:)

  • azra

    good work…

  • shafeeq

    Great work ….It helped me lot..thanks …..

  • Harsh Dev

    Awesome explanation..great job

  • Vinoth

    Superb Explanation.. thanks so much keep up the gud work…