58

我认为答案是否定的，但我希望有人对如何在 SQL（MySQL）中将树结构爬行到任何深度有任何见解，但只需一个查询

更具体地说，给定一个树结构表（id、data、data、parent_id）和表中的一行，是否有可能获取所有后代（子/孙/等），或者就此而言所有祖先（父母/祖父母/etc) 不知道它会下降或上升多远，使用单个查询？

或者正在使用某种递归要求，我一直在深入查询直到没有新结果？

具体来说，我使用的是 Ruby 和 Rails，但我猜这不是很相关。

4

9 回答 9

37

是的，这是可能的，它被称为修改的预序树遍历，正如这里最好的描述

Joe Celko 为 Smarties 编写的 SQL 中的树和层次结构

此处提供了一个工作示例（在 PHP 中）

http://www.sitepoint.com/article/hierarchical-data-database/2/

于 2008-10-04T06:55:15.197 回答
23

这里有几个资源：

基本上，您需要在存储过程或查询中执行某种游标或构建邻接表。我会避免在数据库之外递归：取决于你的树有多深，这可能会变得非常慢/粗略。

于 2008-10-04T05:55:05.803 回答
3

当您要问的主要问题是“我的孩子都是什么”和“我的父母都是什么”时，丹尼尔比尔兹利的回答根本不是一个糟糕的解决方案。

作为对 Alex Weinstein 的回应，与 Celko 技术相比，这种方法实际上导致对父移动节点的更新更少。在 Celko 的技术中，如果最左边的 2 级节点移动到最右边的 1 级节点之下，那么树中的几乎每个节点都需要更新，而不仅仅是节点的子节点。

然而，我要说的是，丹尼尔可能以错误的方式将路径存储回根目录。

我会存储它们，以便查询

SELECT FROM table WHERE ancestors LIKE "1,2,6%"

这意味着 mysql 可以使用 'ancestors' 列上的索引，而它无法使用前导 % 来实现。

于 2012-03-05T15:07:14.083 回答
2

我之前遇到过这个问题并且有一个古怪的想法。您可以在每条记录中存储一个字段，该字段是其直接祖先的 id 的串联字符串，一直到根。

想象一下你有这样的记录（缩进意味着层次结构，数字是 id，祖先。

  • 1、“1”
    • 2、“2,1”
      • 5、“5,2,1”
      • 6、“6,2,1”
        • 7, "7,6,2,1"
        • 11, "11,6,2,1"
    • 3、“3,1”
      • 8、“8,3,1”
      • 9、“9,3,1”
      • 10, "10,3,1"

然后选择 id:6 的后代，只需执行此操作

SELECT FROM table WHERE ancestors LIKE "%6,2,1"

保持祖先列是最新的可能比它的价值更麻烦，但它在任何数据库中都是可行的解决方案。

于 2008-10-04T06:45:59.117 回答
2

Celko 的技术（嵌套集）非常好。我还使用了一个包含“祖先”、“后代”和“距离”字段的邻接表（例如，直系子女/父母的距离为 1，孙子女/祖父母的距离为 2，等等）。

这需要维护，但对于插入来说相当容易：您使用事务，然后将直接链接（父，子，距离 = 1）放入表中，然后通过添加距离插入忽略现有父和子的选择（如果有机会，我可以调出 SQL），它希望在 3 个字段中的每一个上都有一个索引以提高性能。这种方法变得丑陋的地方是删除......你基本上必须标记所有受到影响的项目，然后重建它们。但是这样做的一个优点是它可以处理任意的无环图，而嵌套集模型只能做直接的层次结构（例如，除了根之外的每个项目都有一个且只有一个父级）。

于 2008-12-08T19:43:21.063 回答
1

SQL 不是图灵完备的语言，这意味着您将无法执行这种循环。您可以使用 SQL 和树结构做一些非常聪明的事情，但我想不出一种方法来描述在“其层次结构中”具有特定 id 的行，用于任意深度的层次结构。

你最好的选择是按照@Dan 的建议，即用其他更强大的语言在树中工作。您实际上可以使用循环以通用语言生成查询字符串，其中查询只是一些复杂的连接（或子查询）系列，它反映了您正在寻找的层次结构的深度。这将比循环和多个查询更有效。

于 2008-10-04T06:07:57.337 回答
1

这绝对可以做到，对于 SQL 来说并不复杂。我已经回答了这个问题，并在此处提供了一个使用 mysql 程序代码的工作示例：

MySQL：如何在特定节点中查找叶子

Booth：如果您满意，您应该将其中一个答案标记为已接受。

于 2012-10-09T21:09:47.027 回答
1

我使用了https://stackoverflow.com/questions/27013093/recursive-query-emulation-in-mysql中描述的“With Emulator”例程（由https://stackoverflow.com/users/1726419/yossico提供）。到目前为止，我已经获得了非常好的结果（性能方面），但我没有大量数据或大量后代可供搜索/搜索。

于 2015-01-12T21:15:50.800 回答
-1

您几乎肯定会为此使用一些递归。如果你正在这样做，那么将整个树而不是它的一部分获得固定深度将是微不足道的（实际上更容易）。

在非常粗糙的伪代码中，您将需要以下内容：

getChildren(parent){
    children = query(SELECT * FROM table WHERE parent_id = parent.id)
    return children
}

printTree(root){
    print root
    children = getChildren(root)
    for child in children {
        printTree(child)
    }
}

虽然在实践中你很少想做这样的事情。这将是相当低效的，因为它对表中的每一行都发出一个请求，所以它只适用于小表或嵌套不太深的树。老实说，无论哪种情况，您都可能想限制深度。

然而，鉴于这些数据结构的流行，很可能有一些 MySQL 的东西可以帮助你解决这个问题，特别是减少你需要进行的查询数量。

编辑：考虑到这一点，进行所有这些查询几乎没有意义。如果您无论如何都在阅读整个表格，那么您可以将整个表格放入 RAM - 假设它足够小！

于 2008-10-04T05:54:58.983 回答