从 MySQL 中的分层数据生成基于深度的树(无 CTE)

2021-11-20 00:00:00 common-table-expression hierarchical-data mysql

多年来我一直在 MySQL 中解决这个问题，但是我无法弄清楚.大家有什么建议吗?

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?

基本上，我有一个类别表，其中包含以下域:id、name(类别名称)和 parent(父项的 id类别).

Basically, I have a category table with domains like: id, name (name of category), and parent (id of parent of the category).

示例数据:

1  Fruit        0
2  Apple        1
3  pear         1
4  FujiApple    2
5  AusApple     2
6  SydneyAPPLE  5
....

有很多级别，可能超过3个级别.我想创建一个 sql 查询，根据他的层次结构对数据进行分组:父 > 子 > 孙子 > 等等.

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.

它应该输出树结构，如下:

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

我可以使用单个 SQL 查询来执行此操作吗?我尝试过并且确实有效的替代方法如下:

Can I do this using a single SQL query? The alternative, which I tried and does work, is the following: 

SELECT * FROM category WHERE parent=0

此后，我再次遍历数据，并选择 parent=id 的行.这似乎是一个糟糕的解决方案.因为是mySQL，所以不能使用CTE.

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.

推荐答案

如果您使用存储过程，您可以在从 php 到 mysql 的单个调用中完成:

You can do it in a single call from php to mysql if you use a stored procedure:

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

希望这有帮助:)

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;

测试数据:

insert into categories (name, parent_cat_id) values
('Location',null),
   ('USA',1), 
      ('Illinois',2), 
      ('Chicago',2),  
('Color',null), 
   ('Black',3), 
   ('Red',3);

程序:

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 #

测试运行:

delimiter ;

call category_hier(1);

call category_hier(2);

一些使用 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 |
+----------+

表中有 560 万行(位置)，让我们看看从 php 调用的邻接列表实现/存储过程是如何处理的.

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.

     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

总的来说，我对那些冷运行时非常满意，因为我什至不会考虑将数万行数据返回到我的前端，而是宁愿构建树，每次调用只获取几个级别.哦，以防万一你认为 innodb 比 myisam 慢——我测试的 myisam 实现在所有方面都慢了两倍.

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.

更多内容:http://pastie.org/1672733

希望这有帮助:)

相关文章