从 MySQL 中的分层数据生成基于深度的树（无 CTE）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5291054/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Generating Depth based tree from Hierarchical Data in MySQL (no CTEs)
提问by bluedream
Hi For many days I have been working on this problem in MySQL, however I can not figure it out. Do any of you have suggestions?
嗨，我一直在 MySQL 中解决这个问题很多天了，但是我无法弄清楚。你们有什么建议吗？
Basically, I have a category table with domains like: id, name(name of category), and parent(id of parent of the category).
基本上，我有一个类别表，其中包含以下域：id、name（类别名称）和parent（类别的父级 ID）。
Example Data:
示例数据：
1 Fruit 0
2 Apple 1
3 pear 1
4 FujiApple 2
5 AusApple 2
6 SydneyAPPLE 5
....
There are many levels, possibly more than 3 levels. I want to create an sql query that groups the datas according to he hierarchy: parent > child > grandchild > etc.
有很多层次，可能超过3个层次。我想创建一个 sql 查询，根据他的层次结构对数据进行分组：父 > 子 > 孙子 > 等。
It should output the tree structure, as follows:
它应该输出树结构，如下所示：
1 Fruit 0
^ 2 Apple 1
^ 4 FujiApple 2
- 5 AusApple 2
^ 6 SydneyApple 5
- 3 pear 1
Can I do this using a single SQL query? The alternative, which I tried and does work, is the following:
我可以使用单个 SQL 查询执行此操作吗？我尝试过并且确实有效的替代方法如下：
SELECT * FROM category WHERE parent=0
After this, I loop through the data again, and select the rows where parent=id. This seems like a bad solution. Because it is mySQL, CTEs cannot be used.
在此之后，我再次遍历数据，并选择 parent=id 的行。这似乎是一个糟糕的解决方案。因为是mySQL，所以不能使用CTE。
回答by Jon Black
You can do it in a single call from php to mysql if you use a stored procedure:
如果您使用存储过程，则可以在从 php 到 mysql 的单个调用中完成：
Example calls
示例调用
mysql> call category_hier(1);
+--------+---------------+---------------+----------------------+-------+
| cat_id | category_name | parent_cat_id | parent_category_name | depth |
+--------+---------------+---------------+----------------------+-------+
| 1 | Location | NULL | NULL | 0 |
| 3 | USA | 1 | Location | 1 |
| 4 | Illinois | 3 | USA | 2 |
| 5 | Chicago | 3 | USA | 2 |
+--------+---------------+---------------+----------------------+-------+
4 rows in set (0.00 sec)
$sql = sprintf("call category_hier(%d)", $id);
Hope this helps :)
希望这可以帮助 ：）
Full script
完整脚本
Test table structure:
测试表结构：
drop table if exists categories;
create table categories
(
cat_id smallint unsigned not null auto_increment primary key,
name varchar(255) not null,
parent_cat_id smallint unsigned null,
key (parent_cat_id)
)
engine = innodb;
Test data:
测试数据：
insert into categories (name, parent_cat_id) values
('Location',null),
('USA',1),
('Illinois',2),
('Chicago',2),
('Color',null),
('Black',3),
('Red',3);
Procedure:
程序：
drop procedure if exists category_hier;
delimiter #
create procedure category_hier
(
in p_cat_id smallint unsigned
)
begin
declare v_done tinyint unsigned default 0;
declare v_depth smallint unsigned default 0;
create temporary table hier(
parent_cat_id smallint unsigned,
cat_id smallint unsigned,
depth smallint unsigned default 0
)engine = memory;
insert into hier select parent_cat_id, cat_id, v_depth from categories where cat_id = p_cat_id;
/* http://dev.mysql.com/doc/refman/5.0/en/temporary-table-problems.html */
create temporary table tmp engine=memory select * from hier;
while not v_done do
if exists( select 1 from categories p inner join hier on p.parent_cat_id = hier.cat_id and hier.depth = v_depth) then
insert into hier
select p.parent_cat_id, p.cat_id, v_depth + 1 from categories p
inner join tmp on p.parent_cat_id = tmp.cat_id and tmp.depth = v_depth;
set v_depth = v_depth + 1;
truncate table tmp;
insert into tmp select * from hier where depth = v_depth;
else
set v_done = 1;
end if;
end while;
select
p.cat_id,
p.name as category_name,
b.cat_id as parent_cat_id,
b.name as parent_category_name,
hier.depth
from
hier
inner join categories p on hier.cat_id = p.cat_id
left outer join categories b on hier.parent_cat_id = b.cat_id
order by
hier.depth, hier.cat_id;
drop temporary table if exists hier;
drop temporary table if exists tmp;
end #
Test runs:
测试运行：
delimiter ;
call category_hier(1);
call category_hier(2);
Some performance testing using Yahoo geoplanet places data
使用 Yahoo geoplanet 放置数据的一些性能测试
drop table if exists geoplanet_places;
create table geoplanet_places
(
woe_id int unsigned not null,
iso_code varchar(3) not null,
name varchar(255) not null,
lang varchar(8) not null,
place_type varchar(32) not null,
parent_woe_id int unsigned not null,
primary key (woe_id),
key (parent_woe_id)
)
engine=innodb;
mysql> select count(*) from geoplanet_places;
+----------+
| count(*) |
+----------+
| 5653967 |
+----------+
so that's 5.6 million rows (places) in the table let's see how the adjacency list implementation/stored procedure called from php handles that.
所以这是表中的 560 万行（位置）让我们看看从 php 调用的邻接列表实现/存储过程是如何处理的。
1 records fetched with max depth 0 in 0.001921 secs
250 records fetched with max depth 1 in 0.004883 secs
515 records fetched with max depth 1 in 0.006552 secs
822 records fetched with max depth 1 in 0.009568 secs
918 records fetched with max depth 1 in 0.009689 secs
1346 records fetched with max depth 1 in 0.040453 secs
5901 records fetched with max depth 2 in 0.219246 secs
6817 records fetched with max depth 1 in 0.152841 secs
8621 records fetched with max depth 3 in 0.096665 secs
18098 records fetched with max depth 3 in 0.580223 secs
238007 records fetched with max depth 4 in 2.003213 secs
Overall i'm pretty pleased with those cold runtimes as I wouldn't even begin to consider returning tens of thousands of rows of data to my front end but would rather build the tree dynamically fetching only several levels per call. Oh and just incase you were thinking innodb is slower than myisam - the myisam implementation I tested was twice as slow in all counts.
总的来说，我对这些冷运行时间非常满意，因为我什至不会考虑将数万行数据返回到我的前端，而是宁愿构建树，每次调用只获取几个级别。哦，以防万一你认为 innodb 比 myisam 慢——我测试的 myisam 实现在所有方面都慢了两倍。
More stuff here : http://pastie.org/1672733
这里有更多的东西：http: //pastie.org/1672733
Hope this helps :)
希望这可以帮助 ：）
回答by Ted Hopp
There are two common ways of storing hierarchical data in an RDBMS: adjacency lists (which you are using) and nested sets. There is a very good write-up about these alternatives in Managing Hierarchical Data in MySQL. You can only do what you want in a single query with the nested set model. However, the nested set model makes it more work to update the hierarchical structure, so you need to consider the trade-offs depending on your operational requirements.
在 RDBMS 中存储分层数据有两种常用方法：邻接列表（您正在使用）和嵌套集。在管理 MySQL 中的分层数据中有一篇关于这些替代方案的非常好的文章。您只能使用嵌套集模型在单个查询中执行您想要的操作。但是，嵌套集模型使得更新层次结构的工作量更大，因此您需要根据您的操作需求考虑权衡。
回答by CyberDude
You can't achieve this using a single query. Your hierarchical data model is ineffective in this case. I suggest you try two other ways of storing hierarchical data in a database: the MPTT model or the "lineage" model. Using either of those models allows you to do the select you want in a single go.
您无法使用单个查询来实现这一点。在这种情况下，您的分层数据模型无效。我建议您尝试另外两种在数据库中存储分层数据的方法：MPTT 模型或“沿袭”模型。使用这些模型中的任何一个都可以让您一次性完成所需的选择。
Here is an article with further details: http://articles.sitepoint.com/article/hierarchical-data-database
这是一篇包含更多详细信息的文章：http: //articles.sitepoint.com/article/hierarchical-data-database
回答by Moshe L
The linear way:
线性方式：
I am using a ugly function to create a tree in a simple string field.
我正在使用一个丑陋的函数在一个简单的字符串字段中创建一棵树。
/ topic title
/001 message 1
/002 message 2
/002/001 reply to message 2
/002/001/001/ reply to reply
/003 message 3
etc...
the table can be used to select all the rows in the tree order with a simple SQL Query:
该表可用于通过简单的 SQL 查询选择树顺序中的所有行：
select * from morum_messages where m_topic=1234 order by m_linear asc
select * from morum_messages where m_topic=1234 order by m_linear asc
INSERTis just select the parent linear (and children) and calculate the string as needed.
INSERT只需选择父线性（和子级）并根据需要计算字符串。
select M_LINEAR FROM forum_messages WHERE m_topic = 1234 and M_LINEAR LIKE '{0}/___' ORDER BY M_LINEAR DESC limit 0,1
/* {0} - m_linear of the parent message*/
DELETEis simple as delete the message, or delete by linear all replies of the parent one.
DELETE很简单，删除消息，或线性删除父级的所有回复。
