层次结构数据 (SQL Server)

项目
08/29/2023

适用于：SQL Server Azure SQL 数据库 Azure SQL 托管实例

内置的 hierarchyid 数据类型使存储和查询层次结构数据变得更为容易。针对表示树（最常见的层次结构数据类型）对hierarchyid 进行了优化。

层次结构数据定义为一组通过层次结构关系互相关联的数据项。在层次结构关系中，一个数据项是另一个项的父级。通常存储在数据库中的层次结构数据示例包括以下内容：

组织结构
文件系统
项目中的一组任务
语言术语分类
网页间链接图

使用 hierarchyid 作为数据类型来创建具有层次结构的表，或描述存储在另一个位置的数据层次结构。在 Transact-SQL 中使用“hierarchyid 函数”查询和管理层次结构数据。

hierarchyid 的关键属性

hierarchyid 数据类型的值表示树层次结构中的位置。 hierarchyid 的值具有以下属性：

非常紧凑

在具有 n 个节点的树中，表示一个节点所需的平均位数取决于平均端数（节点的平均子级数）。端数较小时 (0-7)，大小约为 6*logAn 位，其中 A 是平均端数。对于平均端数为 6 级、包含 100,000 个人的组织层次结构，一个节点大约占 38 位。存储时，此值向上舍入为 40 位，即 5 字节。
按深度优先顺序进行比较

给定两个 hierarchyid 值 a 和 b，a<b 表示在对树进行深度优先遍历时，先找到 a，后找到 b。 hierarchyid 数据类型的索引按深度优先顺序排序，在深度优先遍历中相邻的节点的存储位置也相邻。例如，一条记录的子级的存储位置与该记录的存储位置是相邻的。
支持任意插入和删除

使用 GetDescendant 方法，始终可以在任意给定节点的右侧、左侧或任意两个同级节点之间生成同级节点。在层次结构中插入或删除任意数目的节点时，该比较属性保持不变。大多数插入和删除操作都保留了紧凑性属性。但是，对于在两个节点之间执行的插入操作，所产生的 hierarchyid 值的表示形式在紧凑性方面将稍微降低。

hierarchyid 的局限性

该 hierarchyid 数据类型具有以下局限性：

类型为 hierarchyid 的列不会自动表示树。由应用程序来生成和分配 hierarchyid 值，使行与行之间的所需关系反映在这些值中。某些应用程序可能具有 hierarchyid 类型的列，该列指示在另一个表中定义的层次结构中的位置。
由应用程序来管理生成和分配 hierarchyid 值时的并发情况。不能保证列中的 hierarchyid 值是唯一的，除非应用程序使用唯一键约束或应用程序自身通过自己的逻辑来强制实现唯一性。
由 hierarchyid 值表示的层次结构关系不是像外键关系那样强制实现的。可能会出现下面这种层次结构关系而且有时这种关系是合理的：A 具有子级 B，然后删除了 A，导致 B 与一条不存在的记录之间存在关系。如果这种行为不可接受，应用程序在删除父级之前必须先查询其是否有后代。

何时使用 hierarchyid 的替代项

用于表示层次结构数据的两个 hierarchyid 替代项为：

父/子
XML

hierarchyid 通常优于这些替代项。但是，在下面详述的特定情况下，使用这些替代项可能更好。

父/子

使用父/子方法时，每一行都包含对父级的引用。下表定义了一个用于在父/子关系中包含父行和子行的典型表：

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

针对一些常见操作比较父/子与 hierarchyid

使用 hierarchyid进行子树查询时速度明显加快。
使用 hierarchyid进行直接后代查询时速度稍慢。
使用 hierarchyid移动非叶节点时速度明显减慢。
使用 hierarchyid插入非叶节点和插入或移动叶节点具有相同的复杂度。

当存在以下情况时，使用父/子可能更好：

键的大小非常重要。在节点数相同的情况下， hierarchyid 值等于或大于整型系列（smallint、 int、 bigint）的值。这只是在很少情况下使用父/子的一个原因，因为 hierarchyid 在 I/O 局部实用性和 CPU 复杂性方面明显优于使用父/子结构时所需的公用表表达式。
很少跨层次结构的不同部分执行查询。也就是说，通常仅对层次结构中的单个点进行查询。在这些情况下，存储在一起并不重要。例如，如果组织表仅用于为各个雇员处理工资单，则使用父/子更好。
非叶子树移动频繁并且性能非常重要。在父/子表示形式中，更改层次结构中行的位置将影响单个行。使用 hierarchyid 时，更改行的位置将影响 n 行，其中 n 是要移动的子树中的节点数。

