Using hierarchyid Data Types (Database Engine)

Key Properties of hierarchyid

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*logAn 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.

• 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.

Limitations of hierarchyid

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.

Indexing Strategies

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.

Examples

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 AdventureWorks2008R2 ; 
GO

CREATE TABLE Organization
   (
    BusinessEntityID hierarchyid,
    OrgLevel as BusinessEntityID.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,BusinessEntityID) ;
GO

CREATE UNIQUE INDEX Org_Depth_First 
ON Organization(BusinessEntityID) ;
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.

When to Use Alternatives to hierarchyid

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 AdventureWorks2008R2 ;
GO

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

XML

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

Migrating from Parent/Child to hierarchyid

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.

Query Transforms for hierarchyid

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.

GetAncestor is transformed to a range scan and residual predicate

DECLARE @value hierarchyid ;
SELECT * FROM AdventureWorks2008R2.HumanResources.Employee 
WHERE  OrganizationNode.IsDescendantOf(@value) = 1;

See Also

Reference

Concepts