我们在业务中经常要处理树形结构的数据，比如目录树、组织关系、血缘关系等。那么在关系型数据库中如何高效维护并查询树形结构呢? 本文将介绍并对比常见的三种树形结构的存储方案，供大家选择
0. 数据准备
为了方便下文的描述，本文引用《SQL Antipatterns》中评论的例子（本质也是一棵树的结构）进行对比，其树形结构如下：
1. 路径树 Path Enum
路径树，也被成为前缀树，即用从根节点到当前节点的路径来表示节点在树中的位置，其表结构为：
CREATE TABLE path_block_tree (
block_id SERIAL PRIMARY KEY,
path VARCHAR(100000), -- 树路径
parent_id BIGINT UNSIGNED,
FOREIGN KEY (parent_id) REFERENCES adjacency_block_tree(block_id)
);
表中内容为：
其中path字段就是树路径，从根节点到当节点路径树上每一个节点ID都用"/"连接在一起。
查询
如果要查询某个节点向上的根路径或者所有的子节点，可以直接根据path字段进行拼配，SQL简单高效。当然为了提高查询效率，path字段需要加索引。
-- 根路径 向上
SELECT *
FROM path_block_tree AS c
WHERE '1/4/6/7/' LIKE concat(c.path,'%');
-- 子树 向下
SELECT *
FROM path_block_tree AS c
WHERE c.path LIKE concat('1/4/','%');
树结构维护
- 插入：根据父节点
path信息，加入自身节点ID，插入子节点； - 删除：查询删除节点的子树，然后批量删除；
- 修改：查询修改节点子树，然后根据修改节点更新后的
path，批量替换子节点的path;
2. 闭包表 Closure Table
闭包表就是用闭包结构来表示树形结构的表，换句话就是表中包含全部节点是的前驱后继关系，在路径表的基础上，还需要添加如下表结构：
CREATE TABLE closureTree (
ancestor BIGINT UNSIGNED NOT NULL,
descendant BIGINT UNSIGNED NOT NULL,
depth BIGINT UNSIGNED NOT NULL,
PRIMARY KEY(ancestor, descendant),
FOREIGN KEY (ancestor) REFERENCES path_block_tree(block_id),
FOREIGN KEY (descendant) REFERENCES path_block_tree(block_id)
);
表中数据如图：
表中闭包的关联:
查询
对于闭包表，可以通过表之间的Join来实现树形结构的查询。
-- 查询节点4的子树
SELECT c.*
FROM path_block_tree AS c
JOIN closureTree AS t ON c.block_id = t.descendant
WHERE t.ancestor = 4;
-- 查询节点6的根路径
SELECT c.*
FROM path_block_tree AS c
JOIN closureTree AS t ON c.block_id = t.ancestor
WHERE t.descendant = 6;、
树结构维护
删除节点：先查询子树，然后批量删除
-
插入节点：比如将节点8 插入到节点5下面，需要批量插入如下数据
INSERT INTO closure_tree_path (ancestor, descendant, depth) SELECT ancestor, '{$node_id}', depth+1 FROM closure_tree_path WHERE descendant = '{$parent_id}' UNION ALL SELECT '{$node_id}', '{$node_id}', 0; 修改节点：操作比较困难，需要先批量删除所有闭包表中相关节点数据，然后重新依次插入；
3. 邻接表 Adjacency Tree
邻接表是最简单通用也是最好理解的树的存储方式，其表机构如下：
表结构
CREATE TABLE adjacency_block_tree (
block_id SERIAL PRIMARY KEY, # an alias for BIGINT UNSIGNED NOT NULL AUTO_INCREMENT UNIQUE
parent_id BIGINT UNSIGNED,
FOREIGN KEY (parent_id) REFERENCES adjacency_block_tree(block_id)
);
邻接表存储数据很简单，但是要查询就比较麻烦，需要在代码里递归查询每一层数据，这样比较耗时, 幸好Mysql 8已经支持了递归查询。
递归查询并不是什么新鲜事物，其实早在 SQL 99标准中已经规定了通过
WITH来定义通用的表的定义表达式，Microsoft SQL Server 2005, Oracle 11g, IBM DB2, PostgreSQL 8.4 等数据库都支持递归表达式，而MySQL 8.0时代也支持了该功能（虽然晚了好多年）。
查询子树
-- 子树查询（向下）
WITH RECURSIVE blockTree(block_id, parent_id, depth)
AS (
SELECT *, 0 AS depth FROM adjacency_block_tree
WHERE block_id = ?
UNION ALL
SELECT c.*, ct.depth +1 AS depth FROM blockTree ct
JOIN adjacency_block_tree c ON (ct.block_id = c.parent_id)
)
SELECT * FROM blockTree order by depth, block_id;
查询树路径
-- 路径查询（向上）
WITH RECURSIVE blockTree(block_id, parent_id, depth)
AS (
SELECT *, ? AS depth FROM adjacency_block_tree
WHERE block_id = ?
UNION ALL
SELECT c.*, ct.depth - 1 AS depth FROM blockTree ct
JOIN adjacency_block_tree c ON (ct.parent_id = c.block_id)
)
SELECT * FROM blockTree order by depth, block_id;
查询效率
那这样递归查DB的性能如何呢？会不会给mysql造成压力，笔者在2C8G的VM进行压测，分别执行根节点的子树查询，其性能表现如下：
| 节点个数 | 树的最大深度 | 执行时间 |
|---|---|---|
| 10 | 3-depth | 44.5ms |
| 100 | 10-depth | 48ms |
| 1000 | 15-depth | 51ms |
| 10000 | 20-depth | 137ms |
| 100000 | 30-depth | 309ms |
可见其性能在1W节点以内的树应用场景是可以满足的。
数据维护
邻接表的优势在于维护树结构简单：
插入节点：单SQL插入一行数据；
修改节点：单SQL修改一行数据；
删除节点：先查询出该节点子树的全部节点，然后在批量删除；
4. 总结
笔者用一张表来对比下三种方案的特性。
| 方案 | 储存 | 数据导出 | 查询父子关系 | 查询子树 | 查询根路径 | 插入 | 删除 | 修改 | 并发 | 备注 |
|---|---|---|---|---|---|---|---|---|---|---|
| 连接表&迭代查询 | 较少 | Easy | Easy | 迭代查询 Easy | 迭代查询Easy | Easy | 先查询子节点再批量删除 | Easy | 容易控制 | 必须依赖Mysql 8.0 |
| 路径树 | path可能很长 | Easy | Easy | Easy | Easy | Easy | Easy | Esay | 路径上锁 | Path过长，效率不高 |
| 闭包表 | 较多 | Hard | Easy | Easy | Easy | a little hard | Easy | Hard | Hard | 支持多父节点 |
没有最完美的方案，只有最适合。如果读者还在犹豫不决，笔者可以根据自己的经验来做个简单直接的推荐
- 如果树的结构变化频率不大，且深度不大，推荐路径树，反之ID为很长的UUID，则不推荐；
- 如果需要支持多个父节点的情况，支持无限深度，且不用考虑高并发的话，推荐闭包表；
- 如果DB支持递归查询，则建议直接考虑邻接表+递归查询的方式；
