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 cWHERE 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 cWHERE 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 depthFROM comment AS p, comment AS cWHERE c.left_num BETWEEN p.left_num AND p.right_num AND c.comment_id = 4GROUP 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 depthFROM （ SELECT child.* FROM comment AS parent, comment AS child WHERE child.left_num BETWEEN parent.left_num AND parent.right_numAND 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_numAND parent.comment_id = 4） AS sub_parentWHERE sub_child.left_num BETWEEN sub_parent.left_num AND sub_parent.right_numGROUP BY sub_child.comment_idORDER 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 cWHERE 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 + 2FROM comment WHERE comment_id = 4;

验证

-- 获得 "节点4" 孩子SELECT c.*FROM comment AS p, comment AS cWHERE 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 cWHERE 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（我们还没有发现性能很差）。