假设你有一个扁平的表,存储一个有序的树层次结构:

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(或文本,就此而言),作为一个正确有序、正确缩进的树?

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

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

附加问题:在RDBMS中是否存在从根本上更好的方法来存储这样的树结构?


编辑和添加

回答一位评论者(Mark Bessey)的问题:根节点是不必要的,因为无论如何它都不会显示。ParentId = 0是表示“这些是顶级”的惯例。Order列定义了具有相同父节点的节点如何排序。

我所说的“结果集”可以被描绘成一个hashmap数组(继续使用这个术语)。因为我的例子本来就应该在那里。有些答案是额外的,首先构建它,但这没关系。

树可以任意深。每个节点可以有N个子节点。不过,我脑子里并没有“数百万条”树。

不要把我选择的节点命名(“节点1.1.1”)误认为是可以依赖的。节点也可以被称为“Frank”或“Bob”,没有隐含的命名结构,这只是为了让它更具可读性。

我已经发布了我自己的解决方案,所以你们可以把它拆成碎片。


当前回答

现在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年的演讲中测试了MySQL 8.0中的递归查询。

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


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

邻接表(“父”列)和 路径枚举(名称列中的虚线数字)。

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

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

我在演示中用SQL和PHP构建分层数据模型时提到了闭包表,在我的书《SQL反模式第1卷:避免数据库编程的陷阱》中也提到了闭包表。

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的所有后代节点,将它们连接到包含其他节点属性(如名称)的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         |
+------------+-------------+

一位用户建议今天进行编辑。版主批准了编辑,但我要撤销它。

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

如果您希望排序以合理的方式匹配层次结构,这是可能的,但不是简单地按路径长度排序。例如,请参阅我对MySQL闭包表分层数据库的回答-如何以正确的顺序提取信息。

其他回答

比尔的回答非常好,这个答案增加了一些东西,这让我希望SO支持线程的答案。

无论如何,我想要支持树结构和Order属性。我在每个Node中都包含了一个名为leftSibling的属性,它所做的事情与Order在原始问题中所做的事情相同(保持从左到右的顺序)。

mysql> desc nodes ;
+-------------+--------------+------+-----+---------+----------------+
| Field       | Type         | Null | Key | Default | Extra          |
+-------------+--------------+------+-----+---------+----------------+
| id          | int(11)      | NO   | PRI | NULL    | auto_increment |
| name        | varchar(255) | YES  |     | NULL    |                |
| leftSibling | int(11)      | NO   |     | 0       |                |
+-------------+--------------+------+-----+---------+----------------+
3 rows in set (0.00 sec)

mysql> desc adjacencies;
+------------+---------+------+-----+---------+----------------+
| Field      | Type    | Null | Key | Default | Extra          |
+------------+---------+------+-----+---------+----------------+
| relationId | int(11) | NO   | PRI | NULL    | auto_increment |
| parent     | int(11) | NO   |     | NULL    |                |
| child      | int(11) | NO   |     | NULL    |                |
| pathLen    | int(11) | NO   |     | NULL    |                |
+------------+---------+------+-----+---------+----------------+
4 rows in set (0.00 sec)

更多细节和SQL代码在我的博客。

谢谢你,比尔,你的回答对我的开始很有帮助!

假设你知道根元素是0,下面是输出到文本的伪代码:

function PrintLevel (int curr, int level)
    //print the indents
    for (i=1; i<=level; i++)
        print a tab
    print curr \n;
    for each child in the table with a parent of curr
        PrintLevel (child, level+1)


for each elementID where the parentid is zero
    PrintLevel(elementID, 0)

要扩展Bill的SQL解决方案,基本上可以使用平面数组来实现相同的功能。此外,如果你的字符串都有相同的长度,你的最大子代数是已知的(比如在一个二叉树中),你可以使用一个单一的字符串(字符数组)。如果你有任意数量的孩子,事情就会变得复杂一些……我必须检查我的旧笔记,看看能做些什么。

然后,牺牲一点内存,特别是如果你的树是稀疏的和/或不平衡的,你可以,通过一些索引数学,通过存储你的树随机访问所有的字符串,宽度优先在数组中,就像这样(对于二叉树):

String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...

你知道弦的长度,你知道 我现在在工作,所以不能花太多时间在上面,但有兴趣,我可以获取一些代码来做到这一点。 我们过去用它来搜索由DNA密码子组成的二叉树,一个构建树的过程,然后我们将其平铺以搜索文本模式,当找到时,尽管索引数学(从上面反向),我们将节点找回…非常快速和有效,我们的树很少有空节点,但我们可以在一瞬间搜索千兆字节的数据。

如果有选择的话,我会用对象。我将为每条记录创建一个对象,其中每个对象都有一个子集合,并将它们全部存储在一个assoc数组(/hashtable)中,其中Id是键。并在集合中闪动一次,将子元素添加到相关的子字段中。简单。

但是因为你限制一些好的OOP的使用是没有乐趣的,我可能会基于:

function PrintLine(int pID, int level)
    foreach record where ParentID == pID
        print level*tabs + record-data
        PrintLine(record.ID, level + 1)

PrintLine(0, 0)

编辑:这与其他几个条目类似,但我认为它稍微干净一些。我要补充一点:这是非常sql密集的。这是令人讨厌的。如果可以选择的话,选择面向对象的方法。

您可以使用hashmap模拟任何其他数据结构,因此这并不是一个可怕的限制。从上到下扫描,为数据库的每一行创建hashmap,为每一列创建一个条目。将这些hashmap添加到“master”hashmap中,并以id为键。如果任何节点都有一个尚未见过的“父”节点,请在主hashmap中为它创建一个占位符条目,并在看到实际节点时填充它。

要将其打印出来,只需对数据进行简单的深度优先遍历,并在此过程中跟踪缩进级别。您可以通过为每一行保留一个“子”条目,并在扫描数据时填充它来简化这一点。

至于是否有“更好”的方法在数据库中存储树,这取决于您将如何使用数据。我曾经见过一些系统,它们具有已知的最大深度,但却为层次结构中的每个级别使用不同的表。如果树中的级别并不完全相同(顶级类别与叶类别不同),那么这就很有意义了。