（对Nested Sets计算的替代）

Introduction

在我之前的文章中“Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets” 我们学习了一种新的、高性能的方法，在不到一分钟的时间内将一百万节点邻接表转换为嵌套集。问题是，我们所做的就是转换。我们仍然需要完成一些任务，这些任务可能与层次结构有关。例如，转换只允许我们计算层次结构问题的答案，例如每个节点有多少个后代?每个节点的销售额是多少？对于每一个节点的每一层的后代？每个节点的所有后代的总销售额是多少?每个级别只有 7 个等级 （典型的MLM 要求） 的后代的总销售额是什么？虽然嵌套的集结构肯定会使计算这些问题变得更容易，但是应该有一个更简单的方法来回答这些问题，而不是编写自定义代码来分别处理每个节点。它不应该花费比(现在快速)转换到嵌套集的时间更多的时间。

本文将向您展示如何快速计算所有这些内容，并为整个百万个节点层次结构提供更多信息 without Nested Sets.

注意，对于嵌套的集，永远不会有一个替代，特别是当您需要以正确的顺序列出一个层次结构的成员或进行“drill downs”（深入分析？）时。但是我们可以这样做，这样你就不需要在很多情况下计算你可能会询问等级的东西。

Who This Article is For

本文针对的是那些已经至少对层次结构有基本了解的人，比如邻接表是什么，以及它应该如何维护。本文还需要对t-sql有一个很好的理解，还有一些"Black Arts"的方法（like the Tally Table, for example），这是由DBA的良好社区开发的。

这篇文章中有一些术语，在前一篇文章中已经讨论过了。出于这个原因，本文还假设您已经阅读并理解了前面的文章:http://www.sqlservercentral.com/articles/Hierarchy/94040/.

最后但并非最不重要的是，有一些存储过程构建了从前一篇文章中提出的测试数据，并且在本文末尾的“参考资料”一节中介绍了这些数据。这些procs是如何工作的，远远超出了本文的范围。如果您想知道更多关于它们是如何工作的，那么procs本身就包含了一些很重的文档，这些文档应该能够满足您的好奇心(并且感谢您的好奇心！)

The Example Hierarchy and Quick Review（示例层次结构和快速回顾）

如果您执行附带的“BuildSmallEmployeeTable”存储过程，没有参数，那么它将在TempDB中构建一个“Employee”表，它看起来就像我们之前在转换到嵌套集时构建的Bowers。

图形上，它看起来像下面的。

Paste_Image.png

我们使用一个名为“dbo.RebuildNestedSets”的存储过程的形式，使用一些高性能代码从一个邻接表转换到嵌套集。“重新构建”的集合“也被连接了”。

总结一下存储过程,它首先运行rCTE(递归CTE)以生成需要构建嵌套集的几列信息,然后它运行下面的代码来实际构建嵌套的集合

--===== Declare a working variable to hold the result of the calculation
 -- of the LeftBower so that it may be easily used to create the
 -- RightBower in a single scan of the final table.
DECLARE @LeftBower INT
;
--===== Create the Nested Sets from the information available in the table
 -- and in the following CTE. This uses the proprietary form of UPDATE
 -- available in SQL Serrver for extra performance.
 WITH cteCountDownlines AS
 ( --=== Count each occurance of EmployeeID in the sort path
 SELECT EmployeeID = CAST(SUBSTRING(h.SortPath,t.N,4) AS INT),
    NodeCount  = COUNT(*) --Includes current node
 FROM dbo.Hierarchy h,
    dbo.HTally t
 WHERE t.N BETWEEN 1 AND DATALENGTH(SortPath)
 GROUP BY SUBSTRING(h.SortPath,t.N,4)
 ) --=== Update the NodeCount and calculate both Bowers
 UPDATE h
 SET @LeftBower   = LeftBower = 2 * NodeNumber - HLevel,
    h.NodeCount  = downline.NodeCount,
    h.RightBower = (downline.NodeCount - 1) * 2 + @LeftBower + 1
 FROM dbo.Hierarchy h
 JOIN cteCountDownlines downline
 ON h.EmployeeID = downline.EmployeeID
 ;

我们需要知道的一件事是计算Bowers的(行话，指的是前一篇文章)，即每个节点的下一行(行话，指的是前一篇文章)的后代总数。实际执行该操作的代码是上述代码的下面一行代码。

NodeCount  = COUNT(*) --Includes current node

