检索所有子级及其子级，递归SQL

Question

考虑以下数据库中的行:

Id      |   Parent
__________________
1           null
2           1
3           2
4           3
5           null
6           5

每一个具有 null Parent 的 Id 都是“Owner”/“Super Parent”。

在收集父级及其子级方面，哪种方法在性能上最好？我应该使用 LINQ 还是 存储过程？

我希望最终结果为 IEnumerable<IEnumerable<int>>。

- Filip Ekberg

---

你是想要将自己作为父级项目吗？ - Eric Petroelje

你是在暗示一个顺序吗？如果你想要一个包含所有子元素的IEnumerable，你可以执行select * from table where parent is not null，所以你的问题肯定还有更多细节... - Kendrick

第二行的父级是第二行？哎呀。 - Andomar

@Eric，不，情况从来都不是那样，它要么是null，要么指向另一个“行”。 - Filip Ekberg

@Andomar，没注意到，谢谢 :) @Kendrick，正如你所看到的，它是一个IEnumerable，其中包含IEnumerable<int>，其中每个IEnumerable<int>表示父级下面的子级。 - Filip Ekberg

Answer 1

在SQL中，可以使用CTE来查询。例如，要检索带有其父节点和其树中最高父节点的节点列表：

declare @t table (id int, parent int)
insert @t (id, parent) values (1, null), (2,1), (3,2), (4,3), (5,null), (6,5)

; with cte as (
    select  id, parent, id as head
    from    @t
    where   parent is null
    union all
    select  child.id, child.parent, parent.head
    from    @t child
    join    cte parent
    on      parent.id = child.parent
)
select  *
from    cte

这将会得到：

id  parent  head
1   NULL    1
2   1       1
3   2       1
4   3       1
5   NULL    5
6   5       5

请注意，我修改了你的示例数据，所以第二行不再是它自己的子级，而是第一行的子级。

- Andomar

Answer 2

您也可以使用纯SQL解决方案；这里是SQL Server的示例。对于不同的数据库管理器，重写它并不困难：

/* Create table */
CREATE TABLE dbo.Nodes (ID int NOT NULL PRIMARY KEY, Parent int)

/* Insert sample data */
INSERT INTO Nodes VALUES (1,NULL)
INSERT INTO Nodes VALUES (2,1)
INSERT INTO Nodes VALUES (3,2)
INSERT INTO Nodes VALUES (4,3)
INSERT INTO Nodes VALUES (5,NULL)
INSERT INTO Nodes VALUES (6,5)

/* Create recursive function */
CREATE function dbo.fn_Root(@ID int) returns int
AS BEGIN
   DECLARE @R int

   SELECT @R = CASE WHEN Parent IS NULL THEN ID
                    ELSE dbo.fn_Root(Parent)
                 END
            FROM Nodes
           WHERE id = @id

   RETURN @R
END

/* Query the table */
SELECT ID, Parent, dbo.fn_Root(ID) AS Root
  FROM Nodes

/* Also, in SQL Server you can create a calculated column */
ALTER TABLE Nodes ADD Root AS dbo.fn_Root(id)

这是基本版本。但如果您的数据有闭环（不是树形结构），这个版本将失败。为了防止代码进入无限循环，可以对函数进行改进，如下：

CREATE function dbo.fn_Root(@ID int, @Initial int) returns int
AS BEGIN
   DECLARE @R int

   DECLARE @Parent int
   SELECT @Parent = Parent FROM Nodes WHERE ID = @ID

   IF @Parent IS NULL 
      SELECT @R = @ID   /* No parent, the root is the node itself */
   ELSE
      IF @Parent = @Initial 
         /* We have returned to initial node: endless loop. We return NULL to indicate no root exists */
         SELECT @R = NULL
      ELSE
         /* The root will be the root of the parent node */
         SELECT @R = dbo.fn_Root(@Parent,@Initial)   

   RETURN @R

END

/* Query the table */
SELECT ID, Parent, dbo.fn_Root(ID,ID) AS Root FROM Nodes

通过这个修改，如果函数返回NULL，则表示该节点是循环的一部分，因此它没有根节点。

- ACB

Answer 3

如果表不太大，你最好的选择是通过以下方式返回整个表： db.Categories

一旦整个类别表被获取到Entity Framework中，EF将使用关系跨度来修复对象图，这样当你执行category.SubCategories时，你将得到所有的子项。 这样做的优点是，你的SQL语句不会很复杂，因为它基本上只是从categories中选择*。EF在修复对象图方面做了大部分的工作，以便所有的子项都能正确地与它们的父项对齐。

你也可以使用其他人提到的通用表达式。

我在我的书中涵盖了两个这样的概念。

5-11 使用关系跨度 5-2 加载完整的对象图(CTE)

- zeeshanhirani

Answer 4

数据库并不是为了进行任意深度递归而设计的。这里展示了本地执行所需的操作。

List<Item> items = context.Items.ToList();

Dictionary<int, Item> itemsById = items.ToDictionary(item => item.Id);

Dictionary<int, List<Item>> itemsByRoot = new Dictionary<int, List<Item>>();
List<Item> cyclicals = new List<Item>();

foreach(Item item in items)
{
  HashSet<int> seenIt = new HashSet<int>();
  Item parent = item;
  while (parent.ParentId != null && !seenIt[parent.Id])
  {
    seenIt.Add(parent.Id);
    parent = itemsById[parent.ParentId];
  }

  if (parent.ParentId == null)
  {
    if (!itemsByRoot.ContainsKey(parent.Id))
    {
      itemsByRoot[parent.Id] = new List<Item>();
    }
    itemsByRoot[parent.Id].Add(item);
  }
  else
  {
    cyclicals.Add(item);
  }
}

- Amy B

---

这样做是否会带来任何性能上的好处，而不是采用已接受的答案？而且这种感觉比必须要复杂得多。 - Filip Ekberg