业务中经常有需要用到树状结构的地方,比如部门树、文件夹等等。本文总结集中经典设计,针对不同场景按需使用。(参考 SQL Anti-patterns 一书)

邻接表(Adjacency List)和 递归查询(Recursive query)

每条记录存 parent_id ,这也是 树 最常见的设计方案。

  • 优点是结构非常简单直接,增删改很方便,修改 parentId 即可
  • 缺点是查询困难,尤其是要把整个树从根节点开始构建起来(需要不断递归)。随着层级增加,查询效率不断下降

image.png

查某个节点的子节点:

  1. SELECT * FROM dept_info WHERE dept_parent_id =1001

节点移动:

  1. UPDATE dept_info SET dept_parent_id=1001 WHERE dept_id=3001;

路径枚举(Path Enumerations)

在邻接表的基础上增加节点路径,里面存从根节点开始到自己的完整路径

  • 优点是查询方便。可以通过 like 语句快速查询子节点,同时通过长度即可知道节点所在层级
  • 缺点是节点移动变更困难。需要同时变更所有子节点的路径数据,同时路径字段的长度不好缺点

image.png

查询部门 1001 的下级部门:

  1. SELECT * FROM dept_info WHERE dept_parent_ids like '%1001%'

左右值编码(Nested Sets)

左右值编码的思路是基于树的前序遍历算法。这种设计方案会记录一个 左值(lft)和一个右值,分别代表树前序遍历过程的顺序。计算过程如图2

image.png
image.png

左右值设计方案特别适用于类似「文件夹」的场景。前两种设计方案,随着树层级增加,性能都会逐步下降,不适合无限层级的场景。而左右值方案查询效率不受层级影响(不用递归)
但弊端是随着层级增加,修改更新变得困难

闭包表(Closure Table)

闭包表的思路是空间换时间。用一张单独的表存储节点关系,数据表只存储业务数据。

第二种表的设计可以比较灵活,只要能描述节点关系即可。实例的表结构是记录了祖先节点和自己所在的层级。
查节点关系的时候查节点表即可,相比前面的方案,表会稍微小一点。代价是要多一张表

image.png image.png

总结对比

最后用一张图总结对比一下每一种设计方式的优劣:
image.png