获得该节点数的关键在于，实际上是将SortPath中的二进制(4)employeeid拆分为SortPath。在即将到来的代码中也是如此。

A More Complex Problem

让我们将一些新信息添加到我们的小员工表中。让我们将每个员工节点的总销售额添加到一个给定的月份(不管它是什么)。小的员工组织结构图是这样的。注意，每个节点的第4行是员工在给定月份的总销售额。

Paste_Image.png

现在，让我们来定义我们通常希望如何处理这些数据的嵌套集。我用黄色高亮了“Bob”，因为这是我们用来解释一切的节点。我还用不同的颜色强调了Bob的下一行，这样我们就能看到那里发生了什么。这是我们想要计算的关于Bob的计算(MLMers将会喜欢这个)。

1.计算Bob的下一行中节点的总数，包括Bob的节点。
2.计算每个相对级别的节点总数,在Bob的downline ，包括Bob的level.
3.计算Bob的downline 的总销售额，包括Bob的节点.
4.计算Bob的downline 每一个相对级别的总销售额，包括Bob的水平。
5.计算Bob的下一行中每个相对级别的相对级别，包括Bob的级别。Bob的相对水平是1。
6.计算Bob的下一行的总数量，包括Bob的级别
7.计算每一层的总数。

还有很多其他的计算方法你也可以做，比如计算每个Bob的下一行的销售额的百分比，但是这些都取决于上面列出的7个计算，所以我把这些计算留给你。

这些计算的真正妙处在于，我们将一次性完成所有这些计算，并将结果存储在我称为“Pre-Aggregated Hierarchical Table”中(有些人可能称之为“data mart”)。我们要在计算嵌套集的相同时间内做所有的事情。

Step 1: Create the Interim Hierarchy Table(创建临时层次结构表)

我们需要做的第一件事是将邻接表转换为嵌套集的第一步。
面的代码不仅将邻接表复制到一个新表(dbo.层级)，它还使用递归CTE(简称rCTE)来计算典型的SortPath和HLevel列。在第一篇文章中，我对代码所做的惟一更改是删除与创建嵌套集相关的所有列，并为销售添加一个占位符列。其他一切都和以前一样。

--     ===========================================================================
--      1.  Read ALL the nodes in a given level as indicated by the parent/
--          child relationship in the Adjacency List.
--      2.  As we read the nodes in a given level, mark each node with the 
--          current level number.
--      3.  As we read the nodes in a given level, convert the EmployeeID to
 --          a Binary(4) and concatenate it with the parents in the previous
 --          level’s binary string of EmployeeID’s.  This will build the 
 --          SortPath.
 --===========================================================================
 --===== Conditionally drop the final table to make reruns easier in SSMS.
 IF OBJECT_ID('FK_Hierarchy_Hierarchy') IS NOT NULL
    ALTER TABLE dbo.Hierarchy
     DROP CONSTRAINT FK_Hierarchy_Hierarchy;

 IF OBJECT_ID('dbo.Hierarchy','U') IS NOT NULL
     DROP TABLE dbo.Hierarchy;

 --===== Build the new table on-the-fly including some place holders
  WITH cteBuildPath AS 
 ( --=== This is the "anchor" part of the recursive CTE.
 -- The only thing it does is load the Root Node.
 SELECT anchor.EmployeeID, 
    anchor.ManagerID, 
    HLevel   = 1,
    SortPath =  CAST(
                    CAST(anchor.EmployeeID AS BINARY(4)) 
                AS VARBINARY(4000)) --Up to 1000 levels deep.
 FROM dbo.Employee AS anchor
 WHERE ManagerID IS NULL --Only the Root Node has a NULL ManagerID
UNION ALL 
--==== This is the "recursive" part of the CTE that adds 1 for each level
 -- and concatenates each level of EmployeeID's to the SortPath column.  
 SELECT recur.EmployeeID, 
    recur.ManagerID, 
    HLevel   =  cte.HLevel + 1,
    SortPath =  CAST( --This does the concatenation to build SortPath
                    cte.SortPath + CAST(Recur.EmployeeID AS BINARY(4))
                AS VARBINARY(4000))
  FROM dbo.Employee      AS recur WITH (TABLOCK)
   INNER JOIN cteBuildPath AS cte 
      ON cte.EmployeeID = recur.ManagerID
  ) --=== This final INSERT/SELECT creates an iterim working table to hold the
   -- original Adjacency List, the hierarchal level of each node, and the
   -- SortPath which is the binary representation of each node's upline.
    -- The ISNULLs make NOT NULL columns
   SELECT EmployeeID = ISNULL(sorted.EmployeeID,0),
    sorted.ManagerID,
    Sales      = ISNULL(CAST(0 AS BIGINT),0), --Place Holder
    HLevel     = ISNULL(sorted.HLevel,0),
    SortPath   = ISNULL(sorted.SortPath,sorted.SortPath)
   INTO dbo.Hierarchy
   FROM cteBuildPath AS sorted
  OPTION (MAXRECURSION 100) --Change this IF necessary
   ;
   SELECT * FROM dbo.Hierarchy ORDER BY SortPath;

