MySQL多层级结构-树搜索
时间:2016-07-17 00:39 来源:linux.it.net.cn 作者:IT
1.1. 背景
基本上在每个系统中都有那么几张表是自关联父子关系的结构。往往有很多人都是使用pid来做关联。在刚进入IT行业时使用CAKEPHP框架编写WEB的时候，使用它里面的一个ACL plugin实现权限管理的时候。发现一个表结构硬是不明白是怎么回事。具体表结构如下：
1
2
3
4
5
6
7
8
9
10
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. 树的使用（引用上图树结构）
-
构造数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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' 包住。
1
2
3
4
5
6
7
8
9
10
11
12
13
-- 获得 '节点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' 给包住。
1
2
3
4
5
6
7
8
9
10
11
12
-- 获得 '节点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
1
2
3
4
5
6
7
8
9
10
11
12
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' 的所有子节点, 和相关深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
-- 获得 '节点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
1
2
3
INSERT INTO comment
SELECT 44, left_num + 1, left_num + 2
FROM comment WHERE comment_id = 4;
验证
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
-- 获得 '节点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(我们还没有发现性能很差)。
(责任编辑：IT)
1.1. 背景基本上在每个系统中都有那么几张表是自关联父子关系的结构。往往有很多人都是使用pid来做关联。在刚进入IT行业时使用CAKEPHP框架编写WEB的时候，使用它里面的一个ACL plugin实现权限管理的时候。发现一个表结构硬是不明白是怎么回事。具体表结构如下：
我们可以看到上面 acos 表用有lft、rght这两个字段。起初我根本就不明白这两个是做什么用的，几次直接修改数据导致数据错乱。 1.2. 原理解释其实这就是树的后续遍历的每个节点的左值、右值。如下图表示:
1.3. 树的使用（引用上图树结构）
思路:我们只要查找出 节点左值在 '节点4' 左值和右值之间的节点 通俗说法:能被 '节点4' 包住的节点,通过左节点和右节点来判断是否被 '节点4' 包住。
思路: 找出 左值小于 '节点6' 并且 右值大于 '节点6' 的节点。 通俗说法: 找出那个节点能将 '节点6' 给包住。
如果是MySQL5.7 需要修改sql_mode
数据的插入是一件相当麻烦的事，需要更新节点的所有父节点的右值和和所有孩子节点的 '左值、右值' 如上图，如果我们想为 '节点4' 添加一个孩子 '节点44'(为了不给自己挖坑，我们将添加的孩子放在父节点的最左边)，就是将 '节点44' 放在 '节点5' 的左边。如下图：
最终我们获得的结果，如下图：
上图 '紫色' 的是节点需要变更的左值和右值，'绿色' 的是新增节点的值。 更新思路： 1、将左值大于 '节点4' 的左值的节点的左值 加2。 2、将右值大于 '节点4' 的左值的节点的右值 加2。
插入思路 1、将 '节点44' 的左值设置为 '节点4' 的左值 加1 2、将 '节点44' 的右值设置为 '节点4' 的左值 加2
验证
1.4. 总结这种树结构一般会用在查询多增加修改少的场景中（比如地区表，类别表之类的）。 在现实中其实还有些表的数据字段很多，并且具有层级关系。但是他们层级关系并不需要实时的那么准确(最终能达到数据数据一直就行)，这是我们会将这种层级关系的字段和主表分开放在另外一个表。这样为了加快更新。如果实时更新影响到了性能，这是我们会考虑使用kafka(我们还没有发现性能很差)。 (责任编辑：IT) |