将平面表解析为树的最有效/优雅的方法是什么？

Question

假设您有一个存储有序树层次结构的平面表：

 Id   Name         ParentId   Order
 1   'Node 1'            0      10
 2   'Node 1.1'          1      10
 3   'Node 2'            0      20
 4   'Node 1.1.1'        2      10
 5   'Node 2.1'          3      10
 6   'Node 1.2'          1      20

这是一个图表，我们有 [id] Name 。根节点 0 是虚构的。

                       [0] 根
                          / \
              [1] 节点 1 [3] 节点 2
              / \ \
    [2] 节点 1.1 [6] 节点 1.2 [5] 节点 2.1
          /
 [4] 节点 1.1.1

您将使用什么简约方法将其作为正确排序、正确缩进的树输出到 HTML（或文本）？

进一步假设你只有基本的数据结构（数组和哈希图），没有带有父/子引用的花哨对象，没有 ORM，没有框架，只有你的两只手。该表表示为一个结果集，可以随机访问。

伪代码或纯英文都可以，这纯粹是一个概念问题。

额外的问题：有没有更好的方法在 RDBMS 中存储这样的树结构？

---

编辑和添加

回答一位评论者（ Mark Bessey ）的问题：根节点不是必需的，因为它永远不会被显示。 ParentId = 0 是表达“这些是顶级”的约定。 Order 列定义了如何对具有相同父节点的节点进行排序。

我所说的“结果集”可以被描绘成一个哈希图数组（保留在那个术语中）。因为我的例子本来就应该在那里。有些答案会加倍努力并首先构建它，但这没关系。

树可以任意深。每个节点可以有 N 个孩子。不过，我并没有完全想到“数百万个条目”树。

不要将我选择的节点命名（’Node 1.1.1’）误认为是可以依赖的东西。这些节点同样可以称为“Frank”或“Bob”，没有暗示命名结构，这只是为了使其可读。

我已经发布了我自己的解决方案，因此你们可以将其分解。

原文由 Tomalak 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

既然 MySQL 8.0 支持递归查询，我们可以说 所有流行的 SQL 数据库都支持标准语法的递归查询。

 WITH RECURSIVE MyTree AS (
    SELECT * FROM MyTable WHERE ParentId IS NULL
    UNION ALL
    SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;

我在 2017 年的演示 Recursive Query Throwdown 中测试了 MySQL 8.0 中的递归查询。

以下是我 2008 年的原始答案：

---

有几种方法可以在关系数据库中存储树状结构的数据。您在示例中显示的内容使用两种方法：

• 邻接列表（“父”列）和
• 路径枚举（您的姓名列中的虚线数字）。

另一种解决方案称为 嵌套集，它也可以存储在同一个表中。有关这些设计的更多信息，请阅读 Joe Celko 的“ Smarties 中的树和层次结构”。

我通常更喜欢一种称为 闭包表（又名“邻接关系”）的设计来存储树形结构的数据。它需要另一个表，但是查询树非常容易。

我在我的演示文稿 Models for Hierarchical Data with SQL and PHP 和我的书 SQL Antipatterns: Avoiding the Pitfalls of Database Programming 中介绍了 Closure Table。

 CREATE TABLE ClosureTable (
  ancestor_id   INT NOT NULL REFERENCES FlatTable(id),
  descendant_id INT NOT NULL REFERENCES FlatTable(id),
  PRIMARY KEY (ancestor_id, descendant_id)
);

将所有路径存储在闭包表中，其中存在从一个节点到另一个节点的直接祖先。为每个节点包含一行以引用自身。例如，使用您在问题中显示的数据集：

 INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
  (1,1), (1,2), (1,4), (1,6),
  (2,2), (2,4),
  (3,3), (3,5),
  (4,4),
  (5,5),
  (6,6);

现在你可以得到一个从节点 1 开始的树，如下所示：

 SELECT f.*
FROM FlatTable f
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;

输出（在 MySQL 客户端中）如下所示：

 +----+
| id |
+----+
|  1 |
|  2 |
|  4 |
|  6 |
+----+

换句话说，节点 3 和 5 被排除在外，因为它们是单独层次结构的一部分，而不是从节点 1 下降。

---

回复：来自 e-satis 关于直系子女（或直系父母）的评论。您可以在 — 中添加“ path_length ClosureTable 列，以便更轻松地专门查询直系子女或父母（或任何其他距离）。

 INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
  (1,1,0), (1,2,1), (1,4,2), (1,6,1),
  (2,2,0), (2,4,1),
  (3,3,0), (3,5,1),
  (4,4,0),
  (5,5,0),
  (6,6,0);

然后，您可以在搜索中添加一个术语来查询给定节点的直接子节点。这些是 path_length 为 1 的后代。

 SELECT f.*
FROM FlatTable f
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
  AND path_length = 1;

+----+
| id |
+----+
|  2 |
|  6 |
+----+

---

来自@ashraf 的重新评论：“如何[按名称] 对整棵树进行排序？”

这是一个示例查询，用于返回节点 1 的所有后代节点，将它们连接到包含其他节点属性（例如 name ）的 FlatTable，然后按名称排序。

 SELECT f.name
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;

---

来自@Nate的重新评论：

 SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id)