这是我们的努力所得到的。

Paste_Image.png

请注意，原来的邻接表在EmployeeID和ManagerID列中存在。SortPath列与上一篇文章中的内容相同。它包含每个EmployeeID 从根节点到当前节点从左到右为 Binary(4) （4 字节十六进制） 表示。我们还计算了每个节点与根节点一起使用“1”的级别的级别。

作为一种侧栏，这种类型的rCTE在本质上不是RBAR1，因为它处理每个迭代的整组行。这些集合是节点的整个级别，如果这是波音747飞机上的数百万零件，你会发现所有这些部分只有18个左右，而rCTE只需要进行18次迭代。

还要注意，我们没有添加任何索引。事实证明，在EmployeeID列中添加一个索引实际上会使即将到来的代码运行的速度大约是原来的两倍，尽管我们会得到一个合并连接。不要在这个临时表中添加索引！如果您打算将这个表与嵌套的集计算(左和右的Bowers等等)放在一起，在完成下面的步骤之后，添加您需要的索引。

返回到当前的代码，我们还保留并预填充了一个销售列。让我们填满。

Step 2: Fill in the Sales Data

您可能会为EmployeeID提供一个单独的销售表，并对dbo进行更新。我们创建的层次结构表，用一个月的时间填充销售列(例如)。既然这不是火箭科学，我敢肯定你已经知道如何做这样的事情了，我现在不会用一个例子来烦你(在本文末尾的最后代码中有这样一个例子)。

但是，我需要用销售数量填充这个示例表，因为我们在表中有这么少的节点，我希望每个人都有相同的数据，所以我要用一些硬编码的数据来进行更新。这里的代码。

--===== Add an index to expedite the update of Sales data添加一个索引来加快销售数据的更新
ALTER TABLE dbo.Hierarchy
ADD PRIMARY KEY CLUSTERED (EmployeeID)
;
--===== Populate the Hierarchy table with current Sales data.使用当前的销售数据填充层次结构表。
UPDATE h 
SET h.Sales = s.Sales
FROM dbo.Hierarchy h
INNER JOIN 
    (
     SELECT 26,200000 UNION ALL
     SELECT  2, 90000 UNION ALL
     SELECT  3,100000 UNION ALL
     SELECT  6, 75000 UNION ALL
     SELECT  8, 80000 UNION ALL
     SELECT  7, 60000 UNION ALL
     SELECT 12, 50000 UNION ALL
     SELECT 14, 55000 UNION ALL
     SELECT 17, 70000 UNION ALL
     SELECT 18, 40000 UNION ALL
     SELECT 20, 40000 UNION ALL
     SELECT 21, 30000 UNION ALL
     SELECT 39, 90000 UNION ALL
     SELECT 40,120000
    ) s (EmployeeID, Sales)
 ON h.EmployeeID = s.EmployeeID
;
SELECT * FROM dbo.Hierarchy ORDER BY SortPath
;

这是现在的表格。

Paste_Image.png

我用颜色编码了数据，以匹配Bob的颜色编码和他从组织结构图上的下一行。如果您查看SortPath，您实际上可以看到“嵌套集”，即使我们没有使用嵌套集。每个新级别都包含在从左到右的前一级。

Step 3: Calculate Everything

正如您在步骤2中所看到的，如果我们将SortPath拆分为EmployeeID，并带来销售和HLevel列，那么我们就可以合计销售、每个节点的下一行节点的数量以及更多。我们实际上可以在一个高性能查询中计算我们想要的所有7个项目。

同样，这需要我们在前一篇文章中创建的特殊的“HTally”表，它从“1”开始，按“4”计数，如1、5、9、13等。这些值告诉我们每个EmployeeID的起始位置在SortPath中，以便将每个4字节(8个十六进制字符)分配给EmployeeID一个简单的任务。