如果非叶子树移动频繁并且性能非常重要，但多数移动操作都是在比较明确的层次结构级别上进行的，请考虑将较高和较低的级别拆分成两个层次结构。这样，所有的移动操作都是移到较高层次结构的叶级。例如，假设有一个由服务承载的网站的层次结构。各网站包含许多以分层方式排列的页面。承载的网站可能移动到网站层次结构中的其他位置，但是从属的页面很少会重新排列。这种情况可表示如下：
```
CREATE TABLE HostedSites   
   (  
    SiteId hierarchyid, PageId hierarchyid  
   ) ;  
GO  
```

XML

XML 文档是一个树，因此单个 XML 数据类型实例可以表示一个完整的层次结构。在 SQL Server 中，当创建 XML 索引时，内部不会使用 hierarchyid 值来表示在层次结构中的位置。

当满足以下所有条件时，使用 XML 数据类型会更好：

始终存储并检索整个层次结构。
应用程序以 XML 格式使用数据。
谓词搜索有极大的局限性，并且性能不是特别重要。

例如，如果应用程序跟踪多个组织，始终存储并检索整个组织层次结构，并且不在单个组织内部进行查询，则使用如下形式的表可能较为合适：

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

层次结构数据的索引策略

用于对层次结构数据进行索引的策略有两种：

深度优先

深度优先索引在子树中相邻位置存储行。例如，一位经理管理的所有雇员都存储在其经理的记录附近。

在深度优先索引中，一个节点的子树中的所有节点存储在一起。因此，深度优先索引能高效地响应有关子树的查询，“查找此文件夹及其子文件夹中的所有文件”就是这样的一个示例。
广度优先

广度优先索引将层次结构中每个级别的各行存储在一起。例如，同一经理直属的各雇员的记录存储在相邻位置。

在广度优先索引中，一个节点的所有直属子级存储在一起。因此，广度优先索引在响应有关直属子级的查询方面效率很高，“查找此经理直属的所有雇员”就属于这类查询。

采用深度优先、广度优先还是结合使用这两种索引，以及将哪一种设为聚集键（如果有），取决于上述两种查询类型的相对重要性以及 SELECT 与DML 操作的相对重要性。有关索引策略的详细示例，请参阅 Tutorial: Using the hierarchyid Data Type。

创建索引

GetLevel() 方法可用于创建广度优先排序。在下例中，既创建了广度优先索引，又创建了深度优先索引：

USE AdventureWorks2022;   -- wmimof
GO  
  
CREATE TABLE Organization  
   (  
    BusinessEntityID hierarchyid,  
    OrgLevel as BusinessEntityID.GetLevel(),   
    EmployeeName nvarchar(50) NOT NULL  
   ) ;  
GO  
  
CREATE CLUSTERED INDEX Org_Breadth_First   
    ON Organization(OrgLevel,BusinessEntityID) ;  
GO  
  
CREATE UNIQUE INDEX Org_Depth_First   
    ON Organization(BusinessEntityID) ;  
GO

示例

简单示例

以下示例特意进行了简化，以帮助您入门。首先创建一个表以保存一些地理数据。

CREATE TABLE SimpleDemo  
(
    Level hierarchyid NOT NULL,  
    Location nvarchar(30) NOT NULL,  
    LocationType nvarchar(9) NULL
);

现在插入一些洲、国家/地区、州和城市的数据。

INSERT SimpleDemo  
    VALUES   
('/1/', 'Europe', 'Continent'),  
('/2/', 'South America', 'Continent'),  
('/1/1/', 'France', 'Country'),  
('/1/1/1/', 'Paris', 'City'),  
('/1/2/1/', 'Madrid', 'City'),  
('/1/2/', 'Spain', 'Country'),  
('/3/', 'Antarctica', 'Continent'),  
('/2/1/', 'Brazil', 'Country'),  
('/2/1/1/', 'Brasilia', 'City'),  
('/2/1/2/', 'Bahia', 'State'),  
('/2/1/2/1/', 'Salvador', 'City'),  
('/3/1/', 'McMurdo Station', 'City');

选择数据，从而添加将级别数据转换为易于理解的文本值的列。此查询还按 hierarchyid 数据类型对结果排序。

SELECT CAST(Level AS nvarchar(100)) AS [Converted Level], *   
    FROM SimpleDemo ORDER BY Level;

下面是结果集：

