问题

  • 实际开发中很多地方都需要存储树状结构，例如组织架构中需要用树状结构来表示公司员工之间的层级关系、电商网站中用树状结构来组织商品分类、论坛帖子或者评论中可以通过回复来构成树状结构。
  • 假设现在要存储一下公司的人员结构，大概层次如下
  • 怎么存储这个结构？并且要获取以下信息
    1. 查询小天的直接上司；
    2. 查询老宋管理下的直属员工；
    3. 查询小天的所有上司；
    4. 查询老王管理的所有员工。

方案一 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
2
INSERT INTO employees(eid, ename, position, parent_id) 
VALUES(16, '小魏', '产品部员工', 4);

查询小天的直接上司

  • 方式一
1
2
3
4
SELECT e1.eid, e1.ename
FROM employees e1, employees e2
WHERE e1.eid = e2.parent_id
AND e2.ename = '小天'
  • 方式二
1
2
3
SELECT eid, ename
FROM employees
WHERE eid = (SELECT parent_id FROM employees WHERE ename = '小天')
  • 虽然上面两种方式都可以查询，但是推荐使用方式一来进行查询。因为方式二使用了子查询，每次运行外部查询时，都需要重新计算子查询，如果子查询中返回了大量的数据，会导致查询效率低下，绝大多数情况下，使用方式一的查询效率会更高。

查询老宋的直属员工

  • 这次我就不写子查询的方式了
1
2
3
4
SELECT 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
12
WITH 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
12
WITH 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
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 employees2
-- ----------------------------
DROP TABLE IF EXISTS `employees2`;
CREATE TABLE `employees2`  (
  `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 '位置',
  `path` varchar(200) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL COMMENT '所在路径',
  PRIMARY KEY (`eid`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;

-- ----------------------------
-- Records of employees2
-- ----------------------------
INSERT INTO `employees2` VALUES (1, '老王', '高管', '/1');
INSERT INTO `employees2` VALUES (2, '老宋', '产品部主管', '/1/2');
INSERT INTO `employees2` VALUES (3, '老牛', '技术部主管', '/1/3');
INSERT INTO `employees2` VALUES (4, '小吴', '产品A组长', '/1/2/4');
INSERT INTO `employees2` VALUES (5, '小李', '产品B组长', '/1/2/5');
INSERT INTO `employees2` VALUES (6, '小欢', '产品经理', '/1/3/6');
INSERT INTO `employees2` VALUES (7, '小小', '产品经理', '/1/3/7');
INSERT INTO `employees2` VALUES (8, '小天', '产品部员工', '/1/2/4/8');
INSERT INTO `employees2` VALUES (9, '小里', '产品部员工', '/1/2/4/9');
INSERT INTO `employees2` VALUES (10, '小黑', '产品部员工', '/1/2/5/10');
INSERT INTO `employees2` VALUES (11, '小胡', '产品部员工', '/1/2/5/11');
INSERT INTO `employees2` VALUES (12, '小丽', '技术部员工', '/1/3/6/12');
INSERT INTO `employees2` VALUES (13, '小蓝', '技术部员工', '/1/3/6/13');
INSERT INTO `employees2` VALUES (14, '小黄', '技术部员工', '/1/3/7/14');
INSERT INTO `employees2` VALUES (15, '小真', '技术部员工', '/1/3/7/15');
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/4
1
2
3
4
SELECT 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
4
SELECT 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
5
SELECT 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

查询小天的所有上司

  • 查询所有上司或者所有员工的时候，就可以使用LIKE做模糊匹配
1
2
3
4
SELECT e1.eid, e1.ename, e1.position
FROM employees2 e1, employees2 e2
WHERE e2.ename = '小天' 
AND e2.path LIKE CONCAT(e1.path, '/%')

查询老王的所有员工

1
2
3
4
SELECT e1.eid, e1.ename, e1.position
FROM employees2 e1, employees2 e2
WHERE e2.ename = '老王' 
AND e1.path LIKE CONCAT(e2.path, '/%')

方案三 Closure Table(存储关系表和深度)

  • 保存每个节点与其各个子节点的关系，也就是记录以其为根节点的全部子节点信息。

数据库存储结构

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
-- ----------------------------
-- Table structure for employees3
-- ----------------------------
DROP TABLE IF EXISTS `employees3`;
CREATE TABLE `employees3`  (
  `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 '位置',
  PRIMARY KEY (`eid`) USING BTREE
) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;

-- ----------------------------
-- Records of employees3
-- ----------------------------
INSERT INTO `employees3` VALUES (1, '老王', '高管');
INSERT INTO `employees3` VALUES (2, '老宋', '产品部主管');
INSERT INTO `employees3` VALUES (3, '老牛', '技术部主管');
INSERT INTO `employees3` VALUES (4, '小吴', '产品A组长');
INSERT INTO `employees3` VALUES (5, '小李', '产品B组长');
INSERT INTO `employees3` VALUES (6, '小欢', '产品经理');
INSERT INTO `employees3` VALUES (7, '小小', '产品经理');
INSERT INTO `employees3` VALUES (8, '小天', '产品部员工');
INSERT INTO `employees3` VALUES (9, '小里', '产品部员工');
INSERT INTO `employees3` VALUES (10, '小黑', '产品部员工');
INSERT INTO `employees3` VALUES (11, '小胡', '产品部员工');
INSERT INTO `employees3` VALUES (12, '小丽', '技术部员工');
INSERT INTO `employees3` VALUES (13, '小蓝', '技术部员工');
INSERT INTO `employees3` VALUES (14, '小黄', '技术部员工');
INSERT INTO `employees3` VALUES (15, '小真', '技术部员工');

