Id-ParentId 和 HierarchyId 方法在分层数据中的组合
5.00/5 (13投票s)
结合 Id-ParentId 和 HierarchyId 方法以按层级和字母顺序存储和检索数据。
引言
层次和字母排序
对数据进行分层和字母排序 意味着使用 深度优先搜索算法 对树进行排序，并按照其名称的字母顺序选择具有相同父节点的节点。
层次排序结合嵌套级别是一种很好的方法，可以使用扁平的对象列表模拟展开的树或书籍目录，而无需构建对象树。
只需获取记录，按层次和字母顺序对其进行排序，然后将每条记录缩进 n 次（其中 n 是嵌套级别），您将获得用于 UI 和报告的展开树。
两种方法
有几种方法可以构建关系数据库来存储层次数据。其中一种更常用的方法是 Id-ParentId 方法。
Id-ParentId 方法有一些缺点，这使得有必要寻找存储层次数据的替代方法。
在 Id-ParentId 方法中，最困难和最昂贵的任务是那些需要递归方法的任务，例如：
- 查找所有后代
- 查找所有祖先
- 计算嵌套级别
- 先按层次，再按字母顺序排序扁平记录
为了应对这些困难，Microsoft 从 SQL Server 2008 版本开始添加了 HierarchyId 数据类型。
HierarchyId 数据类型
- 有助于无需递归即可查找后代和祖先
- 具有快速的
GetLevel()方法 - 包含有关节点在层次结构中位置的信息
- 包含有关节点在其父节点下的子节点中的顺序的信息
如果您需要在 HierarchyId 上构建聚集索引，那么所有节点记录将物理地按照它们最常被获取的顺序存储。
但 HierarchyId 数据类型仍然存在缺点，这些缺点是其有用属性的权衡：
- 无法将
HierarchyId用作父级的外部键，即自引用
（实际上，父级的外部键可以用 PERSISTED REFERENCES 代替，如 本文 所述，但这种解决方案的所有优缺点仍在等待研究人员的探索） - 为添加和更改的记录生成
HierarchyId以保持所需顺序的方法很困难，SQL Server 不会自动执行此操作，这取决于程序员来管理它 - 将
HierarchyId用作主键和外键很困难：它可能会定期更改 - 它在 JavaScript（例如）中没有对应的类型
那么该选择什么：Id-ParentId 还是 HierarchyId？
解决这种选择困境的一个可接受的方案可能是结合两种方法：Id-ParentId 和 HierarchyId。
这种组合将使我们能够
- 使用
Id作为整数，递增且不可更改的主键 - 使用
ParentId作为自引用外键 - 使用
HierarchyId使记录物理上按层次和字母顺序排序
本文描述了如何 объединить 两种方法并确保其正常运行。
关于 HierarchyId 的一些事实
本文和源代码中的列名和字段名
Hid—HierarchyId数据类型的列HidPath—HierarchyId的人类可读路径的string列HidCode—HierarchyId的二进制表示，转换为string且不带前导0x
转换为人类可读格式
HierarchyId 数据类型是编码为二进制格式的实体化路径。它可以使用 ToString() 方法解码为人类可读的 string 路径
select Hid, Hid.ToString() as HidPath, Hid.GetLevel() as Level from Folders order by Hid;
Hid HidPath Level
----------- -------------- ------
0x / 0
0x58 /1/ 1
0x5AC0 /1/1/ 2
0x5AD6 /1/1/1/ 3
0x5AD6B0 /1/1/1/1/ 4
0x5AD6B580 /1/1/1/1/1/ 5
0x5AD6B680 /1/1/1/1/2/ 5
0x5AD6B780 /1/1/1/1/3/ 5
0x5AD6D0 /1/1/1/2/ 4
0x5AD6D580 /1/1/1/2/1/ 5
0x5AD6D680 /1/1/1/2/2/ 5
0x5AD6D780 /1/1/1/2/3/ 5
...
-- Note: ToString() and GetLevel() are case sensitive!!!
从人类可读格式转换
从 string 路径到二进制格式的相反操作也有效
declare @Hid hierarchyid = '/1/1/1/1/3/';
select @Hid
Results
-------------------------------------------------
0x5AD6B780
以上是隐式转换。HierarchyId 具有显式的 Parse() 方法，尽管调用格式有点奇怪
declare @Hid hierarchyid = hierarchyid::Parse('/1/1/1/1/3/'); -- Parse() is case sensitive!!!
select @Hid
Results
-------------------------------------------------
0x5AD6B780
路径的巧妙编号系统
关于 HierarchyId 有趣的一点是它如何管理插入到另外两个节点之间的新节点的编号。
为了获取新节点的 Hid，HierarchyId 使用父 Hid 的 GetDescendant() 方法，并使用两个新节点要插入的节点之间的 Hid
declare @Parent hierarchyid = 0x;
print @Parent.GetDescendant('/1/', '/2/').ToString() -- /1.1/
print @Parent.GetDescendant('/1/', '/1.1/').ToString() -- /1.0/
print @Parent.GetDescendant('/1/', '/1.0/').ToString() -- /1.-1/
print @Parent.GetDescendant('/1/', '/1.-1/').ToString() -- /1.-2/
print @Parent.GetDescendant('/1.1/', '/2/').ToString() -- /1.2/
print @Parent.GetDescendant('/1.2/', '/2/').ToString() -- /1.3/
print @Parent.GetDescendant('/1.3/', '/2/').ToString() -- /1.4/
print @Parent.GetDescendant('/1.3/', '/1.4/').ToString() -- /1.3.1/
print @Parent.GetDescendant_
('/1.2.3.4.5.6.7.8/', '/1.2.3.4.5.6.7.9/').ToString() -- /1.2.3.4.5.6.7.8.1/
-- by the way
declare @Hid hierarchyid = '/1.2.3.4.5.6.7.8.1/';
select @Hid; -- 0x63A08A49A85258
declare @Hid hierarchyid = '/-1.-2.-3.-4.-5.-6.-7.-8.-1234567890/';
select @Hid; -- 0x41F8F87A3C1D8E87216D9A81A73A
-- special cases with null
print @Parent.GetDescendant(null, null).ToString() -- /1/
print @Parent.GetDescendant('/1/', null).ToString() -- /2/
print @Parent.GetDescendant(null, '/1/').ToString() -- /0/
为什么需要二进制编码？
如果我们能够构建 string 路径，为什么还需要这个 HierarchyId 二进制编码？
我们能否仅仅通过这个字符串路径来排序层次数据？
看看这个例子：
select hierarchyid::Parse('/1/') as Hid, '/1/' as HidPath union all
select hierarchyid::Parse('/2/') , '/2/' union all
select hierarchyid::Parse('/10/') , '/10/'
order by HidPath;
Results
-------------------------------------------------
Hid HidPath
----- --------
0x58 /1/
0xAA /10/
0x68 /2/
The same query but ordered by Hid makes the right sorting:
Hid HidPath
----- --------
0x58 /1/
0x68 /2/
0xAA /10/
Microsoft 使用复杂的 HierarchyId 算法来编码 string 路径，以便它可以仅通过 Hid 列值用于分层排序。
解决方案
主从
所以让我们将 Id-ParentId 自引用方法与 HierarchyId 结合起来。
Id-ParentId 部分将负责 Id 主键、自引用 ParentId 外键，并成为主导或主控。
HierarchyId 部分将是一个计算字段或从属。
当然，将 Hid 作为持久化计算字段是反规范化。但这是一种有意识的步骤，也是为了 HierarchyId 优势而做出的妥协。
计算 HierarchyId 并使其保持协调状态的最佳地点和时间是存储过程，并在保存节点时进行。
用户目录实验
让我们想象我们有一个多用户应用程序，每个用户都有自己的 Catalog。
此 Catalog 将信息存储在分层 Folders 中。
这些 Folders 的表可能如下所示
create table dbo.Folders
(
UserId int not null ,
Hid hierarchyid not null ,
Id int not null identity,
ParentId int null ,
Name nvarchar(50) not null ,
constraint CU_Folders unique clustered (UserId asc, Hid asc),
constraint PK_Folders primary key nonclustered (Id asc),
constraint FK_Folders_UserId foreign key (UserId) references dbo.Users (Id),
constraint FK_Folders_ParentId foreign key (ParentId) references dbo.Folders (Id)
constraint CH_Folders_ParentId check _
(Hid = 0x and ParentId is null or Hid <> 0x and ParentId is not null)
);
请注意，聚集索引是建立在 UserId 和 Hid 上的，但主键是建立在 Id 列上的。
这允许将用户 Folders 的所有记录物理上按层次排序。同时，将整数主键用作其他表和 DTO 的外键。
众所周知，基于 HierarchyId 构建的层次结构只能有一个根。
由于聚集键是 UserId 和 Hid 列的组合，因此表 dbo.Folders 可以为每个用户拥有一个根。
根节点是强制性的，每个用户的目录都必须有一个，所以根节点主要是一个系统记录，用户不能编辑。
一旦根节点是系统记录，所有其他节点都必须有一个父节点，并且 ParentId 不能为空。
最佳计算位置
正如微软 此处 所述：“应用程序有责任生成和分配 HierarchyId 值，以便行之间所需的关系反映在这些值中。”
在这种情况下，创建并保持层次数据完整性和一致性的最佳方法是始终使用相同的存储过程来插入和更新文件夹节点。
代表保存 Folder 的用户定义表类型可以作为 SaveFolder 存储过程的参数
create type dbo.FolderTableType as table
(
Id int not null primary key clustered,
ParentId int not null ,
Name nvarchar(50) not null
);
下面是 SaveFolder 存储过程本身
create procedure dbo.SaveFolder
@Folder dbo.FolderTableType readonly
as
begin
set nocount on;
begin -- variable declaration
declare
@ParamId int ,
@ParentId int ,
@UserId int ,
@ParentHid hierarchyid ,
@StartTranCount int ,
@OldHid hierarchyid ,
@NewHid hierarchyid ;
declare @FolderIds table (
InsertedId int not null,
OldHid hierarchyid null,
NewHid hierarchyid null
);
end;
begin try
set @StartTranCount = @@trancount;
if @StartTranCount = 0
begin
set transaction isolation level serializable;
begin transaction;
end;
begin -- init variables and lock parent for update
select
@ParamId = Id,
@ParentId = ParentId
from
@Folder;
select
@UserId = UserId,
@ParentHid = Hid
from
dbo.Folders
where
Id = @ParentId;
end;
begin -- save the @Folder
merge into dbo.Folders as target
using
(
-- full join in this 'select' allows to see picture
-- as if the change already applied
-- thus coalesce(t.Id, f.Id) take new value if t.Id exists
-- and old value if not
select
-- LAG and LEAD functions help to find the previous
-- and next Hid values if to sort by Name
Hid = @ParentHid.GetDescendant (
LAG (case when t.Id is null then f.Hid end)
over(order by coalesce(t.Name, f.Name)),
LEAD(case when t.Id is null then f.Hid end)
over(order by coalesce(t.Name, f.Name))
),
Id = coalesce( t.Id , f.Id ),
ParentId = coalesce( t.ParentId , f.ParentId ),
Name = coalesce( t.Name , f.Name )
from
(select * from dbo.Folders where ParentId = @ParentId) f
full join @Folder t on t.Id = f.Id
)
-- for LAG and LEAD functions we need all children of the @ParentId
-- but for merge we need the Folder where source.Id = @ParamId
as source on source.Id = @ParamId and source.Id = target.Id
-- target.UserId = @UserId here just to make sure that
-- we do not reparent a Folder to another user
when matched and target.UserId = @UserId then
update set
Hid = source.Hid ,
Name = source.Name ,
ParentId = source.ParentId
-- source.Id = 0 here just to make sure that we insert a new Folder
-- and not already deleted one
-- not matched Id can be deleted by another user and we can try to add it again
when not matched by target and source.Id = 0 then
insert (
UserId ,
Hid ,
ParentId ,
Name )
values (
@UserId ,
source.Hid ,
source.ParentId ,
source.Name )
output
inserted.Id ,
deleted.Hid ,
inserted.Hid
into @FolderIds (
InsertedId ,
OldHid ,
NewHid );
end;
begin -- reparent children
-- saving folder might change its ParentId
-- in that case Hid of all its children should reflect the change also
select top 1 @OldHid = OldHid, @NewHid = NewHid from @FolderIds;
if @OldHid <> @NewHid
update dbo.Folders set
Hid = Hid.GetReparentedValue(@OldHid, @NewHid)
where
UserId = @UserId
and Hid.IsDescendantOf(@OldHid) = 1;
end;
if @StartTranCount = 0 commit transaction;
end try
begin catch
if xact_state() <> 0 and @StartTranCount = 0 rollback transaction;
declare @ErrorMessage nvarchar(4000) = dbo.GetErrorMessage();
raiserror (@ErrorMessage, 16, 1);
return;
end catch;
end;
如果只通过上述存储过程保存每个 Folder，那么 Hid 列将始终拥有实际且一致的信息。
按层次顺序获取文件夹及其后代
因此，以下存储过程获取一个 Folder 及其所有后代，并按层次顺序和字母顺序对它们进行排序，就像它们是一个展开的树一样
create procedure dbo.GetFolderWithSubFolders
@FolderId int
as
begin
set nocount on;
select
d.Id ,
d.ParentId ,
d.Name ,
[Level] = d.Hid.GetLevel(),
HidCode = dbo.GetHidCode(d.Hid),
HidPath = d.Hid.ToString()
from
dbo.Folders f
inner join dbo.Folders d on d.UserId = f.UserId and d.Hid.IsDescendantOf(f.Hid) = 1
where
f.Id = @FolderId
order by
d.Hid;
end;
例如
exec dbo.GetFolderWithSubFolders @FolderId = 40
Id ParentId Name Level HidCode HidPath
----- --------- ----- ------ ---------- ------------
40 13 3A 3 5AD6 /1/1/1/
121 40 4A 4 5AD6B0 /1/1/1/1/
364 121 5A 5 5AD6B580 /1/1/1/1/1/
365 121 5B 5 5AD6B680 /1/1/1/1/2/
366 121 5C 5 5AD6B780 /1/1/1/1/3/
122 40 4B 4 5AD6D0 /1/1/1/2/
367 122 5A 5 5AD6D580 /1/1/1/2/1/
368 122 5B 5 5AD6D680 /1/1/1/2/2/
369 122 5C 5 5AD6D780 /1/1/1/2/3/
123 40 4C 4 5AD6F0 /1/1/1/3/
370 123 5A 5 5AD6F580 /1/1/1/3/1/
371 123 5B 5 5AD6F680 /1/1/1/3/2/
372 123 5C 5 5AD6F780 /1/1/1/3/3/
HidCode 有什么用？
如上所述，HidCode 是 HierarchyId 的二进制表示，转换为 varchar 且不带前导 0x。
这是 dbo.GetHidCode 标量 SQL 函数
create function dbo.GetHidCode
(
@Hid hierarchyid
)
returns varchar(1000)
as
begin
return replace(convert(varchar(1000), cast(@Hid as varbinary(892)), 2), '0x', '');
end;
HidCode 字符串可以在客户端用于按层次排序扁平的 Folders 列表。
完美主义者章节
上述 Hid 计算方法效果很好，但它有一个小缺点。
-- imagine you have two sibling folders
Id ParentId Name Level HidCode HidPath
----- --------- ----- ------ ---------- ------------
364 121 5A 5 5AD6B580 /1/1/1/1/1/
365 121 5B 5 5AD6B680 /1/1/1/1/2/
-- and you want to insert a new folder
Id ParentId Name
----- --------- -----
0 121 5Aaa
-- the result will be
Id ParentId Name Level HidCode HidPath
----- --------- ----- ------ ---------- ------------
364 121 5A 5 5AD6B580 /1/1/1/1/1/
1234 121 5Aaa 5 5AD6B62C /1/1/1/1/1.1/
365 121 5B 5 5AD6B680 /1/1/1/1/2/
请查看 HidPath 中的此序列：1 -> 1.1 -> 2 而不是 1 -> 2 -> 3
随着时间的推移，这种丑陋的序列可能会变得更加丑陋。
如果你觉得没问题，那就跳过这一章。
但对于其他人，我建议再提供一种保持层次数据最新状态的选项。
这是一个存储过程，它重新计算 HierarchyId，以便路径由连续序列中的整数组成。
create procedure dbo.SaveFolderWithHidReculc
@Folder dbo.FolderTableType readonly
as
begin
set nocount on;
begin -- variable declaration
declare
@ParentId int ,
@UserId int ,
@ParentHid hierarchyid ,
@ParentHidStr varchar(1000) ,
@StartTranCount int ,
@OldParentId int ,
@OldParentHid hierarchyid ;
declare @FolderIds table (
InsertedId int not null,
OldParentId int null,
OldParentHid hierarchyid null
);
end;
begin try
set @StartTranCount = @@trancount;
if @StartTranCount = 0
begin
set transaction isolation level serializable;
begin transaction;
end;
begin -- init variables and lock parent for update
select @ParentId = ParentId from @Folder;
select
@UserId = UserId ,
@ParentHid = Hid ,
@ParentHidStr = cast(Hid as varchar(1000))
from
dbo.Folders
where
Id = @ParentId;
end;
begin -- merge calculated hierarchical data with existing folders
merge into dbo.Folders as target
using
(
select
Hid = cast(concat(@ParentHidStr, -1, '/') as varchar(1000)),
Id ,
ParentId ,
Name
from
@Folder
)
as source on source.Id = target.Id
when matched and target.UserId = @UserId then
update set
ParentId = source.ParentId ,
Name = source.Name
when not matched by target and source.Id = 0 then
insert (
UserId ,
Hid ,
ParentId ,
Name )
values (
@UserId ,
source.Hid ,
source.ParentId ,
source.Name )
output
inserted.Id,
deleted.ParentId,
deleted.Hid.GetAncestor(1)
into
@FolderIds (
InsertedId ,
OldParentId ,
OldParentHid );
end
begin -- reculculate SubFolder Hids
select top 1
@OldParentId = OldParentId ,
@OldParentHid = OldParentHid
from
@FolderIds;
exec dbo.ReculcSubFolderHids @UserId, @ParentId, _
@ParentHid, @OldParentId, @OldParentHid ;
end;
if @StartTranCount = 0 commit transaction;
end try
begin catch
if xact_state() <> 0 and @StartTranCount = 0 rollback transaction;
declare @ErrorMessage nvarchar(4000) = dbo.GetErrorMessage();
raiserror (@ErrorMessage, 16, 1);
return;
end catch;
end;
这里的诀窍是在保存 @Folder 后调用 RecalcSubFolderHids 存储过程
create procedure dbo.ReculcSubFolderHids
@UserId int ,
@ParentId int ,
@ParentHid hierarchyid ,
@OldParentId int = null,
@OldParentHid hierarchyid = null
as
begin
declare @ParentHidStr varchar(1000) = cast(@ParentHid as varchar(1000));
declare @OldParentHidStr varchar(1000) = cast(@OldParentId as varchar(1000));
with Recursion as
(
select
Id ,
ParentId ,
Name ,
OldHid = cast(Hid as varchar(1000)),
NewHid = cast(
concat(
case when ParentId = @ParentId then @ParentHidStr _
else @OldParentHidStr end,
row_number() over (order by Name, Id),
'/'
)
as varchar(1000)
)
from
dbo.Folders
where
ParentId in (@ParentId, @OldParentId)
union all
select
Id = f.Id ,
ParentId = f.ParentId ,
Name = f.Name ,
OldHid = cast(f.Hid as varchar(1000)),
NewHid = cast(
concat(
r.NewHid,
row_number() over _
(partition by f.ParentId order by f.Name, f.Id),
'/'
)
as varchar(1000)
)
from
Recursion r
inner join dbo.Folders f on f.ParentId = r.Id
where
r.OldHid <> r.NewHid
)
update f set
Hid = r.NewHid
from
dbo.Folders f
inner join Recursion r on r.Id = f.Id and f.Hid <> r.NewHid
where
f.UserId = @UserId;
end;
上述存储过程计算的路径由连续的整数序列组成。
-- So the result of the example in the section beginning with SaveFolderWithHidReculc will be
Id ParentId Name Level HidCode HidPath
----- --------- ----- ------ ---------- ------------
364 121 5A 5 5AD6B580 /1/1/1/1/1/
1234 121 5Aaa 5 5AD6B680 /1/1/1/1/2/
365 121 5B 5 5AD6B780 /1/1/1/1/3/
这种方法也有缺点。当重新计算的分支节点数不超过大约10,000个时，计算时间不超过一秒，效果很好。100,000个节点的重新计算可能需要15秒或更长时间。
在 C# 中读取树
已实现的 Id-ParentId 引用允许在 C# 中构建 Folders 树。
此外，一旦 Folders 按层次排序，可以通过对 Folders 的扁平列表进行一次迭代来构建树。
假设我们在 C# 中有一个 Folder 类
public class Folder
{
public Int32 Id { get; set; }
public Int32? ParentId { get; set; }
public String Name { get; set; }
public IList<Folder> SubFolders { get; set; }
}
因此，以下方法通过对按层次排序的 Folder 列表进行一次遍历来构建树
public static IList<Folder> ConvertHierarchicallySortedFolderListToTrees
(IEnumerable<Folder> folders)
{
var parentStack = new Stack<Folder>();
var parent = default(Folder);
var prevNode = default(Folder);
var rootNodes = new List<Folder>();
foreach (var folder in folders)
{
if (parent == null || folder.ParentId == null)
{
rootNodes.Add(folder);
parent = folder;
}
else if (folder.ParentId == parent.Id)
{
if (parent.SubFolders == null)
parent.SubFolders = new List<Folder>();
parent.SubFolders.Add(folder);
}
else if (folder.ParentId == prevNode.Id)
{
parentStack.Push(parent);
parent = prevNode;
if (parent.SubFolders == null)
parent.SubFolders = new List<Folder>();
parent.SubFolders.Add(folder);
}
else
{
var parentFound = false;
while(parentStack.Count > 0 && parentFound == false)
{
parent = parentStack.Pop();
if (folder.ParentId != null && folder.ParentId.Value == parent.Id)
{
parent.SubFolders.Add(folder);
parentFound = true;
}
}
if (parentFound == false)
{
rootNodes.Add(folder);
parent = folder;
}
}
prevNode = folder;
}
return rootNodes;
}
上述方法比以下用于未排序 Folder 列表的方法快两倍
public static IList<Folder> ConvertHierarchicallyUnsortedFolderListToTrees
(IEnumerable<Folder> folders)
{
var dictionary = folders.ToDictionary(n => n.Id, n => n);
var rootFolders = new List<Folder>();
foreach (var folder in dictionary.Select(item => item.Value))
{
Folder parent;
if (folder.ParentId.HasValue &&
dictionary.TryGetValue(folder.ParentId.Value, out parent))
{
if (parent.SubFolders == null)
parent.SubFolders = new List<Folder>();
parent.SubFolders.Add(folder);
}
else
{
rootFolders.Add(folder);
}
}
return rootFolders;
}
两种方法都可以构建多个根，因此返回类型是 IList<Folder>。当您需要从树中获取几个分离的分支或几个独立的树时，这很有用。
关于源代码
附加的存档包含在 Visual Studio 2015 中创建的 Hierarchy 解决方案，
其中包括两个项目
Hierarchy.DB- 用于为 SQL Server 2016 创建数据库的 SSDT 项目Hierarchy.Tests- 用于调用存储库方法并查看结果的测试项目
该解决方案包含以下示例：
- 如何通过
Id获取带有HidCode、HidPath和从根Folder的完整路径的Folder - 如何获取
Folder的直接子文件夹 - 如何将
Folder及其所有后代作为扁平列表和树获取 - 如何将
Folder及其所有父级作为扁平列表和树获取 - 如何动态计算
Hid添加新Folder - 如何编辑
Folder并保持正确的层次和字母顺序 - 如何重新分配
Folder的父级 - 在编辑方法中将Folder分配给另一个Parent - 如何删除
Folder及其所有后代 - 如何按
Name查找Folders并从找到的Folders构建分支到根，就像在 Visual Studio 的搜索解决方案资源管理器中实现的那样
为了安装数据库并运行测试，请将文件 Hierarchy.DB.publish.xml 和 App.config 中的连接字符串更改为您的。
数据库项目包含 dbo.GenerateFolders 存储过程，用于为测试生成分层数据。此生成在数据库发布阶段自动进行。
历史
- 2017年6月21日
- 初次发表