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(我们还没有发现性能很差)。
昵称:HH
QQ:275258836
ttlsa群交流沟通(QQ群②:6690706 QQ群③:168085569 QQ群④:415230207(新) 微信公众号:ttlsacom)
感觉本文内容不错,读后有收获?
逛逛衣服店,鼓励作者写出更好文章。
转载请注明:成长的对话 » MySQL多层级结构-树搜索