-- ----------------------------
-- Table structure for emp_relations
-- ----------------------------
DROP TABLE IF EXISTS `emp_relations`;
CREATE TABLE `emp_relations`  (
  `root_id` int(11) NULL DEFAULT NULL COMMENT '根节点的eid',
  `depth` int(11) NULL DEFAULT NULL COMMENT '根节点到该节点的深度',
  `is_leaf` tinyint(1) NULL DEFAULT NULL COMMENT '该节点是否为叶子节点',
  `node_id` int(11) NULL DEFAULT NULL COMMENT '该节点的eid'
) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;

-- ----------------------------
-- Records of emp_relations
-- ----------------------------
INSERT INTO `emp_relations` VALUES (1, 0, 0, 1);
INSERT INTO `emp_relations` VALUES (1, 1, 0, 2);
INSERT INTO `emp_relations` VALUES (1, 1, 0, 3);
INSERT INTO `emp_relations` VALUES (1, 2, 0, 4);
INSERT INTO `emp_relations` VALUES (1, 2, 0, 5);
INSERT INTO `emp_relations` VALUES (1, 2, 0, 6);
INSERT INTO `emp_relations` VALUES (1, 2, 0, 7);
INSERT INTO `emp_relations` VALUES (1, 3, 1, 8);
INSERT INTO `emp_relations` VALUES (1, 3, 1, 9);
INSERT INTO `emp_relations` VALUES (1, 3, 1, 10);
INSERT INTO `emp_relations` VALUES (1, 3, 1, 11);
INSERT INTO `emp_relations` VALUES (1, 3, 1, 12);
INSERT INTO `emp_relations` VALUES (1, 3, 1, 13);
INSERT INTO `emp_relations` VALUES (1, 3, 1, 14);
INSERT INTO `emp_relations` VALUES (1, 3, 1, 15);
INSERT INTO `emp_relations` VALUES (2, 0, 0, 2);
INSERT INTO `emp_relations` VALUES (2, 1, 0, 4);
INSERT INTO `emp_relations` VALUES (2, 1, 0, 5);
INSERT INTO `emp_relations` VALUES (2, 2, 1, 8);
INSERT INTO `emp_relations` VALUES (2, 2, 1, 9);
INSERT INTO `emp_relations` VALUES (2, 2, 1, 0);
INSERT INTO `emp_relations` VALUES (2, 2, 1, 11);
INSERT INTO `emp_relations` VALUES (3, 0, 0, 3);
INSERT INTO `emp_relations` VALUES (3, 1, 0, 6);
INSERT INTO `emp_relations` VALUES (3, 1, 0, 7);
INSERT INTO `emp_relations` VALUES (3, 2, 1, 12);
INSERT INTO `emp_relations` VALUES (3, 2, 1, 13);
INSERT INTO `emp_relations` VALUES (3, 2, 1, 14);
INSERT INTO `emp_relations` VALUES (3, 2, 1, 15);
INSERT INTO `emp_relations` VALUES (4, 0, 0, 4);
INSERT INTO `emp_relations` VALUES (4, 1, 1, 8);
INSERT INTO `emp_relations` VALUES (4, 1, 1, 9);
INSERT INTO `emp_relations` VALUES (5, 0, 0, 5);
INSERT INTO `emp_relations` VALUES (5, 1, 1, 10);
INSERT INTO `emp_relations` VALUES (5, 1, 1, 11);
INSERT INTO `emp_relations` VALUES (5, 1, 1, 12);
  • 主表
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
11
SELECT
	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
11
SELECT
	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
11
SELECT
	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
2
3
4
5
6
7
8
9
10
11
SELECT
	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 > 0 
	AND e1.eid = rel.node_id

总结

  1. Adjacency List（邻接列表）:
  • 优点：简单易于理解和实现，只需要一个父节点 ID 字段，容易添加、删除、移动节点。不需要维护冗余数据。
  • 缺点：查询层级关系和递归操作需要进行多次查询，效率较低。在大型树状结构中，查询深度可能导致性能问题。
  • 使用场景：适用于树状结构较小，层级深度不太深的情况，或者只需要简单的树结构操作。
  1. Path Enumeration（路径枚举）:
    • 优点：相比邻接列表，路径枚举能够更快速地进行递归查询和层级操作，因为路径信息已经在节点上存储。
    • 缺点：相比闭包表，会有一定的冗余，需要维护节点路径信息。对于层级关系较复杂的树结构，可能会占用更多的存储空间。
    • 使用场景：适用于树状结构的层级操作较频繁，但树结构相对不太复杂的情况。
  2. Closure Table（闭包表）:
    • 优点：能够高效地进行层级查询和递归操作，不需要多次查询数据库。对于复杂的树状结构，闭包表是一种强大的方法。
    • 缺点：闭包表引入了数据冗余，存储了所有祖先-后代对，可能会占用更多的存储空间。
    • 使用场景：适用于树状结构非常复杂的情况，或者需要高效查询祖先和后代节点关系的场景。
  • 综合考虑，选择适当的存储方法取决于树状结构的大小、层级深度、复杂性，以及对于层级查询和操作的性能需求。对于小型和简单的树结构，邻接列表是一个简单有效的选择。对于较大且层级深度较深的树结构，Closure Table 提供了更高效的查询方式。而路径枚举则在某些情况下可以作为一种折中方案，同时满足查询效率和数据冗余的需求。