WHERE a.ancestor_id = 1
GROUP BY a.descendant_id
ORDER BY f.name

+------------+-------------+
| name       | breadcrumbs |
+------------+-------------+
| Node 1     | 1           |
| Node 1.1   | 1,2         |
| Node 1.1.1 | 1,2,4       |
| Node 1.2   | 1,6         |
+------------+-------------+

---

一位用户今天提出了修改建议。 SO 版主批准了编辑，但我正在撤消它。

编辑建议上面最后一个查询中的 ORDER BY 应该是 ORDER BY b.path_length, f.name ，大概是为了确保排序与层次结构匹配。但这不起作用，因为它会在“Node 1.2”之后订购“Node 1.1.1”。

如果您希望排序以合理的方式匹配层次结构，这是可能的，但不仅仅是通过路径长度排序。例如，请参阅我对 MySQL Closure Table hierarchy database - How to pull information out in the correct order 的 回答。

原文由 Bill Karwin 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

在邻接表示上使用动态路径枚举进行预排序

嵌套集来自：

• Konchog https://stackoverflow.com/a/42781302/895245
• 乔尼·布坎南 https://stackoverflow.com/a/194031/895245

是我见过的唯一有效的遍历方式，代价是更新速度较慢。这可能是大多数人想要的预购。

https://stackoverflow.com/a/192462/895245 中的闭包表很有趣，但我看不到如何在那里强制执行预订： MySQL Closure Table hierarchy database - How to pull information out in the correct order

主要是为了好玩，这里有一个递归计算 1.3.2.5 的方法。动态前缀并在最后按它们排序，仅基于父 ID/子索引表示。

优点：

• 更新只需要更新每个兄弟的索引

缺点：

• 超深树的 n^2 内存使用最坏情况。这可能非常严重，这就是为什么我说这种方法可能主要是为了好玩。但也许有一些超高更新案例有人想使用它？谁知道
• 递归查询，因此读取的效率将低于嵌套集

创建和填充表：

 CREATE TABLE "ParentIndexTree" (
  "id" INTEGER PRIMARY KEY,
  "parentId" INTEGER,
  "childIndex" INTEGER NOT NULL,
  "value" INTEGER NOT NULL,
  "name" TEXT NOT NULL,
  FOREIGN KEY ("parentId") REFERENCES "ParentIndexTree"(id)
)
;
INSERT INTO "ParentIndexTree" VALUES
  (0, NULL, 0, 1, 'one'  ),
  (1, 0,    0, 2, 'two'  ),
  (2, 0,    1, 3, 'three'),
  (3, 1,    0, 4, 'four' ),
  (4, 1,    1, 5, 'five' )
