Microsoft SQL Server 2012 Bible

Indexing Strategies

There are two approaches when needing to index hierarchical data, and the index you apply depends on which approach you take:

• Depth-first
• Breadth-first

In a depth-first approach, rows in a subtree are stored near each other. For example, employee records are stored near their managers' record. In a breadth-first approach, rows for each level in the hierarchy are stored together. For example, managers and their direct reports are stored near each other.

Thus, in a depth-first approach the index is applied so that all nodes in the subtree of a node are colocated. Depth-first indexes are efficient for queries about the subtree, such as “Find all files in this folder and its subfolders.”

CREATE UNIQUE INDEX OrgNode_Depth_First 
ON HumanResources.Employee(OrganizationNode) ;
GO

In a breadth-first index all direct children of a node are colocated. Breadth-first indexes are efficient for queries about immediate children, such as “Find all employees who report directly to this manager.”

CREATE CLUSTERED INDEX OrgNode_Breadth_First 
ON HumanResources.Employee(OrganizationLevel) ;
GO

Whether to have depth-first, breadth-first, or both, and which to make the clustering key (if any), depends on the relative importance of the above types of queries, and the relative importance of SELECT versus DML operations.