MySQL递归树搜索

Question

我有一个数据库的名称树，可以下去总共9层深，我需要能够从分支上的任何点搜索树的信号分支。

数据库：

+----------------------+ 
| id | name | parent | 
+----------------------+ 
| 1 | tom | 0 | 
| 2 | bob | 0 | 
| 3 | fred | 1 | 
| 4 | tim | 2 | 
| 5 | leo | 4 | 
| 6 | sam | 4 | 
| 7 | joe | 6 | 
| 8 | jay | 3 | 
| 9 | jim | 5 | 
+----------------------+ 

树：

tom 
fred 
    jay 
bob 
tim 
    sam 
    joe 
    leo 
    jim 

例如：

如果我搜索从用户 “鲍勃”， “J” 我应该得到只有“乔”和“吉姆”。如果我搜索“j”形式的“leo”，我只能得到“jim”。

我想不出任何简单的方法做到这一点，所以任何帮助表示赞赏。

Answer 1

你真的应该考虑使用Modified Preorder Tree Traversal这使得这样的查询更加容易。这是用MPTT表示的表格。我已经离开父领域，因为它使一些查询更容易。

+----------------------+-----+------+ 
| id | name | parent | lft | rght | 
+----------------------+-----+------+ 
| 1 | tom | 0 | 1 | 6 | 
| 2 | bob | 0 | 7 | 18 | 
| 3 | fred | 1 | 2 | 5 | 
| 4 | tim | 2 | 8 | 17 | 
| 5 | leo | 4 | 12 | 15 | 
| 6 | sam | 4 | 9 | 16 | 
| 7 | joe | 6 | 10 | 11 | 
| 8 | jay | 3 | 3 | 4 | 
| 9 | jim | 5 | 13 | 14 | 
+----------------------+-----+------+ 

要搜索j从用户bob你使用lft和rght值bob：

SELECT * FROM table WHERE name LIKE 'j%' AND lft > 7 AND rght < 18 

实现逻辑更新lft和rght添加，删除和重新排序节点可以是一个挑战（提示：如果可以，请使用现有的库），但查询将变得轻而易举。

Answer 2

有没有一个很好/简单的方法做到这一点;数据库不能很好地支持树型数据结构。

您需要逐层地工作来修剪从子到父的结果，或者创建一个从给定节点给出所有9代的视图，并使用后代的OR进行匹配。

Answer 3

你有没有想过使用递归循环？我使用了一个循环来构建一个cms，我在codeigniter的基础上构建了一个cms，允许我在站点树中的任意位置启动，然后过滤所有的孩子>盛大的孩子>伟大的孩子等等。另外，它使sql下降到快速缩短查询与大量复杂的连接相反。它可能需要一些修改你的情况，但我认为它可以工作。

/** 
* build_site_tree 
* 
* @return void 
* @author Mike Waites 
**/ 
public function build_site_tree($parent_id) 
{ 
    return $this->find_children($parent_id); 
} 

/** end build_site_tree **/ 

// ----------------------------------------------------------------------- 

/** 
* find_children 
* Recursive loop to find parent=>child relationships 
* 
* @return array $children 
* @author Mike Waites 
**/ 
public function find_children($parent_id) 
{ 
    $this->benchmark->mark('find_children_start'); 

    if(!class_exists('Account_model')) 
      $this->load->model('Account_model'); 

    $children = $this->Account_model->get_children($parent_id); 

    /** Recursively Loop over the results to build the site tree **/ 
    foreach($children as $key => $child) 
    { 
     $childs = $this->find_children($child['id']); 

     if (count($childs) > 0) 
       $children[$key]['children'] = $childs; 
    } 

    return $children; 

    $this->benchmark->mark('find_children_end'); 
} 

/** end find_children **/ 

正如你可以看到这是一记漂亮的simplfied版本和熊本已建成笨，所以你需要将它modyfy到套房，但基本上我们有一个循环调用自身添加到每一个数组时间。这将允许您获取整棵树，或者甚至可以从树中的某个点开始，只要您首先有parent_id！

