MySQL多层级结构-树搜索
亿网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(我们还没有发现性能很差)。
文章转载来自：trustauth.cn