Converted Level  Level     Location         LocationType  
/1/              0x58      Europe           Continent  
/1/1/            0x5AC0    France           Country  
/1/1/1/          0x5AD6    Paris            City  
/1/2/            0x5B40    Spain            Country  
/1/2/1/          0x5B56    Madrid           City  
/2/              0x68      South America    Continent  
/2/1/            0x6AC0    Brazil           Country  
/2/1/1/          0x6AD6    Brasilia         City  
/2/1/2/          0x6ADA    Bahia            State  
/2/1/2/1/        0x6ADAB0  Salvador         City  
/3/              0x78      Antarctica       Continent  
/3/1/            0x7AC0    McMurdo Station  City

请注意，层次结构具有有效的结构，即使其内部不一致。 Bahia 是唯一的州。它作为城市 Brasilia 的对等方出现在层次结构中。同样，McMurdo Station 没有父级国家/地区。用户必须确定此类型的层次结构是否适合于其用途。

添加另一行并选择结果。

INSERT SimpleDemo  
    VALUES ('/1/3/1/', 'Kyoto', 'City'), ('/1/3/1/', 'London', 'City');  
SELECT CAST(Level AS nvarchar(100)) AS [Converted Level], * FROM SimpleDemo ORDER BY Level;

这演示更多可能的问题。 Kyoto 可以作为级别 /1/3/1/ 插入，即使没有父级别 /1/3/。 London 和 Kyoto 具有相同的 hierarchyid值。用户必须再次确定此类型的层次结构是否适合于其用途，并阻止对其用途无效的值。

此外，此表未使用层次结构顶层 '/'。该层被省略，因为没有所有州的公共父级。可以通过添加整个星球来添加一个顶层。

INSERT SimpleDemo  
    VALUES ('/', 'Earth', 'Planet');

相关任务

从父/子迁移到 hierarchyid

大多数树都使用父/子结构来表示。从父/子结构迁移到使用 hierarchyid 的表的最简单方法是，使用临时列或临时表来跟踪各个层次结构级别的节点数。有关迁移父/子表的示例，请参阅教程：使用 hierarchyid 数据类型的第 1 课。

使用 hierarchyid 管理树

尽管 hierarchyid 列不一定表示树，但应用程序可以很容易地确保此列表示树。

生成新的值时，请执行下列操作之一：
- 跟踪父行中的最后一个子级编号。
- 计算最后一个子级。若要高效地执行此操作，需要使用广度优先索引。
通过对列创建可能属于聚集键的唯一索引，强制实现唯一性。若要确保插入的值是唯一的，请执行下列操作之一：
- 检测唯一键冲突故障并重试。
- 确定每个新子节点的唯一性，并将其作为可序列化事务的一部分插入。

使用错误检测的示例

在下例中，示例代码计算新子级的 EmployeeId 值，接着检测有无键冲突，然后返回 INS_EMP 标记以便重新计算新行的 EmployeeId 值：

USE AdventureWorks ;  
GO  
  
CREATE TABLE Org_T1  
   (  
    EmployeeId hierarchyid PRIMARY KEY,  
    OrgLevel AS EmployeeId.GetLevel(),  
    EmployeeName nvarchar(50)   
   ) ;  
GO  
  
CREATE INDEX Org_BreadthFirst ON Org_T1(OrgLevel, EmployeeId);
GO  
  
CREATE PROCEDURE AddEmp(@mgrid hierarchyid, @EmpName nvarchar(50) )   
AS  
BEGIN  
    DECLARE @last_child hierarchyid;
INS_EMP:   
    SELECT @last_child = MAX(EmployeeId) FROM Org_T1   
        WHERE EmployeeId.GetAncestor(1) = @mgrid;
    INSERT INTO Org_T1 (EmployeeId, EmployeeName)  
        SELECT @mgrid.GetDescendant(@last_child, NULL), @EmpName;
-- On error, return to INS_EMP to recompute @last_child  
IF @@error <> 0 GOTO INS_EMP   
END ;  
GO

使用可序列化事务的示例

Org_BreadthFirst 索引可确保确定 @last_child 使用范围查找。除了应用程序可能需要检查的其他错误情况之外，插入后出现重复键冲突表示试图添加具有同一 ID 的多个雇员，因此必须重新计算 @last_child 。以下代码计算可序列化事务中的新节点值：

CREATE TABLE Org_T2  
    (  
    EmployeeId hierarchyid PRIMARY KEY,  
    LastChild hierarchyid,   
    EmployeeName nvarchar(50)   
    ) ;  
GO  
  
CREATE PROCEDURE AddEmp(@mgrid hierarchyid, @EmpName nvarchar(50))   
AS  
BEGIN  
DECLARE @last_child hierarchyid  
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE  
BEGIN TRANSACTION   
  
SELECT @last_child  =  EmployeeId.GetDescendant(LastChild,NULL)
FROM Org_T2
WHERE EmployeeId = @mgrid

