是否可以在单个查询中查询 MySQL 中的树结构表，任何深度？

Is it possible to query a tree structure table in MySQL in a single query, to any depth?

提问by Cameron Booth

I'm thinking the answer is no, but I'd love it it anybody had any insight into how to crawl a tree structure to any depth in SQL (MySQL), but with a single query

我认为答案是否定的，但我很高兴有人对如何在 SQL (MySQL) 中将树结构爬到任何深度有任何见解，但只需要一个查询

More specifically, given a tree structured table (id, data, data, parent_id), and one row in the table, is it possible to get alldescendants (child/grandchild/etc), or for that matter all ancestors (parent/grandparent/etc) without knowing how far down or up it will go, using a single query?

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

Or is using some kind of recursion require, where I keep querying deeper until there are no new results?

还是使用某种递归要求，在那里我继续深入查询，直到没有新结果？

Specifically, I'm using Ruby and Rails, but I'm guessing that's not very relevant.

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

回答by Dave Cheney

Yes, this is possible, it's a called a Modified Preorder Tree Traversal, as best described here

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

Joe Celko's Trees and Hierarchies in SQL for Smarties

Joe Celko 在 SQL for Smarties 中的树和层次结构

A working example (in PHP) is provided here

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

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

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

回答by Aaron Jensen

Here are several resources:

这里有几个资源：

• http://forums.mysql.com/read.php?10,32818,32818#msg-32818
• Managing Hierarchical Data in MySQL
• http://lists.mysql.com/mysql/201896

• http://forums.mysql.com/read.php?10,32818,32818#msg-32818
• 在 MySQL 中管理分层数据
• http://lists.mysql.com/mysql/201896

Basically, you'll need to do some sort of cursor in a stored procedure or query or build an adjacency table. I'd avoid recursion outside of the db: depending on how deep your tree is, that could get really slow/sketchy.

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

回答by Kray

Daniel Beardsley's answer is not that bad a solution at all when the main questions you are asking are 'what are all my children' and 'what are all my parents'.

当您问的主要问题是“我所有的孩子是什么”和“我的父母都是什么”时，Daniel Beardsley 的回答根本不是一个糟糕的解决方案。

In response to Alex Weinstein, this method actually results in less updates to nodes on a parent movement than in the Celko technique. In Celko's technique, if a level 2 node on the far left moves to under a level 1 node on the far right, then pretty much every node in the tree needs updating, rather than just the node's children.

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

What I would say however is that Daniel possibly stores the path back to root the wrong way around.

然而，我要说的是，Daniel 可能会以错误的方式存储返回 root 的路径。

I would store them so that the query would be

我会存储它们，以便查询

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

This means that mysql can make use of an index on the 'ancestors' column, which it would not be able to do with a leading %.

这意味着 mysql 可以使用 'ancestors' 列上的索引，而使用前导 % 则无法做到这一点。

回答by Jason S

Celko's technique (nested sets) is pretty good. I also have used an adjacency table with fields "ancestor" and "descendant" and "distance" (e.g. direct children/parents have a distance of 1, grandchildren/grandparents have a distance of 2, etc).

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

This needs to be maintained, but is fairly easy to do for inserts: you use a transaction, then put the direct link (parent, child, distance=1) into the table, then INSERT IGNORE a SELECTion of existing parent&children by adding distances (I can pull up the SQL when I have a chance), which wants an index on each of the 3 fields for performance. Where this approach gets ugly is for deletions... you basically have to mark all the items that have been affected and then rebuild them. But an advantage of this is that it can handle arbitrary acyclic graphs, whereas the nested set model can only do straight hierarchies (e.g. each item except the root has one and only one parent).

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

回答by Daniel Beardsley

I came across this problem before and had one wacky idea. You could store a field in each record that is concatenated string of it's direct ancestors' idsall the way back to the root.

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

Imagine you had records like this (indentation implies heirarchy and the numbers are id, ancestors.

想象一下你有这样的记录（缩进意味着层次结构，数字是 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"

• 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》

Then to select the descendents of id:6, just do this

然后选择 id:6 的后代，只需这样做

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

Keeping the ancestors column up to date might be more trouble than it's worth to you, but it's feasible solution in any DB.

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

回答by guru_florida

This can definitely be done and it isn't that complicated for SQL. I've answered this question and provided a working example using mysql procedural code here:

这绝对可以完成，而且对于 SQL 来说并没有那么复杂。我已经回答了这个问题，并在此处提供了一个使用 mysql 程序代码的工作示例：

MySQL: How to find leaves in specific node

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

Booth: If you are satisfied, you should mark one of the answers as accepted.

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

回答by Big_Al_Tx

I used the "With Emulator" routine described in https://stackoverflow.com/questions/27013093/recursive-query-emulation-in-mysql(provided by https://stackoverflow.com/users/1726419/yossico). So far, I've gotten very good results (performance wise), but I don't have an abundance of data or a large number of descendents to search through/for.

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

回答by Daniel Spiewak

SQL isn't a Turing Complete language, which means you're not going to be able to perform this sort of looping. You can do some very clever things with SQL and tree structures, but I can't think of a way to describe a row which has a certain id "in its hierarchy" for a hierarchy of arbitrary depth.

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

Your best bet is something along the lines of what @Dan suggested, which is to just work your way through the tree in some other, more capable language. You can actually generate a query string in a general-purpose language using a loop, where the query is just some convoluted series of joins (or sub-queries) which reflects the depth of the hierarchy you are looking for. That would be more efficient than looping and multiple queries.

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

回答by Dan

You're almost definitely going to want to employ some recursion for that. And if you're doing that, then it would be trivial (in fact easier) to get the entire tree rather than bits of it to a fixed depth.

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

In really rough pseudo-code you'll want something along these lines:

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

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)
    }
}

Although in practice you'd rarely want to do something like this. It will be rather inefficient since it's making one request for every row in the table, so it'll only be sensible for either small tables, or trees that aren't nested too deeply. To be honest, in either case you probably want to limit the depth.

虽然在实践中你很少想做这样的事情。这将是相当低效的，因为它对表中的每一行发出一个请求，所以它只对小表或嵌套不太深的树才有意义。老实说，在任何一种情况下，您都可能希望限制深度。

However, given the popularity of these kinds of data structure, there may very well be some MySQL stuff to help you with this, specifically to cut down on the numbers of queries you need to make.

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

Edit: Having thought about it, it makes very little sense to make all these queries. If you're reading the entire table anyway, then you can just slurp the whole thing into RAM - assuming it's small enough!

编辑：考虑过之后，进行所有这些查询毫无意义。如果您无论如何都在阅读整个表格，那么您可以将整个内容放入 RAM 中 - 假设它足够小！