MySQL多层级结构-树搜索

1.1. 背景

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

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

1.2. 原理解释

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

mysql

1.3. 树的使用(引用上图树结构)

  • 构造数据

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

思路:我们只要查找出 节点左值在 '节点4' 左值和右值之间的节点

通俗说法:能被 '节点4' 包住的节点,通过左节点和右节点来判断是否被 '节点4' 包住。

  • 查找 '节点6' 的所有父节点

思路: 找出 左值小于 '节点6' 并且 右值大于 '节点6' 的节点。

通俗说法: 找出那个节点能将 '节点6' 给包住。

  • 计算 '节点4' 的深度

如果是MySQL5.7 需要修改sql_mode

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

  • 插入数据

数据的插入是一件相当麻烦的事,需要更新节点的所有父节点的右值和和所有孩子节点的 '左值、右值'

如上图,如果我们想为 '节点4' 添加一个孩子 '节点44'(为了不给自己挖坑,我们将添加的孩子放在父节点的最左边),就是将 '节点44' 放在 '节点5' 的左边。如下图:

mysql

最终我们获得的结果,如下图:

mysql

上图 '紫色' 的是节点需要变更的左值和右值,'绿色' 的是新增节点的值。

更新思路:

1、将左值大于 '节点4' 的左值的节点的左值 加2。

2、将右值大于 '节点4' 的左值的节点的右值 加2。

插入思路

1、将 '节点44' 的左值设置为 '节点4' 的左值 加1

2、将 '节点44' 的右值设置为 '节点4' 的左值 加2

验证

1.4. 总结

这种树结构一般会用在查询多增加修改少的场景中(比如地区表,类别表之类的)。

在现实中其实还有些表的数据字段很多,并且具有层级关系。但是他们层级关系并不需要实时的那么准确(最终能达到数据数据一直就行),这是我们会将这种层级关系的字段和主表分开放在另外一个表。这样为了加快更新。如果实时更新影响到了性能,这是我们会考虑使用kafka(我们还没有发现性能很差)。

 

昵称:HH
QQ:275258836
ttlsa群交流沟通(QQ群②:6690706 QQ群③:168085569 QQ群④:415230207(新) 微信公众号:ttlsacom)

感觉本文内容不错,读后有收获?

逛逛衣服店,鼓励作者写出更好文章。

HH

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:1   其中:访客  1   博主  0

  1. 匿名 5

    太热特瑞特让他