基本上在每个系统中都有那么几张表是自关联父子关系的结构。往往有很多人都是使用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(我们还没有发现性能很差)。
MySQL,树搜索
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
更新日志
- 小骆驼-《草原狼2(蓝光CD)》[原抓WAV+CUE]
- 群星《欢迎来到我身边 电影原声专辑》[320K/MP3][105.02MB]
- 群星《欢迎来到我身边 电影原声专辑》[FLAC/分轨][480.9MB]
- 雷婷《梦里蓝天HQⅡ》 2023头版限量编号低速原抓[WAV+CUE][463M]
- 群星《2024好听新歌42》AI调整音效【WAV分轨】
- 王思雨-《思念陪着鸿雁飞》WAV
- 王思雨《喜马拉雅HQ》头版限量编号[WAV+CUE]
- 李健《无时无刻》[WAV+CUE][590M]
- 陈奕迅《酝酿》[WAV分轨][502M]
- 卓依婷《化蝶》2CD[WAV+CUE][1.1G]
- 群星《吉他王(黑胶CD)》[WAV+CUE]
- 齐秦《穿乐(穿越)》[WAV+CUE]
- 发烧珍品《数位CD音响测试-动向效果(九)》【WAV+CUE】
- 邝美云《邝美云精装歌集》[DSF][1.6G]
- 吕方《爱一回伤一回》[WAV+CUE][454M]