构建HTally表(HTally.sql)的代码包含在本文末尾的“参考资料”一节中的ZIP文件中。现在请运行这段代码。

这个步骤实际上有三个子步骤，我们将使用级联CTEs(简称“cCTE”)来完成这一步骤。

1.从SortPath中分离出员工，并将每个销售金额和HLevel都带在一起，这样我们就可以在接下来的步骤中对销售额进行汇总。
2.按EmployeeID 和HLevel进行聚合。我们还创建并计算此步骤中每个雇员的每个聚合级别的“相对级别”(RLevel)。
3.将一些子总数添加到步骤2中使用过滤的ROLLUP创建的聚合体中。这为每个EmployeeID创建了一个大的行，并为每个相对级别(RLevel)向前计算了先前计算的子总数。

Step 3, Sub-Step 1: Split the SortPath

这段代码与我们在第一篇文章中使用的代码几乎完全相同。HTally表用于在SortPath中标识每个EmployeeID的起始位置，并将每4个字节分解。EmployeeID的二进制(4)表示转换为一个INT，以供人类的可读性，如果我们需要将最终表加入到原始邻接表(或任何其他表)的最终表中，以获得诸如雇员姓名之类的东西，那么就可以消除隐式转换。

代码还会获取HLevel和销售额，这样我们就可以在接下来的步骤中对销售进行汇总。
下面是这个子步骤的代码。(请注意，代码的每个子部分都是更大的级联CTE的一部分)

--===== Conditionally drop the final table to make reruns easier in SSMS.
 IF OBJECT_ID('dbo.Hierarchy','U') IS NOT NULL
    DROP TABLE dbo.PreAggregatedHierarchy
;
WITH
cteSplit AS
(--==== Splits the path into elements (including Sales and HLevel) 
 -- so that we can aggregate them by EmployeeID and HLevel.
 -- Can't aggregate here without including the SortPath so we don't.
SELECT EmployeeID = CAST(SUBSTRING(h.SortPath,t.N,4) AS INT),
    h.HLevel, h.Sales
FROM dbo.HTally         AS t
CROSS JOIN dbo.Hierarchy AS h
WHERE t.N BETWEEN 1 AND DATALENGTH(SortPath)
),

Step 3, Sub-Step 2: Aggregate the Sales by EmployeeID and HLevel（聚合）

这一步真的没有什么魔法。它是一个相当直接的向前聚合和一个简单的组。这里唯一的“奇怪”的事情是，我们通过EmployeeID分区一个简单的rownumber()来计算RLevel，并按照雇员的downline中包含的每个层次的层次结构进行排序。我们需要这个列(RLevel)来在即将到来的子步骤3中创建子总数

cteAggregate AS
(--==== Creates the aggregates and introduces the "Relative Level"  column.创建聚合并引入“相对级别”列
 -- NodeCount = Count of nodes in downline for each EmployeeID by Level按级别计算每个EmployeeID的节点数
 -- Sales = Total Sales in downline for each EmployeeID by Level.每个员工的总销售额按水平downline 。
 SELECT EmployeeID,
    HLevel,
    RLevel    = ROW_NUMBER() OVER (PARTITION BY EmployeeID 
                                       ORDER BY EmployeeID, HLevel),
    NodeCount = COUNT(*),
    Sales     = SUM(CAST(Sales AS MONEY))
FROM cteSplit
GROUP BY EmployeeID, HLevel
)

Step 3, Sub-Step 3: Use ROLLUP to Create Sub-Totals by Relative Level使用ROLLUP来根据相对级别创建子总数

在这段代码中有一小部分可能不太明显的魔法。我们需要从前面的CTE中引入几个列，将它们包含在我们的最终表中。问题是，我们实际上并不想把它们包含在这个组中，这不仅会使这个组变得更加复杂，而且还会导致卷起来产生大量不必要的行，而我们不得不扔掉这些行。

为了解决这些问题，我们只需要将已经聚合的数据聚合起来。由于每个EmployeeID的HLevel在这一点上都是独一无二的，因此我们可以通过使用MIN聚合函数来聚合它。

