Index structure, illustrated (3 minutes)

Part of "How Index Keys and Includes Work (1 hour)"


Some important things to know about index structure.

This is an example of a root page.

Root and intermediate pages have key columns only

If your index has included columns, they are not on those pages.

The values given for those key columns, like these samples, they are simply guideposts so that if we are trying to seek on the leading key column, or the first two key columns, or all three key columns in this case, we can use them as guideposts to direct us efficiently through the tree, and only read the pages that we have to read.

In the leaf of the index…

We have those key columns as well, and the leaf is also ordered by those key columns. In addition, if included columns are defined for the nonclustered index, the included columns are there as well. It does not have to sort data in those included columns.

Included columns increase the size of your index leaf

Of course, if we allow columns as includes, if we put columns in our included columns list that can contain a large amount of data and then we have very large values in there, this could take up a lot of space on our pages.

So the included columns can definitely increase the size of our leaf, but they don’t change the way that the rows are ordered in the leaf of the index.

The root and intermediate pages in our index, they have the list of child pages, so we can follow these arrows and we can seek to those pages.

Then when we have more than one page at a level, which is true for everything except for the root page, those pages know about the previous page, if there is a previous page, as well as the next page.

This allows SQL Server, if it’s scanning the leaf level of this index it can scan forwards, or it could choose to scan backwards, if it started from what is drawn as the right side of the index on this page.

We draw index diagrams upside down

One of the confusing things about indexes is that we call this the leaf and we talk about it as a tree with a root, but the way we usually draw the indexes, we usually draw the leaf at the bottom of the picture. Well that means it’s really an upside down tree, right? Our root is at the top, and our leaf is at the bottom, so I do tend to picture this as an upside down tree.

I have tried to draw it the other way. You know, draw it with the leaf at the top, and it just doesn’t ever look right to me. So I do draw this as an upside down tree, and the leaf, when we’re looking in those views, the leaf will always be level 0.

The root of our index may have different [level] numbers depending on the depth of the index required to keep track of all of the information.

Next up, we’re going to take a look at a demo of how, given this structure, seeks work, and how scans work.