How Indexes Work

As you learn more about how databases work, you will need to understand the design principles that underpin a good clustered index. We need to discuss how SQL Server stores clustered indexes. Basically, all table data is stored in 8 KB data pages. When a table contains a clustered index, the clustered index tells SQL Server how to order the table’s data pages. It does this by organizing those data pages into a B-tree structure, as illustrated.

Indexes

It can be helpful, when trying to remember which levels hold which information, to compare this structure to an actual (upside-down) tree. You can visualize the root node as the trunk of a tree, the intermediate levels as the branches of a tree, and the leaf nodes as the actual leaves.

The leaf nodes of the B-tree is always level 0, and the root level is always the highest level. The illustration shows only one intermediate level but the number of intermediate levels actually depends on the size of the table. A large index will often have more than one intermediate level, and a small index might not have an intermediate level at all.

Index pages in the root and intermediate levels contain the clustering key and a page pointer down into the next level of the B-tree. This pattern will repeat until the leaf node is reached. You’ll often hear the terms “leaf node” and “data page” used interchangeably, as the leaf node of a clustered index contains the data pages belonging to the table. In other words, the leaf level of a clustered index is where the actual data is stored, in an ordered fashion based on the clustering key.

The purpose of an index is to allow the database engine to traverse the index, finding the rows required for the query as quickly as possible, so the results can be returned to the query process as quickly as possible. This structure means the root page tells SQL Server which intermediate level page to read, and the intermediate page tells it which specific leaf level page to read.

You can read more on this subject here and here.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s