ROLLUP还将创建一个带有NULL EmployeeID的“grand total”行。这一行的总数实际上是不正确的，因为它包含了我们生成的所有重复行的总数。换句话说，一个EmployeeID的每个相对级别的子总数将包含在每个节点的upline的子总数的子总数中，这导致了一个不正确的“总体”计算。为了避免在输出中显示这一行，我们只需将它的NULL EmployeeID转换成一个“0”，然后告诉输出忽略这一行，使用一个过滤器忽略任何EmployeeID不具有EmployeeID的EmployeeID。

--===== Adds a "Rollup" to create all the subtotals that we need.添加一个“Rollup”来创建我们需要的所有子总数
 -- We couldn't do this in the previous step because we didn't know what(在之前的步骤中我们无法做到这一点因为我们不知道)
 -- the "Relative Level" was for each row, yet.然而，每一行的“相对级别”都是如此。
 -- The HAVING eliminates unnecessary subtotals that are created.（消除创建的不必要的子总数）
SELECT EmployeeID = ISNULL(a.EmployeeID,0), --Convert NULL total lines to 0
    HLevel     = MIN(a.HLevel), --Just so we don't have to GROUP BY
    RLevel     = ISNULL(CAST(a.RLevel AS TINYINT),0),
    NodeCount  = SUM(a.NodeCount), --Just so we don't have to         GROUP BY
    Sales      = SUM(a.Sales) --Just so we don't have to GROUP BY(这样我们就不需要分组了
  INTO dbo.PreAggregatedHierarchy
  FROM cteAggregate a
 GROUP BY EmployeeID, RLevel WITH ROLLUP
HAVING EmployeeID > 0 --Eliminates the NULL total lines for cleaner       output 为更清洁的输出消除空总行
;

当然，在使用这个结果表时，我们会添加至少一个对性能至关重要的索引，但是让我们看看在最终的“PreAggregateHierarchy”表中得到了什么。

The Result Can Replace the Need for Nested Sets结果可以替代对嵌套集的需求

为了避免回顾本文的开头，这里有一个组织结构图和我们使用过的销售数据，我添加了棕褐色的颜色(和我的色盲朋友的颜色对比鲜明的虚线)，以代表Bob的下线内所有的销售，包括Bob。

Paste_Image.png

并且，我们可以看到我们创建的代码的前几行数据。

SELECT * FROM dbo.PreAggregatedHierarchy ORDER BY EmployeeID, RLevel;

Paste_Image.png

再一次，Bob是EmployeeID 3，我在输出中用颜色表示了他的行。让我们先看一下黄色行中的Bob(在左边的第6行)。如果你回头看一下组织结构图，Bob就处于他自己的底线。相对而言，他处于他的下一行的一级，这在RLevel列中反映为“1”。对于Bob所处的相对级别，他是这个级别上唯一的节点，这反映在NodeCount列中。Bob的销售额也在10万美元，这反映在销售栏中。

Bob还有另外两个级别的下行。Vivian、Bill和 Natalie在Bob’s 下一行中占据了下一个层次。相对而言，这是Bob的第二个级别，这反映在RLevel中，作为Bob的绿色行(第7行)的“2”(EmployeeID仍然是Bob的“3”),由于Bob的第二个相对级别有3个员工，所以在NodeCount中反映了这一行的“3”。这三名员工的销售额也达到了18万美元这也反映在这一行的销售栏中。

Bob的第三个相对级别有2个人，其销售总额达到$105,000，所有这些都反映在RLevel、NodeCount和蓝色行的销售列(第8行)。

如果您为Bob(EmployeeID=3)取Max(RLevel)，那么您就会知道Bob在他的下一行中包含的所有级别，包括他自己。

最后但并非最不重要的是，(第5行)是Bob整个下线的总行。RLevel是“0”，表示这是一个大的总数，而不是一个相对级别的总和。NodeCount是“6”，即Bob的下一行有多少个节点，包括他自己。最后，销售栏包含Bob的整个产品线的销售总额，包括Bob。

作为一个可能被证明有用的工件，每一行的原始层次结构也被保留。例如，如果我们不仅要知道整个层次结构的总销售额还要知道整个层次结构的总销售额?您可以尝试实现多维数据集，而不是使用ROLLUP或任何时间消耗和代码冗长的方法或……我们只需要记住，根节点将包含所有这些信息。由于表中没有空ManagerID来标识根节点，所以您可能会认为我们必须返回到原始的邻接表来查找根节点的EmployeeID。不是真的!我们知道，只有一个根节点，它可以独自生活在HLevel 1中。考虑到这个想法，下面的非常简单的代码(请原谅“这个例子”)将会发现整个层次结构的总销售额和层次结构中的每个层次的总销售额。我们将在最终代码中添加索引，即使在一百万个节点层次结构中，结果也几乎是即时的。

