Sql Server 2012 : Hierarchical Data and the Relational Database - Hierarchical Table Indexing Strategies

You can create a depth-first index or a breadth-first index (or both) on your hierarchical tables. The two types differ in how SQL Server physically stores node references in the index. Defining depth-first and breadth-first indexes can have a significant impact on performance for accessing data in hierarchical tables.

As their names imply, depth-first indexing stores parent and child node references near each other, whereas breadth-first indexing stores references for nodes at the same hierarchical level near each other. Therefore, you will choose the appropriate type of index based on an understanding of how your hierarchical data is shaped in the table, how it will grow, and how it will be typically queried by client applications. You can create both types of indexes as well, for efficient access both vertically and horizontally across the tree.

Note

Regardless of what indexing strategy you employ, comparison operations are always performed in depth-first order. Thus, A < B means that A always comes before B in a depth-first traversal of the tree (or A is to the left of B if they are both at the same level), even if breadth-first indexing is used.

Depth-First Indexing

Defining either a primary key index or a unique index on a hierarchyid column results in a depth-first index. Because the NodeId column (of type hierarchyid) is designated as the primary key in the employee table, you have already created a depth-first index.

With depth-first indexing (depicted in Figure 1), SQL Server tries to physically store references to nodes in a subtree as near to each other as possible. By “near each other,” we mean that SQL Server records them on disk in the same page, if possible—or in the same extent, if not, and so on—in order to maximize query performance. This strategy yields high query performance if your hierarchy runs very many levels deep. Creating a depth-first index for such a hierarchy will result in very fast vertical searching on the tree (that is, querying ancestors and descendants up and down a potentially long chain).

Figure 1. Physical row storage when optimized for depth-first searching.

Breadth-First Indexing

With breadth-first indexing, illustrated in Figure 2, reference to nodes at the same level of the hierarchy are physically stored as near to each other as possible. This type of index yields high query performance for trees that grow very broad. If there are many children beneath the parents in your hierarchy, you will want to create a breadth-first index to enable fast horizontal searching across a potentially large number of nodes at the same level.

Figure 2. Physical row storage when optimized for breadth-first searching.

To define a breadth-first index, you create a composite index on your hierarchical table that includes two columns: the integer column that holds the level of the node within the hierarchy (such as the NodeLevel column defined in the employee table, based on the GetLevel method against the NodeId column) and the hierarchyid column itself (NodeId). So to create a breadth-first index, run the following code:

CREATE UNIQUE INDEX IX_EmployeeBreadth
 ON Employee(NodeLevel, NodeId)

As we mentioned already, one table can have both depth-first and breadth-first indexes by creating one primary key or unique index on the hierarchyid column and another composite index on the node-level column and the hierarchyid. This will carry slightly more overhead for data manipulation language (DML) actions, because updates will need to be performed in both indexes; however, query performance will be very fast for both horizontal and vertical searching across large hierarchies that are both very broad and very deep.