Increase fan-out to reduce index depth

Question: One of my colleagues told me that I have to be careful how large my indexes are, both in terms of the index key and the index depth. I understand why the index key should be small but what is the index depth and why does it matter?

Answer: The index depth is the number of levels in the tree structure that comprises the index, numbered from 0 at the leaf level (the bottom of the tree, imagining a fir tree) and increasing by 1 up to the root page of the index (the tip of the tree, imagining a fir tree).

Generally speaking, to find a particular record at the leaf level of the index, the Storage Engine starts at the root of the index and navigates down through each level to find the correct leaf-level page that contains the record being retrieved. This is called traversing the index. There are short-cuts that occur for range scans compared to repeated single-row seeks, but those are beyond the scope of this column.

At each level in the index the Storage Engine needs to figure out which path to take to the next level down towards the leaf level. It does this by analyzing the records in the page it’s currently on, finding the page at the next level down which will lead eventually to the correct leaf-level page, and then moving down to that page at the next level down.

One way to think of it is that at any particular point while traversing the index, there are a set of sub-trees. One of the sub-trees will contain the record being searched for (or, I guess not, if that record turns out to not exist!). The Storage Engine needs to determine which sub-tree to move into, and then which sub-tree within that, and so on, until the very last sub-tree it moves down to is a single page at the leaf level.

At each level in the index while traversing it the Storage Engine needs to find the correct index record on the current page that identifies the sub-tree to navigate to. This involves doing a binary search over the records in the page, and occurs whether the index page is in memory, or first needs to be read in from disk.

Obviously, the more levels there are in the index between the root and the leaf, the more pages need to be binary searched, and so the slower an index traversal becomes. Therefore, the index depth affects the performance of index seeks.

If the index key is small then the “fan-out” of the index (the number of index records per page in the non-leaf levels of the index) will be higher. This is because index records in the non-leaf levels comprise the index key, plus a 6-byte pointer to a page at the level below in the index—the smaller the index key is, the smaller the index records will be and the more index records can be stored per page). The larger the fan-out, the smaller the index depth will be and the less effect on index seek performance there will be.

So, as well as reducing overall index size, having a small index key also increases the performance of operations on the index itself.