SELECT *
FROM dbo.PreAggregatedHierarchy
 WHERE EmployeeID IN
    (
     SELECT TOP 1 EmployeeID 
       FROM dbo.PreAggregatedHierarchy 
      WHERE HLevel = 1
    )
ORDER BY HLevel, RLevel;

下面是来自小员工表的结果。

Paste_Image.png

对你传销来说，在人群中，根据你的水平驱动资格来计算每月的支出，使用这种pre-aggregated hierarchy table类型，如果您有类似于7级的单级支付结构，那么您当然会限制这个表只包含每个节点7个级别。里程碑式的奖金也很容易计算。

这也适用于“二进制”结构，尽管它对确保层次结构的二进制性质没有任何作用。无论如何，你应该已经有了这样的约束。

Yeah, but how fast is it?是的，但是它有多快?

在前一篇文章中，我们发现我们可以在大约54秒内将一百万个节点邻接表转换为嵌套集。让我们来看看这篇文章中代码的好坏。我们将首先构建一百万个节点层次结构，构建一百万个节点销售表，然后将所有代码与所有正确的索引放在一起，看看会发生什么。我也不打算将最终表中的下一行节点限制为7。我们的“一应俱全”！

The Test Data

您将在本文底部的“参考资料”一节中找到一个存储过程，以构建一个大型的雇员层次结构表。如果您还没有这样做，请打开“构建大型employeetable”的代码并执行它来构建过程，它都在TempDB中运行，只是为了安全起见。我们不想不小心丢了任何人的真正的表。

接下来，运行以下代码。它将同时构建百万节点“Employee”表和百万行“current月中销售”表。我的笔记本电脑大约需要11秒钟。

-===== Do this in a nice, safe place that everyone has.
USE tempdb
;
--===== Build the million row employee table.
-- This takes about 17 seconds on my laptop and builds the correct
-- indexes, as well. Because of the second parameter, it builds
-- a more realistic hierarchy with randomized EmployeeID's.
EXEC dbo.BuildLargeEmployeeTable 1000000 ,1
;
--===== Conditionally drop the final table to make reruns easier in SSMS.
IF OBJECT_ID('dbo.CurrentMonthlySales','U') IS NOT NULL
DROP TABLE dbo.CurrentMonthlySales
;
--===== Create and randomly populate the new Sales table on-the-fly.
-- Each EmployeeID will have somewhere between $0 and $1,000 of sales.
-- This only takes about 3 seconds on my laptop.
SELECT TOP 1000000
EmployeeID = IDENTITY(INT,1,1),
Sales = ABS(CHECKSUM(NEWID()))%1001
INTO dbo.CurrentMonthlySales
FROM sys.all_columns ac1
CROSS JOIN sys.all_columns ac2
;
--===== Add the expected Clustered Index as a Primary Key
-- This only adds about a second of time to the run.
ALTER TABLE dbo.CurrentMonthlySales
ADD CONSTRAINT PK_CurrentMonthlySales
PRIMARY KEY CLUSTERED (EmployeeID)
;

Putting the Code Together 把代码放在一起

下面的内容可以转换为存储过程。这是我们在这篇文章中所经历的所有代码，以及一些额外的代码来添加一个为了简单起见而省略的索引。如果你运行下面的代码,它将建立临时表“层次结构”(你可以很容易地转换为一个临时表,如果需要的话),销售数字适用于从上面我们刚刚创建的“CurrentMonthlySales”表,构建最终的“PreAggregatedHierarchy”表,并添加最后一个表的聚集索引。 这里的代码。

下面是显示行数和持续时间的运行结果。

(1000000 row(s) affected)

(1000000 row(s) affected)

(3231566 row(s) affected)
Duration: 00:01:01:943 (hh:mi:ss:mmm)

想象一下。在一百万个节点层次结构中，您需要做的大多数工作都是在大约62秒内完成并存储在一个现成的预聚合表中。

Hold the Phone! 3.3 Million Rows? Why?请别挂电话，330万行，为什么？

