Indexing

Clustered Indexes
A printed phone directory is a great example of a clustered index. Each entry in the directory represents one row of the table. A table can have only one clustered index. That is because a clustered index is the actual table sorted in order of the cluster key. At first glance, you might think that inserting a new row into the table will require all the rows after the inserted row to be moved on the disk. Luckily, this is not the case. The row will have to be inserted into the correct data page, and this might require a page split if there is not enough room on the page for the new row. A list of pointers maintains the order between the pages, so the rows in other pages will not have to actually move.

The primary key of the phone directory is the phone number. Usually the primary key is used as the clustering key as well, but this is not the case in our example. The cluster key in the phone directory is a combination of last name and first name. How would you find a friend's phone number if you knew the last and first name? Easy, open the book approximately to the section of the book that contains the entry. If your friend's last name starts with an "F", you will search near the beginning of the book, if an "S", you will search towards the back. You can use the names printed at the top of the page to quickly locate the page with the listing. You then drill down to the section of the correct page till you find the last name you are looking for. Now you can use the first name to choose the correct listing. The phone number is right there next to the name. It probably takes more time describe the process than to actually do it. Using the last name plus first name to find the number is called a clustered index seek.

Lets say you wanted to find all the people who have the last name of "Smith" for a family reunion. How quickly could you locate all the names? Of course, it would take a matter of seconds to find all of them grouped together, possibly over a few pages. What if you wanted to locate everyone with the first name of "Jeff" in the book? Could it be done? Of course it could, but you would have to look at every entry in the entire book because the first name is the second column in our cluster key. This is called a clustered index scan, a very expensive operation on a big table.

Here is an example using one of the tables in AdventureWorks. The Sales.SalesOrderDetail table has a clustered index on SalesOrderID plus SalesOrderDetailID. Take a look at the graphical estimated execution plan (Figure 2) of the batch paying particular attention to the Query cost when either the first or second column in the cluster key is used.