Intermediate Index Pages in SQL Server

2014-07-02 - General, Series, SQL Server Internals, Storage Wednesday

Introduction

SQL Server organizes all conventional indexes on disk in a structure called B+ Tree. In a B+ Tree two types of nodes exist. The first type is the leaf node containing the actual data. This node type is represented in SQL Server by type-1 data pages.

The second type is the intermediate level node. This node contains only key values and pointers to the next level. In SQL Server, these nodes are represented by type-2 pages, the intermediate index pages.

An Intermediate Index Page Example

The way to look at intermediate index pages in SQL Server is very similar to all other pages. First we need to set trace flag 3604 and then we can use DBCC PAGE:

DBCC TRACEON(3604);
DBCC PAGE(0,1,283,3);

The image below shows us that this page is, as expected, of type 2:

The header of an intermediate index page.

However, there is one difference to other DBCC PAGE results. There is an actual result set, returned by this statement. Let us take a closer look:

Rows on an intermediate index page.

The first three columns indicate which entry on page 1:283 we are actually looking at. The Level column tells us which level of the index we are at. Level 1 means we are actually looking at the root page. The first level in a B+ Tree always consists of only a single node. That node is called the root node, or - in SQL Server - root page.

The next two columns, ChildFileId and ChildPageId together make up the pointer to the child page. Remember, each entry in an intermediate index page (in a B+ Tree) points to another page in the index, its child page.

id is the actual key column. If the index key had multiple columns, all would be part of this result set. If you look at the entry for id = 7, you can see that it points to child page 285. The next entry is id = 10. So we would expect to find values that are >= 7 and <10[/tt] on page 285. Let us take a look:

sys.fn_PhysLocCracker in Action

Selecting from the table using the undocumented [tt]%%physloc%% virtual column, we can see that page 285 indeed contains the values 7, 8 and 9, so exactly the values we expected.

Summary

SQL Server indexes are organized as B+ Trees on disk. Each node in such a tree is a single SQL Server data page. The leaf level nodes are normal data pages of type 1, while the intermediate index pages are of type 2.

Categories: General, Series, SQL Server Internals, Storage Wednesday
Tags: , , , , , ,