Database Reference
In-Depth Information
The intermediate level stores one row per each leaf-level page. It stores two pieces of the information: the
physical address and minimum value of the index key from the page it references. The only exception is the very
first row on the first page where SQL Server stores
NULL
rather than the minimum index key value. With such
optimization, SQL Server does not need to update non-leaf level row when you insert the row with the lowest key
value in the table.
The pages on the intermediate levels are also linked to the double-linked list. SQL Server adds more and more
intermediate levels until there is a level that includes just the single page. This level is called the
root level
, and it
becomes the entry point to the index, as shown in Figure
2-7
.
Figure 2-7.
Clustered index structure: Root level
As you see, the index always has one leaf level, one root level, and zero or more intermediate levels. The only
exception is when the index data fits into a single page. In that case, SQL Server does not create the separate root level
page, and the index consists of just the single leaf-level page.
The number of levels in the index largely depends on the row and index key sizes. For example, the index on the
4-byte integer column will require 13 bytes per row on the intermediate and root levels. Those 13 bytes consist of a
2-byte slot array entry, a 4-byte index key value, a 6-byte page pointer, and a 1-byte row overhead, which is adequate
because the index key does not contain variable-length and NULL columns.
As a result, you can accommodate 8,060 bytes / 13 bytes per row = 620 rows per page. This means that, with the
one intermediate level, you can store information about up to 620 * 620 = 384,400 leaf-level pages. If your data row
size is 200 bytes, you can store 40 rows per leaf-level page and up to 15,376,000 rows in the index with just three levels.
Adding another intermediate level to the index would essentially cover all possible integer values.
■
In real life, index fragmentation would reduce those numbers. We will talk about index fragmentation
in Chapter 5.
Note
