三种树形结构存储方案的对比

待我称王封你为后i 2024-03-24 08:26 11阅读 0赞

> 我们在业务中经常要处理树形结构的数据，比如目录树、组织关系、血缘关系等。那么在关系型数据库中如何高效维护并查询树形结构呢?  
> 下面将介绍并对比常见的三种树形结构的存储方案，供大家选择

## 假设我们需要存储这样的组织架构 ##

![在这里插入图片描述][292fd4e2dc114133812478bdb01e1df5.png]

## 路径树存储 Path Block ##

也称前缀树，即用从根节点到当前节点的路径来表示节点在树中的位置，其表结构示例为：

CREATE TABLE path_block_tree (
      id   SERIAL PRIMARY KEY,
      path         VARCHAR(100000),  -- 树路径
      parent_id    BIGINT UNSIGNED,
      FOREIGN KEY (parent_id) REFERENCES adjacency_block_tree(block_id)
    );

![在这里插入图片描述][9e63f28e15494eefa9eff4509e66a86f.png]  
其中 path 字段就是树路径，从根节点到当节点路径树上每一个节点 ID 都用"/"连接在一起。

### 查询 ###

如果要查询某个节点向上的根路径或者所有的子节点，可以直接根据 **path** 字段进行拼配，SQL简单高效。当然为了提高查询效率，**path** 字段需要加索引。

-- 根路径 向上
    SELECT *
    FROM path_block_tree AS c
    WHERE '2/23/231/' LIKE concat(c.path,'%');
    
    -- 子树 向下
    SELECT *
    FROM path_block_tree AS c
    WHERE c.path LIKE concat('2/23/','%');

### 树结构变动 ###

1.  插入：根据父节点 path 信息，加入自身节点 ID，插入子节点；
2.  删除：查询删除节点的子树，然后批量删除；
3.  修改：查询修改节点子树，然后根据修改节点更新后的 path，批量替换子节点的 path;

## 闭包表 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)
    );

表中闭包的关联示例:

![在这里插入图片描述][e7ace3971e434b90b0f087cdef07963d.png]

### 查询 ###

对于闭包表，可以通过表之间的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;

### 树结构变动 ###

1.  删除节点：先查询子树，然后批量删除
2.  插入节点：比如将节点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;

1.  修改节点：操作比较困难，需要先批量删除所有闭包表中相关节点数据，然后重新依次插入；

## 邻接表 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、PostgreSQL 8.4+ 已经支持了递归查询。

### 查询子树 ###

-- 子树查询（向下）
    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;

### 查询效率 ###

可见其性能在 1W 节点以内的树应用场景是可以满足的。

### 树结构变动 ###

1.  插入节点：单SQL插入一行数据；
2.  修改节点：单SQL修改一行数据；
3.  删除节点：先查询出该节点子树的全部节点，然后在批量删除；

## 总结 ##

<table> 
 <thead> 
  <tr> 
   <th>方案</th> 
   <th>储存</th> 
   <th>数据导出</th> 
   <th>查询父子关系</th> 
   <th>查询子树</th> 
   <th>查询根路径</th> 
   <th>插入</th> 
   <th>删除</th> 
   <th>修改</th> 
   <th>并发</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>连接表&amp;迭代查询</td> 
   <td>较少 Easy</td> 
   <td>Easy</td> 
   <td>迭代查询</td> 
   <td>Easy</td> 
   <td>迭代查询</td> 
   <td>Easy</td> 
   <td>Easy</td> 
   <td>先查询子节点再批量删除</td> 
   <td>Easy 容易控制</td> 
   <td>依赖高版本数据库</td> 
  </tr> 
  <tr> 
   <td>路径树</td> 
   <td>path 可能很长</td> 
   <td>Easy</td> 
   <td>Easy</td> 
   <td>Easy</td> 
   <td>Easy</td> 
   <td>Easy</td> 
   <td>Easy</td> 
   <td>Esay</td> 
   <td>路径上锁</td> 
   <td>路径不能过长，深度不能过深</td> 
  </tr> 
  <tr> 
   <td>闭包表</td> 
   <td>较多</td> 
   <td>Hard</td> 
   <td>Easy</td> 
   <td>Easy</td> 
   <td>Easy</td> 
   <td>Hard</td> 
   <td>Easy</td> 
   <td>Hard</td> 
   <td>Hard</td> 
   <td>支持多父节点</td> 
  </tr> 
 </tbody> 
</table>

1.  如果树的结构变化频率不大，且深度不大，推荐路径树（除非 ID 很长）；
2.  如果需要支持多个父节点的情况，支持无限深度，且不用考虑高并发的话，推荐闭包表；
3.  如果 DB 支持递归查询，则建议直接考虑邻接表 + 递归查询的方式；

[292fd4e2dc114133812478bdb01e1df5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/dbc0582a0b9242d4ab48354b1e4eb522.png
[9e63f28e15494eefa9eff4509e66a86f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/bebd77d97cde469b9327b8808353a528.png
[e7ace3971e434b90b0f087cdef07963d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/f59a66abb3a046dab9c8557f61049df0.png