如何在 SQL Server 中有效地合并两个层次结构？

Question

我有两个带有 Hierarchyid 字段的表，其中一个是临时表，其中包含需要合并到另一个中的新数据（即，需要添加到主树中的一组节点，其中一些可能已经是那里）。

除了定义树结构（父/子关系）的hierarchyid 列之外。每个表都有一个单独的列，其中包含唯一标识每个节点的节点标识符。也就是说，判断暂存表中的节点是否已在主表中的方法是通过节点 ID，而不是通过 hierarchyid 列。

必须执行的处理看起来像这样：

For each row, RS, in the staging table:
    If there is not already a row with the same Id as RS in the main table:
         Find the parent, PS, of the staging row
         Find the row, PM, in the main table that has the same node ID as PS
         Create a new child, RM of row PM
         Set PM's ID equal to the ID of RS

重要的是，只有当临时表中的树按广度优先顺序排序/遍历时，这种方法才有效 - 这样当遇到 RS 时，它是保证其父 PS 在主表中已经有相应的行。

到目前为止，我能看到在 SQL Server 中实现此目的的唯一方法是在临时表（已排序）上使用游标，并为每一行调用一个存储过程，该存储过程基本上完全执行上述操作，并使用 SELECT 完成MAX() 查找已作为 PM 的子级存在的最高层级 ID，以便可以唯一地添加该子级。

不过，这是一种效率极低的方法，而且对于我的目的来说太慢了。还有更好的办法吗？

作为背景，这是我正在做的可行性检查。我需要弄清楚是否可以在 SQL Server 中快速执行此操作。如果事实证明我不能，我将不得不在数据库之外以另一种方式进行。树的合并是问题域所固有的（实际上，在某种意义上是），因此以不同的方式构建数据或采取更广泛的视角并试图以某种方式完全避免执行此操作是不可行的一个选项。

更新

根据要求，这是一个具体示例。

表“staging”和“main”都具有相同的两列：

   hierarchy_id of type hierarchyid
   node_id of type bigint

初始内容

main：

 hierarchy_id    node_id
 /1/             1
 /1/1/           2
 /1/2/           3
 /1/3/           4

staging：

 hierarchy_id    node_id
 /1/             1
 /1/1/           3
 /1/2/           5
 /1/1/1/         6

所需内容

main：

 hierarchy_id    node_id
 /1/             1
 /1/1/           2
 /1/2/           3
 /1/3/           4
 /1/4/           5
 /1/2/1/         6

请注意，staging 表中的节点为 Hierarchy_id / 1/1/ 与目标表中的 hiearchy_id /1/2/ 相对应（这就是为什么 node_id 很重要 - 不能只复制 hierarchy_id 值）。另请注意，node_id 6 的新节点将作为正确父节点（node_id 3 的节点）的子节点添加，这就是 hierarchy_id 很重要的原因 - 它定义任何新节点的树结构（父/子关系）。任何解决方案都需要考虑这两方面。

Answer 1

以这种方式建模层次结构会导致问题。 hierarchy_id 列违反了第一范式，如果您不进行序列化/瓶颈访问，合并过程将很容易出现更新异常。

您应该考虑一个只有node_id和parent_id的表，看看它如何简化您的合并问题

node_id   parent_id
1         NULL
2         1
3         2
4         3

node_id   parent_id
1         NULL
3         1
5         2
6         1

您可以对此使用递归查询，您可能会惊讶于执行计划的效率有多高。如果您必须拥有扁平化层次结构列，您可能可以使用递归查询创建索引视图。

Answer 2

我们一直在开发需要类似解决方案的产品。经过对此方法和其他方法的大量研究后，我们得出结论：hierarchyID 方法不适合我们。

因此，作为对您问题的直接回答：使用这种方法没有更好的方法来做到这一点。

查看嵌套集模型和邻接列表模型。

对于这一特定的设计挑战，这两种方法都是更加优雅和高效的解决方案。

编辑：
事后想想，如果您没有使用 SQL，那么使用非关系数据库可以更好地解决这个问题。
我们不能走这条路，因为没有人在设计非关系数据库方面拥有足够的专业知识，但如果 SQL 是可选的，那么您可以在 MongoDB 中以更好、更高效的方式使用当前的方法。

Answer 3

下面是一种将行从源 @S 一次移动一级到目标 @T 的解决方案。为了简化一点，我添加了一个根节点，以便始终有一个父节点存在，在创建新的 HierarcyID 时使用该父节点。

我从未使用过 HierarchyID，因此可能绝对有更有效的方法来执行此操作，但它至少应该比一次一行执行更有效。

-- Target table
declare @T table 
(
  hierarchy_id hierarchyid primary key,
  node_id bigint
)

insert into @T values
('/',             0), -- Needed for simplicity
('/1/',           1),
('/1/1/',         2),
('/1/2/',         3),
('/1/3/',         4)

-- Source table
declare @S table 
(
  hierarchy_id hierarchyid primary key,
  node_id bigint
)

insert into @S values
('/',               0),
('/1/',             1),
('/1/1/',           3),
('/1/2/',           5),
('/1/1/1/',         6)

declare @lvl int = 1

-- Move rows from @S to @T for each level
while exists(select *
             from @S
             where hierarchy_id.GetLevel() = @lvl)
begin

  insert into @T
  select T.hierarchy_id.GetDescendant(C.MaxID, null),
         S.node_id
  from (select S1.node_id, S2.node_id as ParentID
        from @S as S1
          inner join @S as S2
            on S1.hierarchy_id.GetAncestor(1) = S2.hierarchy_id
        where S1.hierarchy_id.GetLevel() = @lvl and
              S1.node_id not in (select node_id
                                 from @T)
       ) as S
    inner join @T as T
      on S.ParentID = T.node_id
    outer apply (select max(hierarchy_id) as MaxID
                 from @T as T2
                 where T.hierarchy_id = T2.hierarchy_id.GetAncestor(1)) as C       

    set @lvl = @lvl + 1
end

select *, hierarchy_id.ToString()
from @T
where hierarchy_id <> hierarchyid::GetRoot()  

结果：

hierarchy_id  node_id  (No column name)
------------  -------  ----------------
0x58          1        /1/
0x5AC0        2        /1/1/
0x5B40        3        /1/2/
0x5B56        6        /1/2/1/
0x5BC0        4        /1/3/
0x5C20        5        /1/4/