希望这有助于

Answer 4

没有单个SQL查询将以树形格式返回数据 - 您需要处理以正确的顺序遍历它。

一种方法是查询的MySQL返回MPTT：

SELECT * FROM表ORDER BY父ASC;

根树的将是表中的第一项，它的子将是下等，树被列“广度优先”（在深度增加的层）

然后使用PHP处理数据，把它变成一个拥有数据结构的对象。

或者，您可以实现给定节点的MySQL搜索函数，递归搜索并返回其所有后代的表或其所有祖先的表。由于这些过程往往比较缓慢（即递归，返回的数据太多而被其他条件过滤掉），所以如果您知道自己不是一次又一次地查询这类数据，或者如果您知道数据集保持小

Answer 5

您可以按如下与存储过程做到这一点（9级深，有多宽？）：

调用示例

mysql> call names_hier(1, 'a'); 
+----+----------+--------+-------------+-------+ 
| id | emp_name | parent | parent_name | depth | 
+----+----------+--------+-------------+-------+ 
| 2 | ali  |  1 | f00   |  1 | 
| 8 | anna  |  6 | keira  |  4 | 
+----+----------+--------+-------------+-------+ 
2 rows in set (0.00 sec) 

mysql> call names_hier(3, 'k'); 
+----+----------+--------+-------------+-------+ 
| id | emp_name | parent | parent_name | depth | 
+----+----------+--------+-------------+-------+ 
| 6 | keira |  5 | eva   |  2 | 
+----+----------+--------+-------------+-------+ 
1 row in set (0.00 sec) 

$sqlCmd = sprintf("call names_hier(%d,'%s')", $id, $name); // dont forget to escape $name 
$result = $db->query($sqlCmd); 

完整剧本

drop table if exists names; 
create table names 
(
id smallint unsigned not null auto_increment primary key, 
name varchar(255) not null, 
parent smallint unsigned null, 
key (parent) 
) 
engine = innodb; 

insert into names (name, parent) values 
('f00',null), 
    ('ali',1), 
    ('megan',1), 
     ('jessica',3), 
     ('eva',3), 
     ('keira',5), 
      ('mandy',6), 
      ('anna',6); 

drop procedure if exists names_hier; 

delimiter # 

create procedure names_hier 
(
in p_id smallint unsigned, 
in p_name varchar(255) 
) 
begin 

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

set p_name = trim(replace(p_name,'%','')); 

create temporary table hier(
parent smallint unsigned, 
id smallint unsigned, 
depth smallint unsigned 
)engine = memory; 

insert into hier select parent, id, v_dpth from names where id = p_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 names n inner join tmp on n.parent = tmp.id and tmp.depth = v_dpth) then 

     insert into hier select n.parent, n.id, v_dpth + 1 
      from names n inner join tmp on n.parent = tmp.id and tmp.depth = v_dpth; 

     set v_dpth = v_dpth + 1;    

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

    else 
     set v_done = 1; 
    end if; 

end while; 


select 
n.id, 
n.name as emp_name, 
p.id as parent, 
p.name as parent_name, 
hier.depth 
from 
hier 
inner join names n on hier.id = n.id 
left outer join names p on hier.parent = p.id 
where 
n.name like concat(p_name, '%'); 

drop temporary table if exists hier; 
drop temporary table if exists tmp; 

end # 

delimiter ; 

-- call this sproc from your php 

call names_hier(1, 'a'); 
call names_hier(3, 'k'); 

Answer 6

新的“recursive with”构造将完成这项工作，但我不知道id MySQL是否支持它。

with recursive bobs(id) as (
    select id from t where name = 'bob' 
    union all 
    select t.id from t, bobs where t.parent_id = bobs.id 
) 
select t.name from t, bobs where t.id = bobs.id 
and name like 'j%'