很多业务场景会遇到树形结构的数据,如公司的人员职级树、行政区划树等。
使用类似MySQL的数据库进行存储,需要将树形结构(二维)存储到行格式(一维)的db中。
本文介绍了树型结构数据存储的三种方式:Adjacency Table , Nested Set , Bridge Table (Closure Table)。
以下方法均基于场景:
设想一个职员团队树,节点中为职工工号id和职工名称,节点1指向2表示职工1属于职工2的团队:
我们有如下的操作:
- 新增职工节点
- 删除职工节点
- 查询该职工节点下属的-1职工节点
- 查询该职工节点的所有下属职工节点
- 查询该职工节点的+1领导节点
- 查询该职工节点的所有领导节点
Adjacency Table
最简单的,我们构建一个邻接表,表中记录了当前职工id及其领导职工id(pid),数据组织结构如下:
id 职工id | name 职工姓名 | pid 职工+1领导的职工id |
---|---|---|
101 | A | null |
102 | B | null |
103 | C | 101 |
104 | D | 101 |
… | … | … |
则我们可以生成如下的sql建表语句:
CREATE TABLE `employee_adjacency_table` (
`id` bigint NOT NULL COMMENT '职工id',
`name` varchar(64) NOT NULL COMMENT '职工姓名',
`pid` bigint COMMENT '+1领导的职工id',
`deleted` tinyint DEFAULT 0 COMMENT '软删标记',
PRIMARY KEY (`id`),
KEY `idx_pid` (`pid`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci
新增职工节点
在节点108下插入叶子节点113:
INSERT INTO employee_adjacency_table (id,name,pid) VALUE (113,'M',108);
在105节点下插入非叶子节点113:
INSERT INTO employee_adjacency_table VALUE (113,'M',105);
-- 将105的-1子节点移植到113下
UPDATE employee_adjacency_table SET pid = 108 WHERE pid = 105;
删除职工节点
删除叶子节点111:
UPDATE employee_adjacency_table SET deleted = 1 where id = 111;
删除非叶子节点107,其叶子节点移植到107的+1领导节点下:
UPDATE employee_adjacency_table SET deleted = 1 where id = 107;
-- 查出107的领导节点,即105
SELECT pid FROM employee_adjacency_table WHERE id = 107 and deleted = 0 FOR UPDATE;
UPDATE employee_adjacency_table SET pid = 105 WHERE pid = 107;
查询该职工节点下属的-1职工节点
查询节点105下的-1子节点
SELECT * FROM employee_adjacency_table WHERE pid = 105 and deleted = 0
查询该职工节点的所有下属职工节点
查询节点105下的所有下属节点
需要每次查询一层数据,每次将查处的id作为pid查询条件继续查下一层,直到结果为空。
查询该职工节点的+1领导节点
查询节点109的+1领导节点
-- 查到109的+1领导节点,即105
SELECT pid FROM employee_adjacency_table WHERE id = 109 and deleted = 0;
SELECT * FROM employee_adjacency_table WHERE id = 105 and deleted = 0;
查询该职工节点的所有领导节点
查询节点112的所有领导节点
需要每次查询一层数据,每次将查处的pid作为id查询条件继续查上一层,直到pid为null。
优缺点及适用场景
优点:结构简单,节点变更简单
缺点:查询多层级节点效率低
一般树形数据会在服务启动时从数据库导入全量数据到缓存中。适合节点数量不大,变更少,变更实时性要求低的场景
Nested Set
相比与Adjacency Table 使用pid记录父级节点, Nested Set使用一对值(left & right)刻画树的父子关系。
以102为root的树为例,将其转化为Nested Set形式,每个节点转化为一个数值范围 [left, right],如下图所示:
层级关系由数据范围的包含关系表示。比如工号102的职工的范围是 [1,12], 其下属职工105的范围是 [2,9],注意到叶子节点的left和right差值都是1。
则我们可以生成如下的sql建表语句:
CREATE TABLE employee_nested_set (
`id` bigint NOT NULL COMMENT '职工id',
`name` varchar(64) NOT NULL COMMENT '职工姓名',
`left` int NOT NULL,
`right` int NOT NULL,
`deleted` tinyint DEFAULT 0 COMMENT '软删标记',
PRIMARY KEY (`id`),
KEY `idx_left` (`left`),
KEY `idx_right` (`right`)
);
新增职工节点
我们要在职工110下面新增一个职工113,由于113是叶子结点,所以其left和right差值为1,且值必须在110的数值范围内,这样
只能将110的范围扩大,随之而来的是其右边值的统一扩大。
则新增的sql语句为(不能并发更新):
-- 找到节点110的左右值,即[7,8]
SELECT left,right FROM employee_nested_set where id = 110 and deleted = 0 FOR UPDATE;
-- 更新右侧left和right值
UPDATE employee_nested_set SET left = left + 2 WHERE left > 8 and deleted = 0;
UPDATE employee_nested_set SET right = right + 2 WHERE right >= 8 and deleted = 0;
-- 插入值范围
INSERT INTO employee_nested_set (id,name,left,right) VALUE (113, "M", 8 , 9);
我们要在职工110下面新增一个职工113,由于113是叶子结点,所以其left和right差值为1,且值必须在110的数值范围内,这样
只能将110的范围扩大,随之而来的是其右边值的统一扩大。
如果要在105和109之间插入新节点114呢?
-- 找到109的左右值,即 [3,6]
SELECT left,right FROM employee_nested_set WHERE id = 109 AND deleted = 0;
UPDATE employee_nested_set SET left = left + 1 , right = right + 1 WHERE left >= 3 and deleted = 0;
UPDATE employee_nested_set SET left = left + 1 , right = right + 1 WHERE left >= 6+1+1 and deleted = 0;
INSERT INTO employee_nested_set (id,name,left,right) VALUE (114,'N',3,8);
删除职工节点
比如删除节点109,109的从属节点继承到109的领导节点下:
-- 找到109的左右值,即 [3,6]
SELECT left,right FROM employee_nested_set WHERE id = 109 AND deleted = 1;
UPDATE employee_nested_set SET left = left - 1,right = right - 1 WHERE left BETWEEN 3 AND 6;
UPDATE employee_nested_set SET left = left - 1,right = right - 1 WHERE left > 7;
查询该职工节点下属的-1职工节点
很麻烦,比如找到105的-1职工节点:
SELECT node.id, (COUNT(parent.id) - (sub_tree.depth + 1)) AS depth
FROM employee_nested_set AS node,
employee_nested_set AS parent,
employee_nested_set AS sub_parent,
(
SELECT node.id, (COUNT(parent.id) - 1) AS depth
FROM employee_nested_set AS node,
employee_nested_set AS parent
WHERE node.left BETWEEN parent.left AND parent.right
AND node.id = 105
GROUP BY node.name
ORDER BY node.left
)AS sub_tree
WHERE node.left BETWEEN parent.left AND parent.right
AND node.left BETWEEN sub_parent.left AND sub_parent.right
AND sub_parent.id = sub_tree.id
GROUP BY node.id
HAVING depth <= 1
ORDER BY node.left;
查询该职工节点的所有下属职工节点
很方便,比如找职工105下所有的职工id:
-- 找到105的left和right,即[2,9]
SELECT left,right FROM employee_nested_set WHERE id = 105 and deleted = 0;
-- 找到2和9之间的left的节点
SELECT id FROM employee_nested_set WHERE left BETWEEN 2 AND 9 and deleted = 0;
查询该职工节点的+1领导节点
找到职工105的+1领导节点,即102。
比较trick的写法:
SELECT parent.id
FROM employee_nested_set AS node, employee_nested_set AS parent
WHERE parent.left < node.left
AND parent.right > node.right
AND node.id =105
ORDER BY ( parent.right - parent.left ) ASC LIMIT 1;
查询该职工节点的所有领导节点
也很方便,比如找到职工110所有的领导节点:
-- 找到节点110的left和right,即[7,8]
SELECT left,right FROM employee_nested_set WEHERE id = 110 and deleted = 0;
-- 找到left<7 && right>8的节点即为其领导节点
SELECT id FROM employee_nested_set WHERE left < 7 and right > 8 and deleted = 0;
优缺点及适用场景
优点:适合查询所有下属节点的场景
缺点:数据从属关系不直观,变更操作复杂,时间复杂度高,且其他查询场景的sql语句复杂
适用于查询所有下属节点且节点变更频率低的场景,可以配合邻接表,邻接表作为变更入口,而Nested Set根据邻接表构造而成,查询所有下属节点的场景走NestSet
Bridge Table (Closure Table)
闭包表使用两张表记录数据,一张记录节点信息,一张记录ancestor节点到descendant节点之间的距离。
-- 节点信息表
CREATE TABLE `employee_node` (
`id` bigint NOT NULL,
`name` int NOT NULL,
`deleted` tinyint NOT NULL DEFAULT '0',
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
-- 节点与下属节点之间的距离表
CREATE TABLE `employee_node_distance` (
`id` bigint NOT NULL,
`ancestor_id` bigint NOT NULL,
`descendant_id` bigint NOT NULL,
`distance` int NOT NULL,
`deleted` tinyint NOT NULL DEFAULT '0',
PRIMARY KEY (`id`),
KEY `idx_anc_dist` (`ancestor_id`,`distance`),
KEY `idx_desc_dist` (`descendant_id`,`distance`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
新增职工节点
在节点110下插入叶子节点113:
INSERT INTO employee_node (id,name) VALUE (113,'M');
-- 查处descendant_id为110的所有ancestor_id和到110的距离
SELECT ancestor_id , distance FROM employee_node_distance
WHERE descendant_id = 110;
-- 根据上面查处的id和distance插入113的数据
INSERT INTO employee_node_distance (ancestor_id, descendant_id, distance)
VALUES (113,113,0),(ancestorIdOf110,113,distanceOf110+1);
在105节点和109节点间插入非叶子节点113:
INSERT INTO employee_node (id,name) VALUE (113,'M');
-- 查出105的所有领导节点
-- 插入113和领导节点的距离
-- 查处所有109的下属节点
-- 插入113和下属节点的距离
-- 根据109及其下属节点到他们领导节点的距离(+1)
删除职工节点
删除节点105:
查询该职工节点下属的-1职工节点
很方便,比如查询105的-1职工节点:
SELECT descendant_id FROM employee_node_distance
WHERE ancestor_id = 105 and distance = 1 and deleted = 0;
查询该职工节点的所有下属职工节点
很方便,比如查询105下所有下属节点:
SELECT descendant_id FROM employee_node_distance
WHERE ancestor_id = 105 and descendant_id != 105 and deleted = 0;
查询该职工节点的+1领导节点
很方便,比如查询109的+1领导节点,即105:
SELECT ancestor_id FROM employee_node_distance
WHERE descendant_id = 109 and distance = 1 and deleted = 0;
查询该职工节点的所有领导节点
很方便,比如查询112的所有领导节点
SELECT ancestor_id FROM employee_node_distance
WHERE descendant_id = 102 and ancestor_id != 102 and deleted = 0;
优缺点及适用场景
优点:满足各种场景查询,sql语句简单好理解
缺点:占用表空间大,空间复杂度O(N^2) N为节点个数,子节点变动需要更新所有领导节点数据
适用于节点数量少,但查询复杂的场景
参考
- What are the options for storing hierarchical data in a relational database?
- Managing Hierarchical Data in MySQL
- Convert an Adjacency List to Nested Sets