在数据库中存储树状结构
问题
- 实际开发中很多地方都需要存储树状结构，例如组织架构中需要用树状结构来表示公司员工之间的层级关系、电商网站中用树状结构来组织商品分类、论坛帖子或者评论中可以通过回复来构成树状结构。
- 假设现在要存储一下公司的人员结构，大概层次如下
- 怎么存储这个结构？并且要获取以下信息
- 查询小天的直接上司；
- 查询老宋管理下的直属员工；
- 查询小天的所有上司；
- 查询老王管理的所有员工。
方案一 Adjacency List（存储父节点）
数据库存储结构
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-- ----------------------------
-- Table structure for employees
-- ----------------------------
DROP TABLE IF EXISTS `employees`;
CREATE TABLE `employees` (
`eid` int(11) NOT NULL COMMENT '主键ID',
`ename` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '姓名',
`position` varchar(100) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '位置',
`parent_id` int(11) NULL DEFAULT NULL COMMENT '上级ID',
PRIMARY KEY (`eid`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;
-- ----------------------------
-- Records of employees
-- ----------------------------
INSERT INTO `employees` VALUES (1, '老王', '高管', 0);
INSERT INTO `employees` VALUES (2, '老宋', '产品部主管', 1);
INSERT INTO `employees` VALUES (3, '老牛', '技术部主管', 1);
INSERT INTO `employees` VALUES (4, '小吴', '产品A组长', 2);
INSERT INTO `employees` VALUES (5, '小李', '产品B组长', 2);
INSERT INTO `employees` VALUES (6, '小欢', '产品经理', 3);
INSERT INTO `employees` VALUES (7, '小小', '产品经理', 3);
INSERT INTO `employees` VALUES (8, '小天', '产品部员工', 4);
INSERT INTO `employees` VALUES (9, '小里', '产品部员工', 4);
INSERT INTO `employees` VALUES (10, '小黑', '产品部员工', 5);
INSERT INTO `employees` VALUES (11, '小胡', '产品部员工', 5);
INSERT INTO `employees` VALUES (12, '小丽', '技术部员工', 6);
INSERT INTO `employees` VALUES (13, '小蓝', '技术部员工', 6);
INSERT INTO `employees` VALUES (14, '小黄', '技术部员工', 7);
INSERT INTO `employees` VALUES (15, '小真', '技术部员工', 7);
| eid | ename | position | parent_id |
|---|---|---|---|
| 1 | 老王 | 高管 | 0 |
| 2 | 老宋 | 产品部主管 | 1 |
| 3 | 老牛 | 技术部主管 | 1 |
| 4 | 小吴 | 产品A组长 | 2 |
| 5 | 小李 | 产品B组长 | 2 |
| 6 | 小欢 | 产品经理 | 3 |
| 7 | 小小 | 产品经理 | 3 |
| 8 | 小天 | 产品部员工 | 4 |
| 9 | 小里 | 产品部员工 | 4 |
| 10 | 小黑 | 产品部员工 | 5 |
| 11 | 小胡 | 产品部员工 | 5 |
| 12 | 小丽 | 技术部员工 | 6 |
| 13 | 小蓝 | 技术部员工 | 6 |
| 14 | 小黄 | 技术部员工 | 7 |
| 15 | 小真 | 技术部员工 | 7 |
SQL示例
添加节点
- 例如我要在小吴下添加一个员工
1
2INSERT INTO employees(eid, ename, position, parent_id)
VALUES(16, '小魏', '产品部员工', 4);
查询小天的直接上司
- 方式一
1
2
3
4SELECT e1.eid, e1.ename
FROM employees e1, employees e2
WHERE e1.eid = e2.parent_id
AND e2.ename = '小天' - 方式二
1
2
3SELECT eid, ename
FROM employees
WHERE eid = (SELECT parent_id FROM employees WHERE ename = '小天') - 虽然上面两种方式都可以查询，但是推荐使用方式一来进行查询。因为方式二使用了子查询，每次运行外部查询时，都需要重新计算子查询，如果子查询中返回了大量的数据，会导致查询效率低下，绝大多数情况下，使用方式一的查询效率会更高。
查询老宋的直属员工
- 这次我就不写子查询的方式了
1
2
3
4SELECT e2.eid, e2.ename
FROM employees e1, employees e2
WHERE e2.parent_id = e1.eid
AND e1.ename = '老宋'
查询小天的所有上司
- 在MySQL8.0以后的版本，使用递归CTE可以轻松实现
1
2
3
4
5
6
7
8
9
10
11
12WITH RECURSIVE Leader AS (
SELECT eid, ename, position, parent_id
FROM employees
WHERE ename = '小天'
UNION ALL
SELECT e.eid, e.ename, e.position, e.parent_id
FROM employees e
INNER JOIN Leader l
ON e.eid = l.parent_id
)
SELECT eid, ename, position FROM Leader - 但是MySQL8.0之前没有CTE，只能写个函数，用循环进行循环查询，先查直接上司，再查直接上司的直接上司，实现起来很麻烦，并且返回的结果也不能是一张表
查询老王的所有员工
- 这里还是使用递归CTE查询
1
2
3
4
5
6
7
8
9
10
11
12WITH RECURSIVE Emp AS (
SELECT eid, ename, position, parent_id
FROM employees
WHERE ename = '老王'
UNION ALL
SELECT e.eid, e.ename, e.position, e.parent_id
FROM employees e
INNER JOIN Emp emp
ON e.parent_id = emp.eid
)
SELECT eid, ename, position FROM Emp
方案二 Path Enumeration（存储路径）
- Path Enumeration 路径枚举法，存储根节点到每个子节点的路径
数据库存储结构
1 | -- ---------------------------- |
| eid | ename | position | parent_id |
|---|---|---|---|
| 1 | 老王 | 高管 | /1 |
| 2 | 老宋 | 产品部主管 | /1/2 |
| 3 | 老牛 | 技术部主管 | /1/3 |
| 4 | 小吴 | 产品A组长 | /1/2/4 |
| 5 | 小李 | 产品B组长 | /1/2/5 |
| 6 | 小欢 | 产品经理 | /1/3/6 |
| 7 | 小小 | 产品经理 | /1/3/7 |
| 8 | 小天 | 产品部员工 | /1/2/4/8 |
| 9 | 小里 | 产品部员工 | /1/2/4/9 |
| 10 | 小黑 | 产品部员工 | /1/2/5/10 |
| 11 | 小胡 | 产品部员工 | /1/2/5/11 |
| 12 | 小丽 | 技术部员工 | /1/3/6/12 |
| 13 | 小蓝 | 技术部员工 | /1/3/6/13 |
| 14 | 小黄 | 技术部员工 | /1/3/7/14 |
| 15 | 小真 | 技术部员工 | /1/3/7/15 |
| 16 | 小魏 | 产品部员工 | /1/2/4/16 |
SQL示例
添加节点
- 依旧是在小吴节点插入一个下属员工
1
2
3
4
5-- 1. 插入下属员工小魏，eid为16，查询父级节点path，拼接小魏的path
INSERT INTO `employees2` (`eid`, `ename`, `position`, `path`)
SELECT 16 AS eid, '小魏' AS ename, '产品部员工' AS position, CONCAT(path, '/16') AS path
FROM `employees2`
WHERE ename = '小吴';
查询小天的直接上司
- 在上一个解决方案中能轻易做到的事情，在这个方案中却有些麻烦了，因为我们需要对path字段做处理，去掉
/+自身id之后才是上司path的值，例如小天的path是/1/2/4/8，小天的eid是8，那么上司id就需要去掉/8，为/1/2/41
2
3
4SELECT e1.eid, e1.ename, e1.position
FROM employees2 e1, employees2 e2
WHERE e2.ename = '小天'
AND e1.path = REPLACE (e2.path, CONCAT( '/', e2.eid ), '')
查询老宋的直属员工
- 这里注意是查询直属员工，而不是所有员工，所以不能用LIKE来模糊匹配，而是需要使用正则来匹配单个层级
1
2
3
4SELECT e1.eid, e1.ename, e1.position
FROM employees2 e1, employees2 e2
WHERE e2.ename = '老宋'
AND e1.path REGEXP CONCAT(e2.path, '/[0-9]{1,}$') - 但是如果想使用LIKE做模糊匹配也不是不行，可以增加一个level字段，用于表示层级。
- 例如老王的level是1，老宋的level是2，老宋的直属员工的level就是3，以此类推，在构建查询语句的时候额外判定一下level就好了
1
2
3
4
5SELECT e1.eid, e1.ename, e1.position
FROM employees2 e1, employees2 e2
WHERE e2.ename = '老宋'
AND e1.path LIKE CONCAT(e2.path, '/%')
AND e1.level = 3
- 例如老王的level是1，老宋的level是2，老宋的直属员工的level就是3，以此类推，在构建查询语句的时候额外判定一下level就好了
查询小天的所有上司
- 查询所有上司或者所有员工的时候，就可以使用LIKE做模糊匹配
1
2
3
4SELECT e1.eid, e1.ename, e1.position
FROM employees2 e1, employees2 e2
WHERE e2.ename = '小天'
AND e2.path LIKE CONCAT(e1.path, '/%')
查询老王的所有员工
1 | SELECT e1.eid, e1.ename, e1.position |
方案三 Closure Table(存储关系表和深度)
- 保存每个节点与其各个子节点的关系，也就是记录以其为根节点的全部子节点信息。
数据库存储结构
1 | -- ---------------------------- |
- 主表
| eid | ename | position |
|---|---|---|
| 1 | 老王 | 高管 |
| 2 | 老宋 | 产品部主管 |
| 3 | 老牛 | 技术部主管 |
| 4 | 小吴 | 产品A组长 |
| 5 | 小李 | 产品B组长 |
| 6 | 小欢 | 产品经理 |
| 7 | 小小 | 产品经理 |
| 8 | 小天 | 产品部员工 |
| 9 | 小里 | 产品部员工 |
| 10 | 小黑 | 产品部员工 |
| 11 | 小胡 | 产品部员工 |
| 12 | 小丽 | 技术部员工 |
| 13 | 小蓝 | 技术部员工 |
| 14 | 小黄 | 技术部员工 |
| 15 | 小真 | 技术部员工 |
- 闭包表
| root_id | depth | is_leaf | node_id |
|---|---|---|---|
| 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 2 |
| 1 | 1 | 0 | 3 |
| 1 | 2 | 0 | 4 |
| 1 | 2 | 0 | 5 |
| 1 | 2 | 0 | 6 |
| 1 | 2 | 0 | 7 |
| 1 | 3 | 1 | 8 |
| 1 | 3 | 1 | 9 |
| 1 | 3 | 1 | 10 |
| 1 | 3 | 1 | 11 |
| 1 | 3 | 1 | 12 |
| 1 | 3 | 1 | 13 |
| 1 | 3 | 1 | 14 |
| 1 | 3 | 1 | 15 |
| 2 | 0 | 0 | 2 |
| 2 | 1 | 0 | 4 |
| 2 | 1 | 0 | 5 |
| 2 | 2 | 1 | 8 |
| 2 | 2 | 1 | 9 |
| 2 | 2 | 1 | 0 |
| 2 | 2 | 1 | 11 |
| 3 | 0 | 0 | 3 |
| 3 | 1 | 0 | 6 |
| 3 | 1 | 0 | 7 |
| 3 | 2 | 1 | 12 |
| 3 | 2 | 1 | 13 |
| 3 | 2 | 1 | 14 |
| 3 | 2 | 1 | 15 |
| 4 | 0 | 0 | 4 |
| 4 | 1 | 1 | 8 |
| 4 | 1 | 1 | 9 |
| 5 | 0 | 0 | 5 |
| 5 | 1 | 1 | 10 |
| 5 | 1 | 1 | 11 |
| 5 | 1 | 1 | 12 |
SQL示例
添加节点
- 依旧是在小吴下添加下属节点，在插入下属节点后，找出以小吴节点为后代的那些节点作为和下属节点之间有后代关系，插入到数据表。
1
2
3
4
5
6
7
8
9
10
11
12-- 1.插入自己M，eid为16
INSERT INTO employees3 ( eid, ename, position )
VALUES ( 16, '小魏', '产品部员工' );
-- 2.查出以小吴为后代的节点数据
SELECT * FROM emp_relations WHERE node_id=4;
-- 3.插入到数据表：深度+1作为和M节点的深度
INSERT INTO emp_relations ( root_id, depth, is_leaf, node_id )
VALUES
( 1, 3, 0, 16 ),
( 2, 2, 0, 16 ),
( 4, 1, 0, 16 ),
( 16, 0, 1, 16 );
查询小天的直接上司
- 在关系表中找到node_id为小天id，depth为1的根节点id即可
1
2
3
4
5
6
7
8
9
10
11SELECT
e2.eid, e2.ename, e2.position
FROM
employees3 e1,
employees3 e2,
emp_relations rel
WHERE
e1.ename = '小天'
AND rel.node_id = e1.eid
AND rel.depth = 1
AND e2.eid = rel.root_id
查询老宋的直属员工
- 只要查询root_id为老宋eid且深度为1的node_id即为其直接下属员工id
1
2
3
4
5
6
7
8
9
10
11SELECT
e1.eid, e1.ename, e1.position
FROM
employees3 e1,
employees3 e2,
emp_relations rel
WHERE
e2.ename = '老宋'
AND rel.root_id = e2.eid
AND rel.depth = 1
AND e1.eid = rel.node_id
查询小天的所有上司
- 只要在关系表中找到node_id为小天eid且depth大于0的root_id即可
1
2
3
4
5
6
7
8
9
10
11SELECT
e2.eid, e2.ename, e2.position
FROM
employees3 e1,
employees3 e2,
emp_relations rel
WHERE
e1.ename = '小天'
AND rel.node_id = e1.eid
AND rel.depth > 0
AND e2.eid = rel.root_id
查询老王的所有员工
1 | SELECT |
总结
- Adjacency List（邻接列表）:
- 优点：简单易于理解和实现，只需要一个父节点 ID 字段，容易添加、删除、移动节点。不需要维护冗余数据。
- 缺点：查询层级关系和递归操作需要进行多次查询，效率较低。在大型树状结构中，查询深度可能导致性能问题。
- 使用场景：适用于树状结构较小，层级深度不太深的情况，或者只需要简单的树结构操作。
- Path Enumeration（路径枚举）:
- 优点：相比邻接列表，路径枚举能够更快速地进行递归查询和层级操作，因为路径信息已经在节点上存储。
- 缺点：相比闭包表，会有一定的冗余，需要维护节点路径信息。对于层级关系较复杂的树结构，可能会占用更多的存储空间。
- 使用场景：适用于树状结构的层级操作较频繁，但树结构相对不太复杂的情况。
- Closure Table（闭包表）:
- 优点：能够高效地进行层级查询和递归操作，不需要多次查询数据库。对于复杂的树状结构，闭包表是一种强大的方法。
- 缺点：闭包表引入了数据冗余，存储了所有祖先-后代对，可能会占用更多的存储空间。
- 使用场景：适用于树状结构非常复杂的情况，或者需要高效查询祖先和后代节点关系的场景。
- 综合考虑，选择适当的存储方法取决于树状结构的大小、层级深度、复杂性，以及对于层级查询和操作的性能需求。对于小型和简单的树结构，邻接列表是一个简单有效的选择。对于较大且层级深度较深的树结构，Closure Table 提供了更高效的查询方式。而路径枚举则在某些情况下可以作为一种折中方案，同时满足查询效率和数据冗余的需求。
评论