In this article we are going to see how index pages are organized with data pages and how to read different levels and types of indexes with simple example

To start with, let’s create a simple table in test database named LearningInternals.

CREATE TABLE tExample6(

intEmployeeId int IDENTITY(1001,1),

strFirstName varchar(100),

strDeptCode char(6),

strAddress varchar(200),

intSalary int)

Let’s create one clustered index on intEmployeeId and non clustered index on strDeptCode.

CREATE CLUSTERED INDEX CI_tExample6_intEmployeeId ON tExample6(intEmployeeId)

GO

CREATE NONCLUSTERED INDEX NCI_tExample6_strDeptCode on tExample6(strDeptCode)

GO

Here is the query to list index entries in sys.indexes system view.

SELECT

      OBJECT_NAME(object_id) TableName,

      name IndexName,

      Index_Id,

      type,

      type_desc

FROM sys.indexes

WHERE OBJECT_NAME(object_id) = 'tExample6'

GO

Output:

To read internals of index, We need Leaf and Non leaf pages for both clustered and non clustered index. For that, let’s add 1000 dummy
records in our table tExample6.

Here is the statement to fire insert statement 1000 times.

SET NOCOUNT ON

INSERT INTO tExample6(strFirstName, strDeptCode, strAddress,intSalary)

VALUES('AAAAA','DEPT01','CHENNAI',12500)

GO 1000

Note:  In this example, Non clustered index is populated with duplicate value ‘DEPT01’.
Query optimizer most probably ignores non clustered Indexes if duplicates are beyond its limit.

As this is a learning exercise let’s not consider this duplicate and its side effects at this moment.

Now let’s use below query to see how B-Tree structure is formed for tExample6

SELECT

      OBJECT_NAME(object_id) TableName,

      index_type_desc,

      index_id,

      index_depth AS IndexDepth,

      index_level AS IndexLevel,

      record_count AS RecordCount,

      page_count AS PageCount

FROM sys.dm_db_index_physical_stats (DB_ID ('LearningInternals') , OBJECT_ID ('tExample6'), NULL, NULL, 'DETAILED');

GO

Observation:
When all data records are available in single data page, there is no need of index page and B-Tree.
I inserted only one record in a Clustered Index table and found index page missing.  Later I inserted lot more records to have more than one data page. Once data page count becomes 2 or more, index page comes in to picture.
Lession learnt : to form basic B-Tree non clustered index structure with root page, minimum 2 data pages are required.

We need leaf and non leaf page numbers for clustered and non clustered indexes. Here is the DBCC command to list all pages allocated to tExample6

DBCC TRACEON(3604)

DBCC IND('LearningInternals', 'tExample6', -1)

DBCC TRACEOFF(3604)

Output (trimmed and formatted for better understanding):

From the above pages I have picked 1 page for each index type and level for further analysis

 Before going to see the internals of different types and levels of index pages, let’s quickly recap their properties and page types used.

Before moving on to see how to read all above types of pages, lets understand the header section of Index page. This is not to repeat this header section for all upcoming examples.

Note:
Properties of Header section are same for all types of pages (Data page, Index page etc.)
But based on the page type values of m_type and m_level properties may differ.

Here I have explained some key properties of header page.

Sample pages in each level of Clustered Index. 

Clustered Index Pages:

I. How to read Root/Intermediate level Index page of Clustered Index:

Here is the DBCC command to see root page of Clustered Index table tExample6:

DBCC TRACEON(3604)

DBCC PAGE('LearningInternals', 1, 265, 3)

DBCC TRACEOFF(3604)

Output (Data Section):
Note : Header and Row Offset Portions are removed. Please refer my previous articles to learn more on this.

Note:  In SQL 2005 and 2008, data section of root and leaf level Index pages are displayed in grid.
This looks great and easy to understand. I do remember that, in SQL 2000 I was interpreting index record in index pages.

Observation:
In Root page range of intEmployeeId(Key) and child (intermediate/leaf) pages to cover the range are given.

To fetch Employeeid value 1200:
1. Query engine first check root page and examine employeeid range values.
2. Page number 261 is picked as this is the first page b/w Employee range 1189 and 1377

II. How to read Leaf page of Clustered Index:

Leaf page of clustered index contains actual data row. Please refer below link to know how to read data page.

http://www.sqlservercentral.com/blogs/livingforsqlserver/archive/2010/12/21/sql-server-storage-internals-part-4-how-to-read-a-heap-page.aspx

 
Non Clustered Index Pages (NCI):

As you can understand, all B-Tree levels of non clustered indexes hold index pages.

Key points to remember:
1. Root page of NCI will have reference to Intermediate or leaf level pages of NCI.
2. Intermediate level pages of NCI will have reference to either lower level intermediate page or leaf pages.
3.  Leaf level pages of NCI will have
     3.1 ROWID reference of underlying table if the table doesn’t have clustered index
     3.2 Clustered Index key references if Clustered index is available in underlying table.

lets create a sample table named tExample6_NCItest and create NCI on strDeptCode column.

CREATE TABLE tExample6_NCItest(

intEmployeeId int IDENTITY(1001,1),

strFirstName varchar(100),

strDeptCode char(6),

strAddress varchar(200),

intSalary int)

GO

CREATE NONCLUSTERED INDEX NCI_tExample6_strDeptCode on tExample6(strDeptCode)

GO

Then let’s populate the table with some dummy records.

SET NOCOUNT ON

INSERT INTO tExample6_NCItest(strFirstName, strDeptCode, strAddress,intSalary)

VALUES('AAAAA', 'DEPT' + cast(round(rand()*100,0) as char(2)),'CHENNAI',12500)

GO 1000

Here is the DBCC command to see data section of root page of NCI.

DBCC TRACEON(3604)

DBCC IND('LearningInternals', 'tExample6_NCItest', -1)

DBCC TRACEOFF(3604)

GO

Output (Formatted with comments):

III. How to read Root/Intermediate page of Non clustered Index:

Here is the DBCC command to see PAGE content of Root Page number 283

DBCC TRACEON(3604)
DBCC PAGE('LearningInternals', 1, 283, 3)
DBCC TRACEOFF(3604)

Output (Formatted):

IV. How to read Leaf page of Non clustered Index in a HEAP:

Lets take child page number 282 to check internals of leaf page of NCI.

DBCC TRACEON(3604)

DBCC PAGE('LearningInternals', 1, 282, 3)

DBCC TRACEOFF(3604)

Output (formatted)

Now let’s create clustered index on tExample6_NCItest table and see the impact on leaf pages of NCI.

CREATE CLUSTERED INDEX tExample6_NCItest_intEmployeeId ON tExample6_NCItest(intEmployeeId)

GO

Observation:
Creating a clustered index on a heap having non clustered index, forces to rebuild the non clustered index. Resulting changes in page allocation.
Reason: NCI leaf page index entries needs to update its reference from RowId to Clustered Index Keys.

 IV. How to read Leaf page of Non clustered Index table in Clustered Index Table:

Let’s take child page number 296 to read content of NCI leaf page.

DBCC TRACEON(3604)

DBCC PAGE('LearningInternals', 1, 296, 3)

DBCC TRACEOFF(3604)

Output (formatted)

Summary:

In this article, we have seen how index and data pages are organized in Clustered and Non clustered indexes. And also we have seen how to read different levels of clustered and Non clustered index pages.

In my next article I am going to try interpreting bitmap pages like GAM, SGAM, IAM etc.

Reference
1. Microsoft Press SQL Server 2008 Internals