MySQL多层级结构-树搜索-成长的对话

1.1. 背景

基本上在每个系统中都有那么几张表是自关联父子关系的结构。往往有很多人都是使用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)
);

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. 原理解释

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

mysql

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`);

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 |
+------------+----------+-----------+

-- 获得 '节点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 |
+------------+----------+-----------+

-- 获得 '节点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 |
+------------+----------+-----------+-------+

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 ;

+ -- -- -- -- -- -- + -- -- -- -- -- + -- -- -- -- -- - + -- -- -- - +

+ -- -- -- -- -- -- + -- -- -- -- -- + -- -- -- -- -- - + -- -- -- - +

| 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 |
+------------+----------+-----------+-------+

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 ;

+ -- -- -- -- -- -- + -- -- -- -- -- + -- -- -- -- -- - + -- -- -- - +

+ -- -- -- -- -- -- + -- -- -- -- -- + -- -- -- -- -- - + -- -- -- - +

| 4 | 6 | 13 | 0 |

| 5 | 7 | 8 | 1 |

| 6 | 9 | 12 | 1 |

| 7 | 10 | 11 | 2 |

+ -- -- -- -- -- -- + -- -- -- -- -- + -- -- -- -- -- - + -- -- -- - +

插入数据

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

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

mysql

最终我们获得的结果，如下图：

mysql

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

更新思路：

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;

-- 获得 '节点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;

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 |
+------------+----------+-----------+

-- 获得 '节点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(我们还没有发现性能很差)。

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

感觉本文内容不错，读后有收获？

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

转载请注明：成长的对话 » MySQL多层级结构-树搜索

1.1. 背景

1.2. 原理解释

1.3. 树的使用（引用上图树结构）

1.4. 总结

与本文相关的文章