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

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]名称。根节点 0 是虚构的。

                       [0] ROOT                          /    \               [1] Node 1          [3] Node 2              /       \                   \    [2] Node 1.1     [6] Node 1.2      [5] Node 2.1          /           [4] Node 1.1.1

您将使用哪种简约方法将其输出为 HTML(或文本)作为正确排序、正确缩进的树？

进一步假设你只有基本的数据结构(数组和 HashMap )，没有带有父/子引用的奇特对象，没有 ORM，没有框架，只有你的两只手。该表表示为结果集，可以随机访问。

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

额外问题:是否有一种更好的方法在 RDBMS 中存储这样的树结构？

<小时/>

编辑和添加

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

我所说的“结果集”可以被描述为 HashMap 数组(保留该术语)。对于我的例子来说，它本来就已经在那里了。有些答案会加倍努力并首先构建它，但这没关系。

树的深度可以是任意的。每个节点可以有 N 个子节点。不过，我心里并没有真正想到“数百万个条目”树。

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

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

Answer 1

现在MySQL 8.0 supports recursive queries ，我们可以说all popular SQL databases support recursive queries采用标准语法。

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;

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

以下是我 2008 年的原始回答:

<小时/>

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

• 邻接列表(“父”列)和
• 路径枚举(您的姓名列中的点号)。

另一种解决方案称为嵌套集，它也可以存储在同一个表中。阅读 Joe Celko 的“Trees and Hierarchies in SQL for Smarties”，了解有关这些设计的更多信息。

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

我在演讲中介绍了 Closure Table Models for Hierarchical Data with SQL and PHP在我的书中SQL Antipatterns Volume 1: Avoiding the Pitfalls of Database Programming .

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 关于直系子代(或直系父代)的评论。您可以向 ClosureTable 添加“path_length”列，以便更轻松地专门查询直接子项或父项(或任何其他距离)。

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.1.1”排序在“Node 1.2”之后。

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