如何在关系型数据库中存储树形结构
日常工作中，经常会使用到树形数据结构，比如说商品类目树，评论树，部门树，权限树等，如何在关系型数据库中存储树形结构呢？今天来介绍几种方案。
业务场景
文中使用公司部门结构树作为栗子，要在mysql中存储这个公司部门结构树
公司部门结构树
第一种方案：邻接表(Adjacency List)
邻接表想必大家都不陌生吧，用邻接表的关键是，在每个节点存储他的父节点的id。
CREATE TABLE `company_adjacency_list` (
`id` bigint(20) NOT NULL AUTO_INCREMENT COMMENT '主键',
`name` varchar(200) NULL DEFAULT NULL COMMENT '部门名称',
`parent_id` int(11) NULL DEFAULT NULL COMMENT '父id',
PRIMARY KEY (`id`) USING BTREE
)
在每一个部门信息中都存储了他的父节点id，parent_id字段
表结构
导入数据的过程就不说了，直接来看下数据吧：
公司部门结构数据
数据查询方式
这里使用常用的几种查询方式来看下这种方案的查询
- 查询一个部门的直属下级部门
select * from company_adjacency_list where parent_id = ?
可以通过parent_id做查询条件，可以快速查询到一个部门的直属下级部门
- 查询一个部门的直属上级部门
select * from company_adjacency_list where id= 要查询的部门的parent_id
通过部门信息中的parent_id去查相应的父节点信息就可以快速实现
- 查询一个部门的所有下级部门（查询子节点包括子节点的子节点）
这种表结构进行查询时，是一个循环的过程，先查询到子节点，然后在查询子节点的子节点，这样循环下去查，虽然网上很多文章都给了循环查询的sql和用存储过程查，但是其实这两种方式的效率都比较低，尤其用在线上服务时，这种查询效率低的方式，不建议使用sql直接查询，这种查询可以把数据全查询出来，然后在应用中组装成树形结构，放到缓存中，通过定时更新、提前预热等方式来提高查询效率
数据更新方式
这种数据存储结构下，更新数据是比较方便快捷的，添加数据时直接找准父节点的id，组织部门变更时，也直接变更父id就好了，删除时候，看自己业务是否需要删除子节点这几种情况，
第二种方案：路径表(Path Enumeration)
路径标的要点，就是每个节点存储根节点到该节点的路径，其实我觉得和别的几种方案可以共用
CREATE TABLE `company_path_enumeration` (
`id` bigint(20) NOT NULL AUTO_INCREMENT COMMENT '主键',
`name` varchar(200) NULL DEFAULT NULL COMMENT '部门名称',
`path` varchar(200) NULL DEFAULT NULL COMMENT '路径',
PRIMARY KEY (`id`) USING BTREE
)
在每一个部门信息中都存储了他完整的路径，path字段
company_path_enumeration表结构
导入数据的过程就不说了，直接来看下数据吧：
数据
数据查询方式
使用路径表，通过path这个字段查询起来是比较困难的，一般都需要使用like，CONCAT函数、REPLACE函数等做字符串的处理逻辑，查询起来比较复杂，这里不做展示了，线上服务不建议使用这种方式，查询效率低会影响到服务性能，一般建议和邻接表方式统一使用，同时添加parent_id和path字段，parent_id用来查询，path用来查看节点完整的路径
数据更新方式
这种数据存储结构下，更新数据是比较方便快捷的，添加数据时直接找准路径就好，组织部门变更时，也直接找准路径就好，删除时候，看自己业务是否需要删除子节点这几种情况，
第三种方案：闭包表？闭合表？(Closure Table)
Closure Table，百度直译过来叫闭合表，大多数人叫做闭包表，这种方案的要点是存储公司部门信息主表中，不存储节点关系的数据，使用另一张关系表来存储节点之间的关系，其中包含了任何两个有关系（上下级）节点的关联信息
公司部门信息主表
公司部门信息主表，只需要存储部门的本身信息
公司部门信息主表
公司部门结构关系表
主要包括三个字段
| 字段 | 字段直译 | 字段说明 |
|---|---|---|
| ancestor | 直译叫祖先节点 | 上级节点 |
| descendant | 直译叫子孙节点 | 下级节点 |
| distance | 直译叫距离 | 就上级节点与下级节点之间的距离 |
要点就是关系表的一条记录是一个上级节点、下级节点、与他们之间的路径距离。拿部门结构图来举例子
公司部门结构树
总公司-企划部的关系数据是：
ancestor: 主表中总公司的id 1
descendant: 主表中企划部的id 2
distance： 总公司到企划部的路径是： 总公司-企划部，所以他们的路径是 1
总公司-大区A的关系数据是：
ancestor: 主表中总公司的id 1
descendant: 主表中大区A的id 6
distance： 总公司到大区A的路径是： 总公司-大区- 大区A，所以他们的路径是 2
关系表中存储所有的节点路径信息，还用distance表示路径的距离，需要把树形结构中每两个节点之间的路径信息都维护进来。
CREATE TABLE `company_relation` (
`id` bigint(20) NOT NULL AUTO_INCREMENT,
`ancestor` bigint(20) NULL DEFAULT NULL,
`descendant` bigint(20) NULL DEFAULT NULL,
`distance` int(11) NULL DEFAULT NULL,
PRIMARY KEY (`id`) USING BTREE,
INDEX `index_ancestor`(`ancestor`) USING BTREE,
INDEX `descendant`(`descendant`) USING BTREE,
INDEX `distance`(`distance`) USING BTREE
) ENGINE = InnoDB
数据存储示例
数据存储的过程就拿导入总公司-门店A的过程做个示例。主表的数据存储就不说，说下关系中，存储部门结构的路径信息，总公司-门店A总共包含以下几条路径：
- 总公司-大区
ancestor: 主表中总公司的id 1
descendant: 主表中大区的id 4
distance： 总公司到大区的路径是： 总公司-大区，所以他们的路径是 1
INSERT INTO `company_relation`(`ancestor`, `descendant`, `distance`) VALUES (1, 4, 1);
- 总公司-大区A
ancestor: 主表中总公司的id 1
descendant: 主表中大区A的id 6
distance： 总公司到大区A的路径是： 总公司-大区-大区A，所以他们的路径是2
INSERT INTO `company_relation`(`ancestor`, `descendant`, `distance`) VALUES (1, 6, 2);
- 总公司-门店A
ancestor: 主表中总公司的id 1
descendant: 主表中门店A的id 8
distance： 总公司到门店A的路径是： 总公司-大区-大区A-门店A，所以他们的路径是3
INSERT INTO `company_relation`(`ancestor`, `descendant`, `distance`) VALUES (1, 8, 3);
- 大区-大区A
ancestor: 主表中大区的id 4
descendant: 主表中大区A的id 6
distance： 大区到大区A的路径是： 大区-大区A，所以他们的路径是1
INSERT INTO `company_relation`(`ancestor`, `descendant`, `distance`) VALUES (4, 6, 1);
- 大区-门店A
ancestor: 主表中大区的id 4
descendant: 主表中门店A的id 8
distance： 大区到门店A的路径是： 大区-大区A-门店A，所以他们的路径是2
INSERT INTO `company_relation`(`ancestor`, `descendant`, `distance`) VALUES (4, 8, 2);
- 大区A-门店A
ancestor: 主表中大区A的id 6
descendant: 主表中门店A的id 8
distance： 大区A到门店A的路径是： 大区A-门店A，所以他们的路径是1
INSERT INTO `company_relation`(`ancestor`, `descendant`, `distance`) VALUES (6, 8, 1);
看到了么，是存储了所有总公司-门店A之间的路径信息
数据查询方式
这里使用常用的几种查询方式来看下这种方案的查询
- 查询一个部门的直属下级部门，只需要查询ancestor为本节点id，距离为1的
select * from company_relation where ancestor = 本节点id and distance=1
- 查询一个部门的直属上级部门，只需要查询descendant为本节点id，距离为1的
select * from company_relation where distance= 本节点id and distance=1
- 查询一个部门的所有下级部门（查询子节点包括子节点的子节点），只需要使用ancestor为本节点id就可以查询到所有的子部门
select * from company_relation where ancestor = 本节点id
- 这种设计，也可以很方便的查询到指定层级的节点
数据更新方式
这种数据存储结构下，更新数据比较麻烦，因为他存储了两节点直接所有路径信息（包括中间节点的）
方案对比：
- 方案一：邻接表(Adjacency List)
优点：只用在主表中添加父id字段，空间占用低，在查询相邻节点关系，添加删除节点都比较简单
缺点：对于多级节点的查询会比较麻烦，需要使用一些手段去优化
适用场合：对于节点增删比较频繁，节点层级不是很复杂的场景 - 方案二：路径表(Path Enumeration)
我理解方案二，使用path字段存储节点到顶级节点之间的路径，查询其实比较麻烦，一般不会单独使用这种方案，一般和邻接表(Adjacency List) 方案配合使用，添加父id字段的同时在添加path字段，用来标识到顶级节点路径，用来快速支持节点整体路径的查询诉求 - 方案三：闭包表？闭合表？(Closure Table)
优点：在查询树形结构任意层级之间的关系时效率都很高
缺点：是一种空间换时间的方案，关系表存储数据量，增删改都比较麻烦
适用场合：查询诉求大，树形结构变动频率小的场景
如何在关系型数据库中存储树形结构就为大家讲到这，欢迎大家来交流，指出文中一些说错的地方，让我加深认识，愿大家没有bug，谢谢！
