分层数据 Hierarchical Data 探索 (2.邻接表模型)

分层数据 Hierarchical Data 探索 (2.邻接表模型)

分层数据Hierarchical Data探索(例如:无限级分类、多级菜单、省份城市)

引言

第一篇 分层数据Hierarchical Data探索(1.递归)已经介绍了分层数据以及使用递归算法实现了无限极分类,但是递归即浪费时间,又浪费空间(内存),尤其是在数据量大的情况下效率显著下降。
那么,在MySQL中如何处理分层数据呢?下面我们来说一说数据模型邻接表模型

邻接表模型(Adjacency List Model)

更多 邻接表模型(Adjacency List Model)的介绍请见:wiki

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# 为了模拟,我们创建一个表category包含三个字段:id,title,和parent_id如下:
CREATE TABLE category (
id int(10) unsigned NOT NULL AUTO_INCREMENT,
title varchar(255) NOT NULL,
parent_id int(10) unsigned DEFAULT NULL,
PRIMARY KEY (id),
FOREIGN KEY (parent_id) REFERENCES category (id)
ON DELETE CASCADE ON UPDATE CASCADE
);

# 插入模拟数据
INSERT INTO category(title,parent_id) VALUES('Electronics',NULL);

INSERT INTO category(title,parent_id) VALUES('Laptops & PC',1);

INSERT INTO category(title,parent_id) VALUES('Laptops',2);
INSERT INTO category(title,parent_id) VALUES('PC',2);

INSERT INTO category(title,parent_id) VALUES('Cameras & photo',1);
INSERT INTO category(title,parent_id) VALUES('Camera',5);

INSERT INTO category(title,parent_id) VALUES('Phones & Accessories',1);
INSERT INTO category(title,parent_id) VALUES('Smartphones',7);

INSERT INTO category(title,parent_id) VALUES('Android',8);
INSERT INTO category(title,parent_id) VALUES('iOS',8);
INSERT INTO category(title,parent_id) VALUES('Other Smartphones',8);

INSERT INTO category(title,parent_id) VALUES('Batteries',7);
INSERT INTO category(title,parent_id) VALUES('Headsets',7);
INSERT INTO category(title,parent_id) VALUES('Screen Protectors',7);

select * from category;
+----+----------------------+-----------+
| id | title | parent_id |
+----+----------------------+-----------+
| 1 | Electronics | NULL |
| 2 | Laptops & PC | 1 |
| 3 | Laptops | 2 |
| 4 | PC | 2 |
| 5 | Cameras & photo | 1 |
| 6 | Camera | 5 |
| 7 | Phones & Accessories | 1 |
| 8 | Smartphones | 7 |
| 9 | Android | 8 |
| 10 | iOS | 8 |
| 11 | Other Smartphones | 8 |
| 12 | Batteries | 7 |
| 13 | Headsets | 7 |
| 14 | Screen Protectors | 7 |
+----+----------------------+-----------+
14 rows in set (0.00 sec)
  • 检索根节点
1
2
3
4
5
6
7
SELECT * FROM category WHERE parent_id IS NULL;
+----+-------------+-----------+
| id | title | parent_id |
+----+-------------+-----------+
| 1 | Electronics | NULL |
+----+-------------+-----------+
1 row in set (0.00 sec)
  • 检索所有叶子节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
SELECT
c1.id, c1.title
FROM
category c1
LEFT JOIN
category c2 ON c2.parent_id = c1.id
WHERE
c2.id IS NULL;
+----+-------------------+
| id | title |
+----+-------------------+
| 3 | Laptops |
| 4 | PC |
| 6 | Camera |
| 9 | Android |
| 10 | iOS |
| 11 | Other Smartphones |
| 12 | Batteries |
| 13 | Headsets |
| 14 | Screen Protectors |
+----+-------------------+
9 rows in set (0.00 sec)
  • 检索整棵树的分层路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
SELECT t1.title AS lev1, t2.title as lev2, t3.title as lev3, t4.title as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent_id = t1.id
LEFT JOIN category AS t3 ON t3.parent_id = t2.id
LEFT JOIN category AS t4 ON t4.parent_id = t3.id
WHERE t1.title = 'Electronics';
-------------+----------------------+-------------------+-------------------+
| lev1 | lev2 | lev3 | lev4 |
+-------------+----------------------+-------------------+-------------------+
| Electronics | Laptops & PC | Laptops | NULL |
| Electronics | Laptops & PC | PC | NULL |
| Electronics | Cameras & photo | Camera | NULL |
| Electronics | Phones & Accessories | Smartphones | Android |
| Electronics | Phones & Accessories | Smartphones | iOS |
| Electronics | Phones & Accessories | Smartphones | Other Smartphones |
| Electronics | Phones & Accessories | Batteries | NULL |
| Electronics | Phones & Accessories | Headsets | NULL |
| Electronics | Phones & Accessories | Screen Protectors | NULL |
+-------------+----------------------+-------------------+-------------------+
9 rows in set (0.00 sec)
  • 检索单一指定路径
1
2
3
4
5
6
7
8
9
10
11
12
SELECT t1.title AS lev1, t2.title as lev2, t3.title as lev3, t4.title as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent_id = t1.id
LEFT JOIN category AS t3 ON t3.parent_id = t2.id
LEFT JOIN category AS t4 ON t4.parent_id = t3.id
WHERE t1.title = 'Electronics' AND t4.title = 'iOS';
+-------------+----------------------+-------------+------+
| lev1 | lev2 | lev3 | lev4 |
+-------------+----------------------+-------------+------+
| Electronics | Phones & Accessories | Smartphones | iOS |
+-------------+----------------------+-------------+------+
1 row in set (0.00 sec)