UPDATE Org_T2 SET LastChild = @last_child  WHERE EmployeeId = @mgrid

INSERT Org_T2 (EmployeeId, EmployeeName)   
    VALUES(@last_child, @EmpName)  
COMMIT  
END ;

下面的代码使用三行数据填充表，并返回结果：

INSERT Org_T2 (EmployeeId, EmployeeName)   
    VALUES(hierarchyid::GetRoot(), 'David') ;  
GO  
AddEmp 0x , 'Sariya'  
GO  
AddEmp 0x58 , 'Mary'  
GO  
SELECT * FROM Org_T2

下面是结果集。

EmployeeId LastChild EmployeeName  
---------- --------- ------------  
0x        0x58       David  
0x58      0x5AC0     Sariya  
0x5AC0    NULL       Mary

强制表示树

以上示例说明了应用程序如何确保树得到维护。若要通过使用约束强制表示树，创建定义各节点父级的计算列时可以为它创建一个反过来约束主键 ID 的外键。

CREATE TABLE Org_T3  
(  
   EmployeeId hierarchyid PRIMARY KEY,  
   ParentId AS EmployeeId.GetAncestor(1) PERSISTED    
      REFERENCES Org_T3(EmployeeId),  
   LastChild hierarchyid,   
   EmployeeName nvarchar(50)  
)  
GO

当用于维护层次结构树的不可信代码对表拥有直接 DML 访问权限时，将优先采用这种强制关系的方法。但是，这种方法可能会降低性能，因为必须针对每个 DML 操作检查约束。

使用 CLR 查找祖先

查找级别最低的共同祖先就是一项涉及层次结构中两个节点的常用操作。可以用 Transact-SQL 或 CLR 编写此操作，因为它们都提供 hierarchyid 类型。建议用 CLR，因为用它时查找速度会更快。

使用下面的 CLR 代码来列出祖先，并查找级别最低的共同祖先：

using System;  
using System.Collections;  
using System.Text;  
using Microsoft.SqlServer.Server;  // SqlFunction Attribute
using Microsoft.SqlServer.Types;   // SqlHierarchyId
  
public partial class HierarchyId_Operations  
{  
    [SqlFunction(FillRowMethodName = "FillRow_ListAncestors")]
    public static IEnumerable ListAncestors(SqlHierarchyId h)
    {  
        while (!h.IsNull)  
        {  
            yield return (h);  
            h = h.GetAncestor(1);  
        }  
    }  
    public static void FillRow_ListAncestors(
        Object obj,
        out SqlHierarchyId ancestor
        )
    {  
        ancestor = (SqlHierarchyId)obj;  
    }  
  
    public static HierarchyId CommonAncestor(
        SqlHierarchyId h1,
        HierarchyId h2
        )  
    {  
        while (!h1.IsDescendantOf(h2))  
            h1 = h1.GetAncestor(1);  
  
        return h1;  
    }  
}

若要在以下 Transact-SQL 示例中使用 ListAncestor 和 CommonAncestor 方法，请在 SQL Server 中通过执行如下代码生成 DLL 并创建 HierarchyId_Operations 程序集：

CREATE ASSEMBLY HierarchyId_Operations   
    FROM '<path to DLL>\ListAncestors.dll';
GO

列出祖先

创建节点的祖先列表是一项常用操作，例如可用于显示组织中的职位。此操作的其中一种实现方式就是使用表值函数和上面定义的 HierarchyId_Operations 类：

使用 Transact-SQL：

CREATE FUNCTION ListAncestors (@node hierarchyid)  
RETURNS TABLE (node hierarchyid)  
AS  
EXTERNAL NAME HierarchyId_Operations.HierarchyId_Operations.ListAncestors  
GO

用法示例：

DECLARE @h hierarchyid  
SELECT @h = OrgNode   
FROM HumanResources.EmployeeDemo    
WHERE LoginID = 'adventure-works\janice0' -- /1/1/5/2/  
  
SELECT LoginID, OrgNode.ToString() AS LogicalNode  
FROM HumanResources.EmployeeDemo AS ED  
JOIN ListAncestors(@h) AS A   
   ON ED.OrgNode = A.Node  
GO

查找级别最低的共同祖先

使用上面定义的 HierarchyId_Operations 类创建以下 Transact-SQL 函数，以便查找涉及层次结构中两个节点的最低级别的共同上级：

CREATE FUNCTION CommonAncestor (@node1 hierarchyid, @node2 hierarchyid)  
RETURNS hierarchyid  
AS  
EXTERNAL NAME HierarchyId_Operations.HierarchyId_Operations.CommonAncestor  
GO