我们时常会遇到这样的场景，如：组织结构图、回复评论的评论链、用于组织资源的树形资源组。
如图：
而作为一名程序员如果你特别纠结于类似这样的问题 “我们的需求方想要支持多少层”， “我觉得管理或者维护树形结构的代码简直烦透了”，那么你应该试一试我下面提到的第二种树形结构的解决方案。
到目前为止我在实战中曾使用过三种方式来实现这种hierarchical-data:
Adjacency list (邻接表)
Closure table (闭包表)
Path enumeration (路径枚举)
因为不想篇幅太长，本文仅详细介绍Closure table，并与Adjacency list做少许对比，文章附录中会有资料链接，里面有四种hierarchical-data详解(上面三种 + Nested Set )。
我这里以一个网易评论树来做讲解【已编号（1）-（9）】：
两种设计共有的数据：
comment table data：
这种设计非常直观，在表comment上添加一个parent_id字段, 每一条记录都知道自己的父记录是谁. comment之间数据结构关系如下图所示：
comment table data:
comment_path table data:
这种设计, comment table本身并不保存 评论与评论之间的关系， 而将该关系用另外一张表(comment_path)保存起来, 理论上讲需要O(n²)的空间来存储关系，但现实中并不会需要这么多。
comment之间数据结构关系如下图所示：
每根红线都是comment_path中的一条数据， 线条上的数字为depth。
查询直接回复4号comment的comment(父查子)
Adjacency :
select * from comment c1 where c1.parent_id=4;
Closure :
select c.* from comment c join comment_path cp on (c.id = cp.descendant) where cp.ancestor = 4 and depth = 1;
查询所有回复4号的子comment(父查所有子)
Adjacency :
思路为递归查询(使用SQL99的CTE 或 oracle的connect by语法)，不支持递归查询的数据库(如mysql) 将无法使用一条sql语句满足不固定层级数量的需求.
Closure :
select c.* from comment c join comment_path cp on (c.id = cp.descendant) where cp.ancestor = 4;
--如果你需要保留层级关系, 则将cp中的值也返回即可
查询所有7号的 父comment(子查所有父)
Adjacency :
方案与需求2类似
Closure :
select c.* from comment c JOIN comment_path cp on (c.id = cp.ancestor) where cp.descendant = 7;
添加一条子回复到 6号comment上(新增)
Adjacency :
insert into comment (value, parent_id, topic_id, user_id) values('(10)我以gin食阼啦', 6, 1, 2);
Closure :
step a: insert into comment(value, topic_id, user_id) values('(10)我以gin食阼啦', 1, 2);
-- 拿到该句返回的id, 假设为10
step b: insert into comment_path (ancestor, descendant, depth) select cp.ancestor, 10, cp.depth+1 from comment_path as cp where cp.descendant=6 union all select 10, 10, 0;
-- 只要拥有子comment_id为6作为子节点的节点，全都新增一个id为10，deepth+1的子节点 并且插入一个10, 10, 0的节点.
从评论链中删除4号comment及其子comment(删除子或者子树)
Adjacency :
由于parent_id是可以为空的foreign key约束 ==> 递归将所有4号的子节点从栈底开始 删除到栈顶。
Closure :
delete a from comment_path a join comment_path b on (a.descendant = b.descendant) where b.ancestor=4;
-- 这句话等价于 "delete from comment_path where descendant in (select descendant from comment_path where ancestor = 4);”, 但mysql会报from句子中的表不能用于update的错误.
将6号comment的父comment更改为2号(移动子或者子树)
Adjacency :
update comment set parent_id = 2 where id = 6;
Closure :
step a:
delete a from comment_path as a join comment_path as d on a.descendant = d.descendant left join comment_path as x on x.ancestor = d.ancestor and x.descendant = a.ancestor where d.ancestor = 6 and x.ancestor is null;
--这样删除的原因和需求5一致.
step b:
insert into comment_path (ancestor, descendant, depth) select supertree.ancestor, subtree.descendant, supertree.depth+subtree.depth+1 from comment_path as supertree join comment_path as subtree where subtree.ancestor = 6 and supertree.descendant = 2;
以上6种需求覆盖了最为常用的几种情况，更多的例子请各位看官脑补..
Every thing has tradeoffs, Designers should keep data structure & algorithm in mind.
本文作者：钱晟龙 Arc_Qian（点融黑帮），现任点融网架构组产品研发工程师，主要任务是思考并尝试解决各类点融网迈出第一公里之后遇到的现实问题。
随着点融网新一轮融资，点融网即将开始大规模的扩张，需要各种优秀人才的加入，如果你觉得自己够优秀，欢迎加入我们！获取更多职位信息，请关注点融黑帮。
