什么是最有效率的/优雅的方式来解析一个平坦的表格到树？
假设您有一个存储有序树层次结构的平坦表格：
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] 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（或文本，就此而言）作为正确排序，正确缩进的树？
进一步假设你只有基本的数据结构（数组和hashmaps），不带有父/子引用的奇特对象，没有ORM，没有框架，只有你的两只手。 该表格表示为结果集，可以随机访问。
伪代码或纯英文是可以的，这纯粹是一个概念性问题。
奖金问题：在RDBMS中有没有一种更好的方法来存储像这样的树结构？
编辑和附加
回答一个评论者（Mark Bessey）的问题：根节点不是必需的，因为它永远不会被显示。 ParentId = 0是表达“这些是最高级别”的约定。 “订单”列定义如何对具有相同父级的节点进行排序。
我所说的“结果集”可以被描绘成一系列hashmaps（留在这个术语中）。 对于我的例子本来就是已经存在的。 有些答案会加倍努力并首先构建它，但那没关系。
树可以是任意深的。 每个节点可以有N个孩子。 虽然我并没有真正拥有“数百万条目”树。
不要误将我选择的节点命名（'节点1.1.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;
以下是我2008年的原始答案：
在关系数据库中存储树结构化数据有多种方法。 您在示例中显示的内容使用两种方法：
另一个解决方案称为嵌套集 ，它也可以存储在同一个表中。 请阅读Joe Celko的“SQL中的Trees和Hierarchies for Smarties”以获得更多关于这些设计的信息。
我通常更喜欢一种称为Closure Table （又名“Adjacency Relation”）的设计来存储树形结构数据。 它需要另一张桌子，但随后查询树木非常容易。
我介绍了我的演示文稿中的Closure Table 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)
);
将所有路径存储在Closure Table中，其中存在从一个节点到另一个节点的直接祖先。 为每个节点添加一行以引用自身。 例如，使用您在问题中显示的数据集：
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递减。
Re：关于直系孩子（或直系父母）的e-satis评论。 您可以在path_length添加一个“ 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，并按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 b.path_length, f.name应该是ORDER BY b.path_length, f.name ，大概是为了确保排序与层次结构相匹配。 但这不起作用，因为它会在“节点1.2”之后订购“节点1.1.1”。
如果您希望命令以合理的方式匹配层次结构，这是可能的，但不能简单地按路径长度排序。 例如，请参阅我对MySQL Closure Table分层数据库的回答 - 如何以正确的顺序提取信息。
如果使用嵌套集（有时称为修改的预定义树遍历），则可以使用单个查询以树形结构提取整个树结构或其中的任何子树，但代价是插入代价更高，因为您需要管理通过树结构描述有序路径的列。
对于django-mptt，我使用了这样的结构：
id parent_id tree_id level lft rght -- --------- ------- ----- --- ---- 1 null 1 0 1 14 2 1 1 1 2 7 3 2 1 2 3 4 4 2 1 2 5 6 5 1 1 1 8 13 6 5 1 2 9 10 7 5 1 2 11 12
其中描述了一个看起来像这样的树（带有代表每个项目的id ）：
1
+-- 2
| +-- 3
| +-- 4
|
+-- 5
+-- 6
+-- 7
或者，作为一个嵌套的设置图，这使得它更明显地显示了lft和rght值是如何工作的：
__________________________________________________________________________ | 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 | |________________________________| |________________________________| | |__________________________________________________________________________|
正如你看到的，让整个子树给定节点，在树的顺序，你只需要选择哪个都行lft和rght其之间的值lft和rght值。 检索给定节点的祖先树也很简单。
为了方便起见， level列有点非tree_id化，并且tree_id列允许您为每个顶级节点重新启动lft和rght编号，从而减少了受插入，移动和删除操作影响的列数，如lft并且在进行这些操作时必须相应地调整rght列以创建或缩小差距。 当我试图围绕每个操作所需的查询来解决问题时，我做了一些开发笔记。
在实际使用这些数据来显示树的过程中，我创建了一个tree_item_iterator实用程序函数，该函数为每个节点提供足够的信息来生成您想要的任何类型的显示。
有关MPTT的更多信息：
从Oracle 9i开始，您可以使用CONNECT BY。
SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)
从SQL Server 2005开始，您可以使用递归公用表表达式（CTE）。
WITH [NodeList] (
[Id]
, [ParentId]
, [Level]
, [Order]
) AS (
SELECT [Node].[Id]
, [Node].[ParentId]
, 0 AS [Level]
, CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
WHERE [Node].[ParentId] = 0
UNION ALL
SELECT [Node].[Id]
, [Node].[ParentId]
, [NodeList].[Level] + 1 AS [Level]
, [NodeList].[Order] + '|'
+ CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]
两者都会输出以下结果。
Name 'Node 1' ' Node 1.1' ' Node 1.1.1' ' Node 1.2' 'Node 2' ' Node 2.1'链接地址: http://www.djcxy.com/p/5159.html
上一篇: What is the most efficient/elegant way to parse a flat table into a tree?