MySQL多层级结构-树搜索介绍

基本上在每个系统中都有那么几张表是自关联父子关系的结构。往往有很多人都是使用pid来做关联。在刚进入it行业时使用cakephp框架编写web的时候，使用它里面的一个acl plugin实现权限管理的时候。发现一个表结构硬是不明白是怎么回事。具体表结构如下：

create table acos (
 id integer(10) unsigned not null auto_increment,
 parent_id integer(10) default null,
 model varchar(255) default '',
 foreign_key integer(10) unsigned default null,
 alias varchar(255) default '',
 lft integer(10) default null,
 rght integer(10) default null,
 primary key (id)
);

我们可以看到上面 acos 表用有lft、rght这两个字段。起初我根本就不明白这两个是做什么用的，几次直接修改数据导致数据错乱。

1.2. 原理解释

其实这就是树的后续遍历的每个节点的左值、右值。如下图表示:

1.3. 树的使用（引用上图树结构）

构造数据

drop table if exists comment;
create table `comment` (
 `comment_id` int(11) default null,
 `left_num` int(11) default null,
 `right_num` int(11) default null
);

insert into `comment` values 
 (1,1,14),
 (2,2,5),
 (3,3,4),
 (4,6,13),
 (5,7,8),
 (6,9,12),
 (7,10,11);
 
create index idx$comment$left_num$right_num on `comment` (`left_num`, `right_num`);

查找 '节点4' 的所有子节点

思路:我们只要查找出 节点左值在 '节点4' 左值和右值之间的节点
通俗说法:能被 '节点4' 包住的节点,通过左节点和右节点来判断是否被 '节点4' 包住。

-- 获得 '节点4' 孩子
select c.*
from comment as p, comment as c
where c.left_num between p.left_num and p.right_num
 and p.comment_id = 4;
+------------+----------+-----------+
| comment_id | left_num | right_num |
+------------+----------+-----------+
|     4 |    6 |    13 |
|     5 |    7 |     8 |
|     6 |    9 |    12 |
|     7 |    10 |    11 |
+------------+----------+-----------+

查找 '节点6' 的所有父节点
思路: 找出 左值小于 '节点6' 并且 右值大于 '节点6' 的节点。
通俗说法: 找出那个节点能将 '节点6' 给包住。

-- 获得 '节点6' 父亲
select p.* 
from comment as p, comment as c
where c.left_num between p.left_num and p.right_num
 and c.comment_id = 6;
+------------+----------+-----------+
| comment_id | left_num | right_num |
+------------+----------+-----------+
|     1 |    1 |    14 |
|     4 |    6 |    13 |
|     6 |    9 |    12 |
+------------+----------+-----------+

计算 '节点4' 的深度
如果是mysql5.7 需要修改sql_mode

set session sql_mode = 'strict_trans_tables,no_zero_in_date,no_zero_date,error_for_division_by_zero,no_auto_create_user,no_engine_substitution';
select c.*,
 count(c.comment_id) as depth
from comment as p, comment as c
where c.left_num between p.left_num and p.right_num
 and c.comment_id = 4
group by c.comment_id;
+------------+----------+-----------+-------+
| comment_id | left_num | right_num | depth |
+------------+----------+-----------+-------+
|     4 |    6 |    13 |   2 |
+------------+----------+-----------+-------+

获取 '节点4' 的所有子节点, 和相关深度

select sub_child.*,
 (count(sub_parent.comment_id) - 1) as depth
from (
 select child.*
 from comment as parent, comment as child
 where child.left_num between parent.left_num and parent.right_num
  and parent.comment_id = 4
) as sub_child, (
 select child.*
 from comment as parent, comment as child
 where child.left_num between parent.left_num and parent.right_num
  and parent.comment_id = 4
) as sub_parent
where sub_child.left_num between sub_parent.left_num and sub_parent.right_num
group by sub_child.comment_id
order by sub_child.left_num;
+------------+----------+-----------+-------+
| comment_id | left_num | right_num | depth |
+------------+----------+-----------+-------+
|     4 |    6 |    13 |   0 |
|     5 |    7 |     8 |   1 |
|     6 |    9 |    12 |   1 |
|     7 |    10 |    11 |   2 |
+------------+----------+-----------+-------+

插入数据
数据的插入是一件相当麻烦的事，需要更新节点的所有父节点的右值和和所有孩子节点的 '左值、右值'
如上图，如果我们想为 '节点4' 添加一个孩子 '节点44'(为了不给自己挖坑，我们将添加的孩子放在父节点的最左边)，就是将 '节点44' 放在 '节点5' 的左边。如下图：

最终我们获得的结果，如下图：

上图 '紫色' 的是节点需要变更的左值和右值，'绿色' 的是新增节点的值。
更新思路：
1、将左值大于 '节点4' 的左值的节点的左值 加2。
2、将右值大于 '节点4' 的左值的节点的右值 加2。

-- 获得 '节点4' 和 '节点4'的第一个孩子的(节点5)的左右值
select c.*
from comment as p, comment as c
where c.left_num between p.left_num and p.right_num
 and p.comment_id = 4;
+------------+----------+-----------+
| comment_id | left_num | right_num |
+------------+----------+-----------+
|     4 |    6 |    13 |
|     5 |    7 |     8 |
... omit ...
-- 通过上面获得的信息更新 '节点4' 的父子几点的左右值
update comment set left_num = left_num + 2 where left_num > 6;
update comment set right_num = right_num + 2 where right_num > 6;

插入思路
1、将 '节点44' 的左值设置为 '节点4' 的左值 加1
2、将 '节点44' 的右值设置为 '节点4' 的左值 加2

insert into comment 
select 44, left_num + 1, left_num + 2
from comment where comment_id = 4;

验证

-- 获得 '节点4' 孩子
select c.*
from comment as p, comment as c
where c.left_num between p.left_num and p.right_num
 and p.comment_id = 4;
+------------+----------+-----------+
| comment_id | left_num | right_num |
+------------+----------+-----------+
|     4 |    6 |    15 |
|     5 |    9 |    10 |
|     6 |    11 |    14 |
|     7 |    12 |    13 |
|     44 |    7 |     8 |
+------------+----------+-----------+
-- 获得 '节点44' 父亲
select p.* 
from comment as p, comment as c
where c.left_num between p.left_num and p.right_num
 and c.comment_id = 44;
+------------+----------+-----------+
| comment_id | left_num | right_num |
+------------+----------+-----------+
|     1 |    1 |    16 |
|     4 |    6 |    15 |
|     44 |    7 |     8 |
+------------+----------+-----------+

1.4. 总结

这种树结构一般会用在查询多增加修改少的场景中（比如地区表，类别表之类的）。
在现实中其实还有些表的数据字段很多，并且具有层级关系。但是他们层级关系并不需要实时的那么准确(最终能达到数据数据一直就行)，这是我们会将这种层级关系的字段和主表分开放在另外一个表。这样为了加快更新。如果实时更新影响到了性能，这是我们会考虑使用kafka(我们还没有发现性能很差)。