SQL INDEXING – Simplified

3 Apr

Let us talk about indexing in SQL Server:

Depending on size of the data, a table can have more than a million rows. If you want to search for a specific record there are two ways:

  1. Go row by row and see if that is the row you want.
    Example: Let us say we want to search an employee table that has 1 million rows for an employee with last name “Smith”. Remember you can have more than one record with name “Smith”. One way to do this is to go record by record and check if last name is “Smith”. The problem with this approach is that this will be very slow as you have to go row by row. May be there is only one record with last name “Smith” and that could be the last record. In this case you will have to read one million times, only to find one record. This in SQL terms is called “TABLE SCAN”.
  2. The second approach is a better approach. What if I tell you that all names are sorted in “Alphabetical Order”. So, if you directly go to half a million record and if that name is say “Karsen” then you know “Smith” will be after “Karsen” (‘S’ comes after ‘K’). Now you can go directly to six hundred thousand record and if that name is “Tedd” then you know “Smith” is between half a million record and six hundred thousand record.  So now in two attempts you have narrowed it down from one million to hundred thousand. Isn’t that great? This is what is called as indexing.

Let us now get deep into details. Indexes are created on columns in tables. The index provides a fast way to look up data based on the values within those columns. An index is made up of a set of pages (index nodes) that are organized in a B-tree structure. Figure below shows how a typical B-tree looks like.

 

SQL Indexing Example
Fig.1 – B-tree.

 

Data is stored in the form of pages. Now let us try to find records with last name “Dull”.
Go to Root Page (level 1). With indexing now we know that any name starts with ‘Bennet’ and is before ‘Karsen’ we should go to page 1007. What this means is if we want to find out employees with name “Charlie” we should go to page 1007 and if we want to find out employees with name “Kyle’ we should go to page 1009 (“Ky” comes between “Ka” and “Sm”).

So, looking at page 1007 (level 0) we see that if name is between ‘Bennet’ and ‘Greane’ (‘D’ comes between ‘B’ and ‘G’) we need to go to page 1132. So, let us go there and find out.

Looking at page 1132 we can see record with name “Dull”. Hurray…. our search is over. We found our record. This is how indexing will work typically.

There are two types of indexes, Clustered index and Non Clustered Index. Clustered index is on primary key and data will be physically sorted. So, leaf level will have the actual data record. In a non-clustered index level will have a pointer to actual data page. This means you have to go one extra step to actually get your data. Remember indexes can make your search faster but insert, updates and delete will be slower.

Thanks for visiting my blog. Please feel free to leave suggestions/feedbacks/comments.
If you like my post please click “LIKE” button below.

Read about SQL Technical Interview Questions here: Crack the SQL Interview

Written by Amit Uppal

Email us

Advertisements

3 Responses to “SQL INDEXING – Simplified”

  1. Prashant Munshi April 6, 2012 at 8:42 am #

    Equally important to know about different tables used in databases and each provide a specific functionality. Please visit this link for a good coverage on different types of tables :
    Link : http://crazy4db.blogspot.in/2012/04/what-are-temporary-tables.html

  2. PriConnects April 11, 2012 at 10:21 am #

    Thanks

  3. Prashant Munshi April 18, 2012 at 6:09 am #

    Creating indexes is a very crucial issue from the performance point of view. It’s not just important to create index but also important to understand the concepts and various types of indexes and their structure to suit to a particular access pattern. The index that has been described here so nicely falls in the category of B-Tree index. To know more about the index I would like to advise to visit : http://crazy4db.blogspot.in/2012/04/overview-of-database-indexes.html

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: