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%'