In SQL server, there are two types of table based on the storage.A table with clustered index is called Clustered Table and a table with out a clustered index is called Heap Table. In earlier post, we have discussed about the specialty and the storage structure of the heap table. In this post let us discuss about Clustered Table.
A table with clustered index is called clustered table.Clustered index stores the actual data in the order of clustering key using a b tree structure and the data can be stored only in one order.That is the reason SQL server restricted the number of cluster index to one on a table.Let us see a logical representation of b tree structure. I have done this logical representation based on the copy of SalesOrderDetail table from AdventureWorks2008 database.
USE mydb
GO
SELECT * INTO dbo.SalesOrderDetail FROM AdventureWorks2008.Sales.SalesOrderDetail
GO
CREATE UNIQUE CLUSTERED INDEX ix_SalesOrderDetail ON dbo.SalesOrderDetail(SalesOrderDetailID)
 |
| Fig 1 |
This table has 121317 records. SQL server requires 3 level to store this data.Let us look into the Fig 1 and analyse the pages. On top level, you can see only one page which is called root page. In all B tree structure, there will be only one page in the root level which is the entry point to the tree structure.The root level is always the highest level . In our case root page has index level 2. The pages in the root level and intermediate levels are called index pages.In the index pages, SQL server stores the clustering key and entry point(page pointer) to the next level of B tree. The clustering key stored against child page id is the lowest value stored in the below level page(Child page). The maximum value of the clustering key on a specific child page can be obtained by looking into the next record. For example, in that root level first record (Salesorderdetailid =NULL,pageid=456) says, salesorderdetailid less than or equal to 29599 can be found in the page number 456. The next entry (Salesorderdetailid =29599 ,pageid=520) says, salesorderdetailid value between 29599 and 60372 can be found on page 520 and son on.The prevpage and nextpage values will work as doubly link list to connect the pages in that level. As there is only one page in the root level, the value of prevpage and nextpage will be always 0.
Let us move to the next level. we have four pages in this level. You can find the values in the nextpage and prevpage which links the pages in that level. This level is called intermediate level. The number of intermediate level and pages in the intermediate levels are depends on the size of the table and clustering key. A large table can have multiple intermediate level and a small table might not have any intermediate level.The values in this level can be read in the same way as we did in the root level. For example first entry in the first page of this level ( Salesorderdetailid =NULL,pageid=392) says , all record with salesorderdetailid less than and equal to 72 can be found in the page number 392.
Next level is the bottom level is called leaf level (index level 0). The pages in this level are called leaf pages or data pages. In this page you can find complete data(all column) of each record in the salesorderdetails table.In other words , the leaf level of the clustered index is where the actual data is stored.
Let us create a copy of SalesOrderDetail table without any indexes
USE mydb
GO
SELECT * INTO dbo.SalesOrderDetailHeap FROM AdventureWorks2008.Sales.SalesOrderDetail
GO
Now let us run the below set of query.Both will return the same record.We are more interested to see the IO part.
SET STATISTICS IO ON
GO
SELECT * FROM SalesOrderDetail WHERE SalesOrderDetailID =75
GO
SELECT * FROM SalesOrderDetailheap WHERE SalesOrderDetailID =75
The IO stats result look like as below.The logical read on the table which has clustered index is negligible compared to other one.
Let us see how SQL server manage to fetch the record using clustered index with 3 logical reads.First of all we need to find the root node of the clustered index. The dbcc ind will help us to find that.
DBCC IND('mydb','SalesOrderDetail',1)
This is returning 1501 records.This include one IAM page , one index page and 1499 data pages.Part of the output is shown below
From the output ,we can see that page 186 (page type 2) is the root page and this page is the entry point to this table. Let us see the out put of DBCC page.
GO
DBCC page('mydb',1,186,3)
SQL server stores the lowest value of clustered key stored in the child page and its page id in the index pages.For example Page 456 will have information of all the records that have value less than or equal to 29599 for salesorderdetailid column . In the same way page 520 will have information of all records that have value between 29599 and 60372 for salesorderdetailid(29599 may be there in both pages) and so on.The value of salesorderdetailid column for the record that we are searching is less than 29599. So the information about that records can be found in the childpage 456.
Let us see what we can see inside the page 456
GO
DBCC page('mydb',1,456,3)
The output contains 401 records and below is part of the output. you can run the DBCC page command with option 1 (last parameter) to see the page header.There we can find the m_type=2 which means it is a index page.As we discussed above,the details of records that we are searching (Salesorderdetailsid=75) can be found in the child page 393.
Let us see what we can see in page number 393.
GO
DBCC page('mydb',1,393,3) with tableresults
From the page header section we can see that value of m_type is 1. So this page is data page and it is the leaf level of the index. On scrolling down the output we can see the details of the record that we are searching as given below.We have value for all columns of the record that we are searching as the leaf level of the clustered index is the actual data.
SQL server manage fetch the records from clustered index reading only three pages(Root page,one page from intermediate level and one page from level)
Storage Overhead :Let us run the DBCC ind command for both tables(SalesOrderDetail and SalesOrderDetailHeap)
DBCC IND('mydb','SalesOrderDetail',1)
DBCC IND('mydb','SalesOrderDetailHeap',1)
From the output, we can see that the table, that does not have clustered index need 1496 page where as the table with clustered index need 1501 pages. This extra 5 pages are used to store the intermediate and root level of the b tree structure.Considering the advantage that we have on the select (lesser IO), this is a negligible overhead.
If you liked this post, do like my page on FaceBook
