2

我有一个包含名称树的数据库，该名称树总共可以向下 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

例如：

如果我从用户“bob”中搜索“j”，我应该只得到“joe”和“jim”。如果我从“leo”中搜索“j”，我应该只得到“jim”。

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

4

6 回答 6

9

您真的应该考虑使用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添加、删除和重新排序节点的逻辑可能是一个挑战（提示：如果可以的话，使用现有的库）但查询将是一件轻而易举的事。

于 2011-04-20T06:54:00.090 回答
1

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

您将需要逐级工作以修剪从子到父的结果，或创建一个视图，从给定节点提供所有 9 代，并在后代上使用 OR 进行匹配。

于 2011-04-20T05:42:18.643 回答
1

您是否考虑过使用递归循环？我为我在 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 **/

正如您所看到的，这是一个非常简化的版本，请记住，它已内置在 codeigniter 中，因此您需要对其进行修改以适应套件，但基本上我们有一个循环，它每次都调用自己添加到数组中。这将允许您获取整棵树，甚至可以从树中的某个点开始，只要您首先拥有可用的 parent_id！

希望这可以帮助

于 2011-04-20T06:23:08.670 回答
1

新的“recursive with”构造将完成这项工作，但我不知道 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%'
于 2013-01-31T11:07:17.890 回答
0

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

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

SELECT * FROM table ORDER BY parent asc;

树的根将是表的第一项，它的子项将是下一个，依此类推，树被列为“广度优先”（按深度递增的层）

然后使用 PHP 处理数据，将其变成一个包含数据结构的对象。

或者，您可以实现给定节点的 MySQL 搜索函数，递归搜索并返回其所有后代的表或所有祖先的表。由于这些过程往往很慢（递归，返回太多数据，然后被其他条件过滤），你只想这样做，如果你知道你不是一次又一次地查询那种数据，或者如果你知道数据集仍然很小（9 级深，多宽？）

于 2011-04-20T07:50:45.747 回答
0

您可以使用存储过程执行此操作，如下所示：

示例调用

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');
于 2011-04-20T08:43:17.823 回答