Get tree path in MySQL table

问题:

Perhaps the easiest approach to manage hierarchical data in MySQL databases is the adjacency list model. It is, give to every node a parent:

CREATE TABLE category(
category_id INT AUTO_INCREMENT PRIMARY KEY,
name VARCHAR(20) NOT NULL,
parent INT DEFAULT NULL);

It is easy to get the parent node, or even if there is a maximum tree depth, you can get the whole tree using this:

SELECT CONCAT_WS('/', `t3`.`name`, `t2`.`name`, `t1`.`name`) AS `path`
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'xxxxx';

That's enough in many cases, but how can you generalize this solution for trees deeper than 3 nodes? I.e. You may have a path like "Electronics/Audio/Transmiter/FM/Motorola".

Is it possible with only one query?

回答1:

here's a simple non recursive stored procedure that does the job:

drop table if exists employees;
create table employees
(
emp_id smallint unsigned not null auto_increment primary key,
name varchar(255) not null,
boss_id smallint unsigned null,
key (boss_id)
)
engine = innodb;

insert into employees (name, boss_id) values
('f00',null), 
  ('ali later',1), 
  ('megan fox',1), 
      ('jessica alba',3), 
      ('eva longoria',3), 
         ('keira knightley',5), 
            ('liv tyler',6), 
            ('sophie marceau',6);


drop procedure if exists employees_hier;

delimiter #

create procedure employees_hier
(
in p_emp_id smallint unsigned
)
begin

declare v_done tinyint unsigned default(0);
declare v_dpth smallint unsigned default(0);

create temporary table hier(
 boss_id smallint unsigned, 
 emp_id smallint unsigned, 
 depth smallint unsigned
)engine = memory;

insert into hier select boss_id, emp_id, v_dpth from employees where emp_id = p_emp_id;

/* http://dev.mysql.com/doc/refman/5.0/en/temporary-table-problems.html */

create temporary table emps engine=memory select * from hier;

while not v_done do

    if exists( select 1 from employees e inner join hier on e.boss_id = hier.emp_id and hier.depth = v_dpth) then

        insert into hier select e.boss_id, e.emp_id, v_dpth + 1 
            from employees e inner join emps on e.boss_id = emps.emp_id and emps.depth = v_dpth;

        set v_dpth = v_dpth + 1;            

        truncate table emps;
        insert into emps select * from hier where depth = v_dpth;

    else
        set v_done = 1;
    end if;

end while;

select 
 e.emp_id,
 e.name as emp_name,
 p.emp_id as boss_emp_id,
 p.name as boss_name,
 hier.depth
from 
 hier
inner join employees e on hier.emp_id = e.emp_id
left outer join employees p on hier.boss_id = p.emp_id;

drop temporary table if exists hier;
drop temporary table if exists emps;

end #

delimiter ;

-- call this sproc from your php

call employees_hier(1);

回答2:

As that article explains, you need to know the depth of a node to generate its path, which you do by generating separate queries for nodes at different depths. That is one of the reasons the nested set model is often preferred.

Getting a node's path from a nested set model, adapted from a Managing Hierarchical Data in MySQL example:

SELECT CONCAT(GROUP_CONCAT(parent.name 
                           ORDER BY parent.lft 
                           SEPARATOR '/'), 
              '/Motorola')
  FROM nested_category AS node,
       nested_category AS parent
  WHERE node.lft BETWEEN parent.lft AND parent.rgt
    AND node.name = 'Motorola'
;

回答3:

Yes, this solution is scalable, you can have as many children/parents as you want, you just need to update the indexes of all elements in table, every time when you insert new node. I think that this is described in this article

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/