以下递归公用表达式(CTE)检索。请注意,MySQL 8.0以上版本,CTE功能已经支持

  • CTE 查询整棵树
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
27
28
29
30
31
WITH RECURSIVE category_path (id, title, path) AS
(
SELECT id, title, title as path
FROM category
WHERE parent_id IS NULL
UNION ALL
SELECT c.id, c.title, CONCAT(cp.path, ' > ', c.title)
FROM category_path AS cp JOIN category AS c
ON cp.id = c.parent_id
)
SELECT * FROM category_path
ORDER BY path;
+------+----------------------+----------------------------------------------------------------------+
| id | title | path |
+------+----------------------+----------------------------------------------------------------------+
| 1 | Electronics | Electronics |
| 5 | Cameras & photo | Electronics > Cameras & photo |
| 6 | Camera | Electronics > Cameras & photo > Camera |
| 2 | Laptops & PC | Electronics > Laptops & PC |
| 3 | Laptops | Electronics > Laptops & PC > Laptops |
| 4 | PC | Electronics > Laptops & PC > PC |
| 7 | Phones & Accessories | Electronics > Phones & Accessories |
| 12 | Batteries | Electronics > Phones & Accessories > Batteries |
| 13 | Headsets | Electronics > Phones & Accessories > Headsets |
| 14 | Screen Protectors | Electronics > Phones & Accessories > Screen Protectors |
| 8 | Smartphones | Electronics > Phones & Accessories > Smartphones |
| 9 | Android | Electronics > Phones & Accessories > Smartphones > Android |
| 10 | iOS | Electronics > Phones & Accessories > Smartphones > iOS |
| 11 | Other Smartphones | Electronics > Phones & Accessories > Smartphones > Other Smartphones |
+------+----------------------+----------------------------------------------------------------------+
14 rows in set (0.01 sec)
  • CTE 查询指定子树

查询id为 7 的 Phone & Accessories 的子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
WITH RECURSIVE category_path (id, title, path) AS
(
SELECT id, title, title as path
FROM category
WHERE parent_id = 7
UNION ALL
SELECT c.id, c.title, CONCAT(cp.path, ' > ', c.title)
FROM category_path AS cp JOIN category AS c
ON cp.id = c.parent_id
)
SELECT * FROM category_path
ORDER BY path;
+------+-------------------+---------------------------------+
| id | title | path |
+------+-------------------+---------------------------------+
| 12 | Batteries | Batteries |
| 13 | Headsets | Headsets |
| 14 | Screen Protectors | Screen Protectors |
| 8 | Smartphones | Smartphones |
| 9 | Android | Smartphones > Android |
| 10 | iOS | Smartphones > iOS |
| 11 | Other Smartphones | Smartphones > Other Smartphones |
+------+-------------------+---------------------------------+
7 rows in set (0.01 sec)

  • CTE 查询单个枝叶路径

从底部 iOS 到 顶部 Electronics 的单个路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
WITH RECURSIVE category_path (id, title, parent_id) AS
(
SELECT id, title, parent_id
FROM category
WHERE id = 10 -- child node
UNION ALL
SELECT c.id, c.title, c.parent_id
FROM category_path AS cp JOIN category AS c
ON cp.parent_id = c.id
)
SELECT * FROM category_path;
+------+----------------------+-----------+
| id | title | parent_id |
+------+----------------------+-----------+
| 10 | iOS | 8 |
| 8 | Smartphones | 7 |
| 7 | Phones & Accessories | 1 |
| 1 | Electronics | NULL |
+------+----------------------+-----------+
4 rows in set (0.00 sec)

  • CTE 计算每个节点的层级

根节点为 0,每个子节点等于父节点加 1

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
27
28
29
30
31
WITH RECURSIVE category_path (id, title, lvl) AS
(
SELECT id, title, 0 AS lvl
FROM category
WHERE parent_id IS NULL
UNION ALL
SELECT c.id, c.title,cp.lvl + 1
FROM category_path AS cp JOIN category AS c
ON cp.id = c.parent_id
)
SELECT * FROM category_path
ORDER BY lvl;
+------+----------------------+------+
| id | title | lvl |
+------+----------------------+------+
| 1 | Electronics | 0 |
| 2 | Laptops & PC | 1 |
| 5 | Cameras & photo | 1 |
| 7 | Phones & Accessories | 1 |
| 4 | PC | 2 |
| 6 | Camera | 2 |
| 8 | Smartphones | 2 |
| 12 | Batteries | 2 |
| 13 | Headsets | 2 |
| 14 | Screen Protectors | 2 |
| 3 | Laptops | 2 |
| 11 | Other Smartphones | 3 |
| 9 | Android | 3 |
| 10 | iOS | 3 |
+------+----------------------+------+
14 rows in set (0.00 sec)

  • 删除节点及其子节点

要删除节点及其子节点,只需删除节点本身,所有子节点将由 DELETE CASCADE 外键约束自动删除
例如:要删除Laptops & PC节点及其子节点

1
DELETE FROM category WHERE id = 2;

  • 删除节点并提升其子节点

    1. 首先,parent_id将节点的直接子节点更新为id新父节点的子节点。
    2. 然后,删除该节点。

例如,要删除 Smartphones 节点和更新 Android,iOS,Other Smartphones 节点:
两个语句都应该包含在一个事务中:

1
2
3
4
5
6
7
8
9
10
11
12
13
BEGIN;

UPDATE category
SET
parent_id = 7 -- Phones & Accessories
WHERE
parent_id = 5; -- Smartphones

DELETE FROM category
WHERE
id = 8;

COMMIT;

参考资源

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×