使用 hierarchyid 数据类型(数据库引擎)

hierarchyid 数据类型是系统提供的。使用 hierarchyid 作为数据类型来创建具有层次结构的表,或引用位于另一个位置的数据层次结构。使用 hierarchyid 函数可利用 Transact-SQL 查询和处理分层数据。

分层数据定义为一组通过层次结构关系互相关联的数据项。在层次结构关系中,一个数据项是另一个项的父级。分层数据在数据库中很常见。这方面的例子有:

  • 组织结构

  • 文件系统

  • 项目中的一组任务

  • 语言术语分类

  • 网页间链接图

hierarchyid 是 SQL Server 2008 中新增的类型,它使得存储和查询分层数据更为容易。hierarchyid 最适宜表示树,树是最常见的分层数据类型。

hierarchyid 的关键属性

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

  • 非常紧凑

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

  • 按深度优先顺序进行比较

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

  • 支持任意插入和删除

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

hierarchyid 的局限性

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

  • 类型为 hierarchyid 的列不会自动表示树。由应用程序来生成和分配 hierarchyid 值,使行与行之间的所需关系反映在这些值中。一些应用程序甚至可能不需要用类型为 hierarchyid 的列来表示树。可能这些值为对其他表中定义的层次结构中位置的引用。

  • 由应用程序来管理生成和分配 hierarchyid 值时的并发情况。不能保证列中的 hierarchyid 值是唯一的,除非应用程序使用唯一键约束或应用程序自身通过自己的逻辑来强制实现唯一性。

  • 由 hierarchyid 值表示的层次结构关系不是像外键关系那样强制实现的。可能会出现下面这种层次结构关系而且有时这种关系是合理的:A 具有子级 B,然后删除了 A,导致 B 与一条不存在的记录之间存在关系。如果这种行为不可接受,应用程序在删除父级之前必须先查询其是否有后代。

索引策略

用于对分层数据进行索引的策略有两种:

  • 深度优先

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

节点存储在一起。

  • 广度优先

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

每个层次结构级别都存储在一起。

示例

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

USE AdventureWorks ; 
GO

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

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

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

CREATE UNIQUE INDEX Org_Depth_First 
ON Organization(EmployeeID) ;
GO

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

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

何时使用 hierarchyid 的替代项

用于表示分层数据的两个 hierarchyid 替代项为:

  • 父/子

  • XML

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

父/子

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

USE AdventureWorks ;
GO

CREATE TABLE ParentChildOrg
   (
    EmployeeID int PRIMARY KEY,
    ManagerId int REFERENCES ParentChildOrg(EmployeeID),
    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

从父/子迁移到 hierarchyid

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

hierarchyid 的查询转换

为了在查询层次结构时达到最佳性能,SQL Server 会自动对涉及 hierarchyid 的查询执行三次转换。在转换后的查询的显示计划输出中可以看到这些转换的结果。

IsDescendantOf 转换成范围查找

假定 E 为一个列或变量,E.IsDescendantOf(c) 会转换成范围查找。这样会显著降低查找后代的成本。如果存在对 E 的深度优先索引,则由于 E 的所有后代存储在一起,因此这种转换会有所帮助。例如,代码段 EmployeeId.IsDescendantOf(@value) 将作为 EmployeeId >= @Value AND EmployeeId <= @Value.DescendantLimit() 执行。DescendantLimit 是一种用于确定节点所有可能后代的最小上限的内部方法。请注意,@value 不一定是参数。它可以是列,可能来自联接条件。

GetAncestor 转换成范围扫描和剩余谓词

GetAncestor(n) 提供节点的第 n 级祖先。当需要两个节点之间的精确关系(父级、子级、祖父级等)时,这种方法比更常见的 IsDescendantOf 有用。

例如,执行下面的查询可查找直接经理为 @value 的所有雇员:

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

对于 @value 的后代,这将转换为范围扫描,原始谓词转换为剩余谓词。上面的代码转换成如下内容:

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

产生的效果是将扫描范围限制在 @value 的子树。

GetAncestor 转换为使用广度优先索引的索引查找

在上面的查询中,如果 @value 处于树的较高级别,则上面的优化不能显著减少扫描的行数。当有关第 n 级祖先的查询较常见时,应用程序应按前文所述创建广度优先索引。

当存在广度优先索引时,上面的查询进一步转换成如下内容:

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

最后一行(包含 GetLevel 方法)在广度优先索引中变成索引查找。如果 EmployeeId 为聚集键,则它会成为广度优先索引中的第二列,并且两个谓词会变为一个索引查找,用来精确指定 @value 的 n 个存储在一起的直接下属。

GetAncestor 转换并不仅限于查询直接父级。GetAncestor 的参数可以为任何变量或常量。