在最后的表中，所有“额外”的行都是从哪里来的?请记住，层次结构中的每个节点都可以在下行线中有多个级别，并且每个节点对于该节点的总金额也有一个“0”级。如果您有一百万个节点层次结构，每个节点都有7个级别的下行线(对于离叶节点或叶节点本身最近的节点，实际上不可能)，这将会产生一个800万行表格。100万的相对水平和100万的“0”级。

不要被这样的行扩展或最终表的大小吓倒。这就是创建索引的目的，以确保此类表上的查找和其他聚合将以极快的速度运行。问问传销公司的人。800万行，相对瘦的桌子对他们来说毫无意义。:-)

I Can’t Afford the 62 Seconds of “DownTime” 我无法承受62秒的“停机”

如果最后的预聚合层次结构表，24/7/.999999999 web site or application是信息的来源，如果你在经营一个世界范围的多层次直销公司，那么你真的无法承受62秒的停机时间。在重新构建表时，您确实不想让任何成员对“宕机”一分钟感到愤怒。

那么你会怎么做呢?

这很简单。在构建新版本时，有一个同义词(或直通视图)指向 pre-aggregated hierarchy表的当前版本。完成后，只需将同义词或视图重新指向新表并删除旧表(或将其保存为一个月的月比较)。现在的“停机时间”是用几秒的时间来衡量的

下个月，你做同样的事情。只需要在两个表之间保持“反覆”的同义词或视图。

您甚至可以将主键的构建包括在这样的在线方式中，如果您让系统为您命名PKs，而不是将它们添加为“命名约束”。添加其他索引是件很容易的事，因为在数据库中，索引名称不必是惟一的，就像约束需要的那样。

Conclusion

不要让这成为你的“结论”。您是否决定将一个邻接表的高性能转换与我们在第一篇文章中所做的一样，在本文中使用预聚合的层次结构表，或者是一些有趣的进一步的混合，我们刚刚触及了层次结构和所有你可以用它们做的事情。正如您所看到的，代码并不需要复杂或执行得很差，因为我们有一百万行。

这两篇文章的主要目的是向你展示你可以拥有多层蛋糕（一种等级制度，对双关语很抱歉)然后吃它，您可以享受到邻接表的所有快速、简单和简单的维护好处，并且仍然可以通过嵌套集和/或您可能使用的预聚合的层次表来报告马力，而不是嵌套集。

如果您已经将您的层次结构转换为仅使用嵌套集，并且希望使用邻接表来实现易于维护，请不要绝望。只需做一个web搜索“将嵌套的集合转换为一个邻接表”。我还没有测试过您在性能方面会发现的任何方法，但是它们至少看起来是基于集合的，并且应该是相当快的。除此之外，你只需要做一次。:-)

最后那当然也是最重要的。，如果你保持“dbo.Hierarchy”为嵌套集,你没有理由不让你的邻接表像以前一样拥有最好的3个世界，在"Hierarchy" table中包含嵌套集，在“预聚合层次结构”表中对大多数层次化问题进行预先聚合的回答。

Acknowledgements

和前一篇文章一样，如果没有我从几个个人中获得的一些知识，这篇文章是不可能的，尤其是直接或间接的。这里没有提到它们的空间，但这里有一些。

首先，当你说“SQL中的层次结构”或“嵌套”的时候，你必须站起来，向Joe Celko致敬，他在这几年里所做的工作。他逐字地写了这本书。

：我还想感谢Grant Fritchey的工作，他在像我这样的人身上做了一项令人难以置信的工作，他如何阅读“执行计划”。我有幸和他的优秀作品回顾了他的关于解剖执行计划的书籍，他们教会了我如何弄清楚我需要做什么，以及添加哪些索引以使那些懒惰的代码以光速运行。他的一本书在SQLServerCentral上可以在下面的URL中找到。是的，你可以免费下载，然后我必须告诉你，没有它，你的图书馆是不完整的。

http://www.sqlservercentral.com/articles/books/65831/

我还想感谢Peter Larsson(又称“比索”)，他在教导人们(比如我)的“预聚合”和一些我在小组中提出的各种各样的技巧，而不是由他们来分组。就我而言，彼得创造了“预聚合”这个词，我在很多领域都使用了他的技术，在这些领域，我需要创造高性能的聚合。

最后，我不知道是谁写了我在使用数字表格时看到的第一篇文章(Tally Tables)，但感谢你让我的生活变得更简单。感谢Adam Machanic第一次提出“Calendar Tables”的主题，这让我想到了关于数字(数字)的文章。

Resources:

HierarchyCode.zip