;

代表树：

     1
   / \
  2   3
 / \
4   5

然后对于具有像 PostgreSQL 这样的数组的 DBMS]( https://www.postgresql.org/docs/14/arrays.html )：

 WITH RECURSIVE "TreeSearch" (
  "id",
  "parentId",
  "childIndex",
  "value",
  "name",
  "prefix"
) AS (
  SELECT
    "id",
    "parentId",
    "childIndex",
    "value",
    "name",
    array[0]
  FROM "ParentIndexTree"
  WHERE "parentId" IS NULL

  UNION ALL

  SELECT
    "child"."id",
    "child"."parentId",
    "child"."childIndex",
    "child"."value",
    "child"."name",
    array_append("parent"."prefix", "child"."childIndex")
  FROM "ParentIndexTree" AS "child"
  JOIN "TreeSearch" AS "parent"
    ON "child"."parentId" = "parent"."id"
)
SELECT * FROM "TreeSearch"
ORDER BY "prefix"
;

这会动态创建表单前缀：

 1 -> 0
2 -> 0, 0
3 -> 0, 1
4 -> 0, 0, 0
5 -> 0, 0, 1

然后PostgreSQL然后按字母顺序对数组进行排序：

 1 -> 0
2 -> 0, 0
4 -> 0, 0, 0
5 -> 0, 0, 1
3 -> 0, 1

这是我们想要的预购结果。

对于没有像 SQLite 这样的数组的 DBMS，您可以通过使用一串固定宽度整数对前缀进行编码来破解。二进制是理想的，但我不知道如何，所以十六进制会起作用。这当然意味着您必须选择适合所选字节数的最大深度，例如，在下面我选择 6，允许每个节点最多 16^6 个子节点。

 WITH RECURSIVE "TreeSearch" (
  "id",
  "parentId",
  "childIndex",
  "value",
  "name",
  "prefix"
) AS (
  SELECT
    "id",
    "parentId",
    "childIndex",
    "value",
    "name",
    '000000'
  FROM "ParentIndexTree"
  WHERE "parentId" IS NULL

  UNION ALL

  SELECT
    "child"."id",
    "child"."parentId",
    "child"."childIndex",
    "child"."value",
    "child"."name",
    "parent"."prefix" || printf('%06x', "child"."childIndex")
  FROM "ParentIndexTree" AS "child"
  JOIN "TreeSearch" AS "parent"
    ON "child"."parentId" = "parent"."id"
)
SELECT * FROM "TreeSearch"
ORDER BY "prefix"
;

一些嵌套的音符

在查看其他嵌套集合答案后，这里有几点让我有点困惑。

Jonny Buchanan 将他的嵌套集设置显示为：

 __________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

这让我想知道为什么不使用更简单的外观：

 __________________________________________________________________________
|  Root 1                                                                 |
|   ________________________________    _______________________________   |
|  |  Child 1.1                     |  |  Child 1.2                    |  |
|  |   ___________    ___________   |  |   ___________   ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  | |  C 1.2.2  |  |  |
1  2  3___________|  4___________|  |  5  6___________| 7___________|  |  |
|  |________________________________|  |_______________________________|  |
|_________________________________________________________________________|

每个端点没有额外的数字。

但是当我真正尝试实现它时，我注意到很难/不可能实现这样的更新查询，除非我有 Konchog 使用的父信息。问题是在树被移动时很难/不可能区分兄弟姐妹和父母，我需要它来决定在缩小差距时是否要减少右侧.

左/大小与左/右：您可以将其存储在数据库中，但我认为左/右可以更有效，因为您可以使用多列索引（左，右）对数据库进行索引，然后可以使用它来加速up 祖先查询，其类型为：

 left < curLeft AND right > curLeft

在 Ubuntu 22.04、PostgreSQL 14.5、SQLite 3.34.0 上测试。

原文由 Ciro Santilli OurBigBook.com 发布，翻译遵循 CC BY-SA 4.0 许可协议