将平板餐桌解析成树的最有效/最优雅的方法是什么？

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中？

编辑和添加

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

我所说的“结果集”可以图片为一个哈希表数组（保留在该术语中）。对于我的示例，本应已经存在。一些答案需要付出额外的努力，然后再进行构建，但这没关系。

这棵树可以任意深。每个节点可以有N个子节点。不过，我并没有真正想到“成千上万的条目”树。

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

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

Answer 1

既然MySQL8.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年的演示文稿递归查询Throwdown中测试了MySQL
8.0中的递归查询。

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

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

• 邻接列表 （“父”列）和
• 路径枚举 （名称列中的点号）。

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

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

在我的演示文稿“使用SQL和PHP的分层数据模型”以及《SQL反模式：避免数据库编程的陷阱》一书中，我介绍了闭包表。

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的后代的所有节点，将它们连接到包含其他节点属性（例如）的FlatTable并按name名称排序。

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，以确保顺序与层次结构匹配。但这是行不通的，因为它将在“节点1.2”之后对“节点1.1.1”进行排序。