A value of the hierarchyid data type represents a position in a tree hierarchy. Values for hierarchyid have the following properties:

• Extremely compact
  The average number of bits that are required to represent a node in a tree with n nodes depends on the average fanout (the average number of children of a node). For small fanouts, (0-7) the size is about 6*log_An bits, where A is the average fanout. A node in an organizational hierarchy of 100,000 people with an average fanout of 6 levels takes about 38 bits. This is rounded up to 40 bits, or 5 bytes, for storage.
  
• Comparison is in depth-first order
  Given two hierarchyid values a and b, a<b means a comes before b in a depth-first traversal of the tree. Indexes on hierarchyid data types are in depth-first order, and nodes close to each other in a depth-first traversal are stored near each other. For example, the children of a record are stored adjacent to that record. For more information, see Using hierarchyid Data Types (Database Engine).
  
• Support for arbitrary insertions and deletions
  By using the GetDescendant method, it is always possible to generate a sibling to the right of any given node, to the left of any given node, or between any two siblings. The comparison property is maintained when an arbitrary number of nodes is inserted or deleted from the hierarchy. Most insertions and deletions preserve the compactness property. However, insertions between two nodes will produce hierarchyid values with a slightly less compact representation.
  

The hierarchyid data type has the following limitations:

• A column of type hierarchyid does not automatically represent a tree. It is up to the application to generate and assign hierarchyid values in such a way that the desired relationship between rows is reflected in the values. Some applications might not even want to have a column of type hierarchyid represent a tree. Perhaps the values are references to location in a hierarchy defined in another table.
  
• It is up to the application to manage concurrency in generating and assigning hierarchyid values. There is no guarantee that hierarchyid values in a column are unique unless the application uses a unique key constraint or enforces uniqueness itself through its own logic.
  
• Hierarchical relationships represented by hierarchyid values are not enforced like a foreign key relationship. It is possible and sometimes appropriate to have a hierarchical relationship where A has a child B, and then A is deleted leaving B with a relationship to a nonexistent record. If this behavior is unacceptable, the application must query for descendants before deleting parents.
  

There are two strategies for indexing hierarchical data:

• Depth-first
  A depth-first index, rows in a subtree are stored near each other. For example, all employees that report through a manager are stored near their managers' record.
  

• Breadth-first
  A breadth-first stores the rows each level of the hierarchy together. For example, the records of employees who directly report to the same manager are stored near each other.
  

The GetLevel() method can be used to create a breadth first ordering. In the following example, both breadth-first and depth-first indexes are created:

USE AdventureWorks ; 
GO

CREATE TABLE Organization
   (
    EmployeeID hierarchyid,
    OrgLevel as EmployeeID.GetLevel(), 
    EmployeeName nvarchar(50) NOT NULL
   ) ;
GO

In a depth-first index all nodes in the subtree of a node are co-located. Depth-first indexes are therefore efficient for answering queries about subtrees, such as "Find all files in this folder and its subfolders".

CREATE CLUSTERED INDEX Org_Breadth_First 
ON Organization(OrgLevel,EmployeeID) ;
GO

CREATE UNIQUE INDEX Org_Depth_First 
ON Organization(EmployeeID) ;
GO

In a breadth-first index all direct children of a node are co-located. Breadth-first indexes are therefore efficient for answering queries about immediate children, such as "Find all employees who report directly to this manager".

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 vs. DML operations. For a detailed example of indexing strategies, see Tutorial: Using the hierarchyid Data Type.

Two alternatives to hierarchyid for representing hierarchical data are:

• Parent/Child
  
• XML
  

hierarchyid is generally superior to these alternatives. However, there are specific situations detailed below where the alternatives are likely superior.

Parent/Child

USE AdventureWorks ;
GO

CREATE TABLE ParentChildOrg
   (
    EmployeeID int PRIMARY KEY,
    ManagerId int REFERENCES ParentChildOrg(EmployeeID),
    EmployeeName nvarchar(50) 
   ) ;
GO

XML

CREATE TABLE XMLOrg 
    (
    Orgid int,
    Orgdata xml
    ) ;
GO

Most trees are represented today using Parent/Child. The easiest way to migrate from a Parent/Child structure to a table using hierarchyid, is to use a temporary column or a temporary table to keep track of the number of nodes at each level of the hierarchy. For an example of migrating a Parent/Child table, see lesson 1 of Tutorial: Using the hierarchyid Data Type.

To maximize performance of querying hierarchies, SQL Server automatically performs three transformations of queries involving hierarchyid. The result of these transforms can be seen in the showplan output for transformed queries.

IsDescendantOf is transformed to an range seek

GetAncestor is transformed to a range scan and residual predicate

SELECT * FROM Employees WHERE EmployeeId.GetAncestor(1) = @value

SELECT * FROM Employees 
WHERE 
   EmployeeId >= @Value AND EmployeeId <= @value.DescendantLimit() 
   AND EmployeeId.GetAncestor(1) = @value

GetAncestor is transformed to an index lookup using the breadth-first-index

SELECT * FROM Employees 
WHERE 
   EmployeeId >=@value AND EmployeeId <= @Value.DescendantLimit() 
   AND @value.GetLevel()+1 = EmployeeId.GetLevel()

Concepts

Other Resources

Help and Information