背景

因为存证项目版本重构，新增部门等业务，有一个相对较麻烦的设计是关于部门关系的存储。花了一两天找了网上比较主流的一些方案设计。如下为常见的树型结构的数据：

image.png

一、邻接表

最开始我和陈健定的方案就是最容易想到的，model 层增加一个 parent_id 字段专门记录父部门子部门关系，表结构通常设计为 {Node_id,Parent_id}，如下图：

image.png

这种方案的优点很明显：结构简单易懂，由于互相之间的关系只由一个 parent_id 维护，所以增删改都是非常容易，只需要改动和他直接相关的记录就可以。

缺点当然也是非常的突出：由于直接地记录了节点之间的继承关系，因此对 Tree 的任何 CRUD 操作都将是低效的，这主要归根于频繁的 “递归” 操作，递归过程不断地访问数据库，每次数据库 IO 都会有时间开销。举个例子，如果想要返回所有水果，也就是水果的所有子孙节点，看似很简单的操作，就需要用到一堆递归。

因为和产品还有和陈健讨论了下，确实觉得在业务上来说查 >> 写，所以这个最开始敲定的方案就推翻了，还是要想办法优化查的性能。当然，这种方案并非没有用武之地，在树的层级比较少的时候就非常实用。这种方法的优点是存储的信息少，查直接上级和子节点的时候很方便，缺点是多级查询的时候很费劲。所以当只需要用到直接上下级关系的时候，用这种方法还是不错的，可以节省很多空间。

二、物化路径

核心思想就是借鉴了 unix 文件目录的思想，空间换时间。在创建节点时，将节点的完整路径进行记录。如下图：

image.png

这个算最后敲定的方案，理由就是比较直观，查询的还算比较好。相关 sql 例子如下：

  1. // 查询某一节点下的所有子节点:（以 Fruit 为例）
  2. SET @path = (SELECT path FROM pathTree WHERE node_name = 'Fruit');
  3. SELECT * FROM pathTree WHERE path like CONCAT(@path,'/%');
  5. // 如何查询直属子节点？需要采用 MySQL 的正则表达式查询：
  6. SET @path = (SELECT path FROM pathTree WHERE node_name = 'Fruit');
  7. SELECT * FROM pathTree WHERE path REGEXP CONCAT(@path,'/','[0-9]+$'); 
  9. // 查询任意节点的所有上级：（以Yellow为例）：
  10. SET @path = (SELECT path FROM pathTree WHERE node_name = 'Yellow');
  11. SELECT * FROM pathTree WHERE @path LIKE CONCAT(path, '%') AND path <> @path;
  13. // 插入新增数据：
  14. INSERT INTO pathtree (path,node_name) VALUES (CONCAT(@parent_path,'/'),'White') ;
  15. UPDATE pathtree SET path = CONCAT(@path, '%', @id) WHERE id=@id;

值得注意的是，查询直属子节点的正则应该是 [0-9]+$，而不是 '[0-9]$，因为存在 id 为 10 以上的部门。

还有一个比较有意思的 bug 就是插入的时候为什么不用 orm 或者原生的 sql 自带的取数据库的 LAST_INSERT_ID() 方法拼接 PATH，如下：

  1. // 插入新增数据：
  2. SET @parent_path = ( SELECT path FROM pathTree WHERE node_name = 'Fruit');
  3. INSERT INTO pathtree (path,node_name) VALUES (CONCAT(@parent_path,'/',LAST_INSERT_ID()+1),'White')

原因就是高并发下，很多连接可能会取到同一个 last_id ，从而导致 PATH 插入有误。后面想了下还是设计成插入，再拿到插入的 ID 去更新 PATH。

正则错误和这个插入 bug 都是陈健 review 代码的时候指出来的，说明我写代码一定要有人帮我兜底（不是

缺点就是怕层级无限大，把 PATH 的字段长度撑爆，但是这种可能性微乎其微，基本不用考虑。另外一个缺点就是虽然查的性能是解决了，但是更新是比较烦的，因为你得把更新过后的 PATH 给计算一遍，然后插入，所以给的 sql 例子也没有更新的示例。因为重要的 PATH 是在业务层代码解决了。

相关的数组和树形结构相互转换的代码之前写前端的时候就经常写，给一个时间复杂度 O(n) 的 Javascript 实现。

image.png

Go 业务代码实现

carbon.png

虽然 Protobuf 也支持嵌套结构，但是网关层又需要做一遍转换。所以最后在网关层写了这段代码，Go 写这种嵌套结构的业务确实不如 Javascript/Python 无脑。相关测试代码在 getdepartmentstreelogic_test.go。

三、左右值编码

最后一种方案就很巧妙了，但是陈健还是觉得路径的方案好一点，这个左右值编码的方案还是骚了一点（非贬义。

先上图：

image.png

image.png

很一目了然，移动的顺序就是对这棵树进行前序遍历的顺序。我们可以推断出所有左值大于 2，并且右值小于 11 的节点都是 Fruit 的后续节点，整棵树的结构通过左值和右值存储了下来。按照深度优先，由左到右的原则遍历整个树，从 1 开始给每个节点标注上 left 值和 right 值，并将这两个值存入对应的 name 之中。

本方案的优点是查询非常的方便，缺点就是每次插入删除数据涉及到的更新内容太多，如果树非常大，插入一条数据可能花很长的时间。所以不推荐，了解下就行，也不打算深入研究，想研究的可以查其他资料。

四、闭包表

闭包表的思路和物化路径差不多，都是空间换时间，Closure Table，一种更为彻底的全路径结构，分别记录路径上相关结点的全展开形式。能明晰任意两结点关系而无须多余查询，级联删除和结点移动也很方便。但是它的存储开销会大一些，除了表示结点的 Meta 信息，还需要一张专用的关系表。

和陈健讨论了下，添加额外一张表还是没必要，造成了额外的心智负担，所以也就 pass 了。与之对应的存储和更新开销很大，查和写都多了个连表的操作。

image.pngimage.png