我如何将当前的数据重组成数据库中的特定格式？
我如何将当前的数据重组成数据库中的特定格式？
假设您有一张存储有序树结构的平面表：
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（或纯文本）？
进一步假设您只有基本的数据结构（数组和哈希映射），没有带有父/子引用的高级对象，没有ORM，没有框架，只有您的双手。该表被表示为结果集，可以随机访问。
伪代码或纯英语都可以，这纯粹是一个概念性问题。
附加问题：在关系数据库管理系统中存储树形结构是否有根本上更好的方法？
编辑和补充
回答一个评论者（Mark Bessey）的问题：根节点并不是必需的，因为它永远不会被显示。ParentId = 0 是表示“这些是顶级”的约定。Order列定义了具有相同父级的节点的排序方式。
我所说的“结果集”可以被看作是一个哈希映射数组（保持在该术语中）。对于我的例子，它已经存在。一些答案会更加努力地先构建它，但这是可以的。
树的深度可以任意。每个节点可以有N个子节点。虽然我没有具体考虑过“数百万条条目”的树。
不要将我的节点命名选择（'Node 1.1.1'）视为依赖的东西。节点也可以叫做'Frank'或'Bob'，没有命名结构的暗示，这只是为了使其可读。
我已经发布了我的解决方案，所以你们可以拆解它。
如何将我当前的数据重组成数据库中的特定格式？
问题的出现原因：使用嵌套集（有时也称为修改的前序树遍历）可以使用一个查询提取整个树结构或其中任何子树，并按照树的顺序进行排序，但插入操作的代价更高，因为需要管理描述树结构中顺序路径的列。
解决方法：对于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列允许您为每个顶级节点重新开始lft和rght编号，从而减少插入、移动和删除所影响的列数，因为在进行这些操作时必须相应地调整lft和rght列以创建或关闭间隙。我在尝试理解每个操作所需的查询时，写了一些开发笔记。
在实际处理这些数据以显示树时，我创建了一个tree_item_iterator实用函数，对于每个节点，它应该提供足够的信息来生成您想要的任何显示方式。
关于MPTT的更多信息：
我希望我们停止使用像lft和rght这样的缩写作为列名，我的意思是我们需要多少个字符来输入？只有一个？！这是因为“left”和“right”是SQL中的保留字，所以我们只需始终用双引号“EVERYTHING”。
我想知道左/右表示法相对于左/大小表示法的优势，来自stackoverflow.com/a/42781302/895245的左/大小表示法似乎更新兄弟节点更简单。
我发现了一篇有趣的帖子，比较了Postgres 8中嵌套集与邻接列表的性能：explainextended.com/2009/09/24/…。简而言之：在某些操作中，邻接集的性能更快，而在性能较差的情况下，较差的程度是两倍。
如何将我的当前数据重组成数据库中的特定格式？
在MySQL 8.0开始支持递归查询之后，可以说现在所有流行的SQL数据库都支持标准语法中的递归查询。
我在2017年的演示中测试了MySQL 8.0中的递归查询。
下面是我2008年的原始答案：
在关系数据库中，有几种存储树形结构数据的方法。您在示例中展示的使用了两种方法：
邻接列表（"parent"列）和
路径枚举（名称列中的点号）。
另一种解决方案称为嵌套集，它也可以存储在同一张表中。请阅读Joe Celko的《SQL智者的树和层次结构》一书，了解更多关于这些设计的信息。
我通常更喜欢一种称为闭包表（也称为邻接关系）的设计来存储树形结构数据。它需要另一个表，但是查询树形结构非常简单。
我在我的演示《使用SQL和PHP处理层次数据的模型》以及我的书《SQL反模式卷1：避免数据库编程的陷阱》中介绍了闭包表。
将所有路径存储在闭包表中，其中一个节点直接从另一个节点派生。包括每个节点引用自身的行。例如，使用您在问题中展示的数据集：
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派生的。
关于对节点的直接子节点（或直接父节点）的评论，您可以在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);
然后，您可以在查询中添加一个术语，用于查询给定节点的直接子节点。这些是路径长度为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 |
+----+
如果想要按名称对整个树进行排序，可以使用以下查询：
SELECT f.name
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;
如果想要获取节点的路径，可以使用以下查询：
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;
以上是关于如何将当前数据重组成特定格式的问题的原因和解决方法的整理。
如何将当前的数据重构为数据库中的特定格式？
问题的原因：该问题的原因是作者希望将当前的数据重新组织成数据库中的特定格式，以方便查询和展示。
解决方法：作者提供了一种解决方法，即使用递归公共表表达式（CTEs）来读取树形结构。通过使用递归CTEs，可以一次性获取整个树形结构，了解节点的级别、父节点和在父节点的子节点中的顺序。
解决方法的具体步骤如下：
1. 创建一个结构化的表，并插入数据。
2. 编写一个查询语句，使用递归CTEs来获取树形结构。
在查询结果中，树的节点按照深度级别进行排序，并以连续的行进行展示。对于每个级别，它们按照父节点和在父节点中的顺序进行排序。这告诉我们如何在输出中将它们连接到父节点。具有这样的结构，很容易在HTML中进行漂亮的展示。
递归CTEs在PostgreSQL、IBM DB2、MS SQL Server、Oracle和SQLite中都可用。如果想要了解更多关于递归SQL查询的内容，可以查阅相关数据库管理系统的文档或者阅读作者撰写的两篇文章。
作者喜欢这种方法的简洁性，并且它通过最终的ORDER BY生成确定性的输出。然而，这种方法是广度优先遍历，而书的树形表示需要使用先序遍历。
文章中还提到的两个链接无法访问。