目标

---

在一颗树中快速查找到子孙节点、祖先节点

查找节点A的所有子孙节点

---

图1
树的表结构

CREATE TABLE `node` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT '' COMMENT '节点名称',
  `parent_id` bigint(20) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4

node表的数据

id	name	parent_id
1	A	0
2	B	1
3	C	1
4	D	2
5	E	2
6	F	3

查找节点A的子孙节点，可以用以下3个SQL完成

select … where parent_id = A ==> B, C
select … where parent_id in (B, C) ==> D,E,F
select … where parent_id in (D,E,F) ==> empty

可以看到随着节点深度的增加，获取子孙节点SQL条数会越来越多。
如何进行优化，来避免和SQL的多次交互？闭包表一次就能获取节点的子孙部门或者祖先部门

什么是闭包表

一张记录树中所有节点的关系表。记录节点之间距离的关系表，注意:这次讨论的闭包关系表不包含自身的关系，例如 (ancestor,descendant,distance) => (A,A,0)
表结构如下:

CREATE TABLE `node_relation` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增ID',
  `ancestor` int(10) unsigned NOT NULL DEFAULT '0' COMMENT '祖先节点',
  `descendant` int(10) unsigned NOT NULL DEFAULT '0' COMMENT '后代节点',
  `distance` tinyint(3) unsigned NOT NULL DEFAULT '0' COMMENT '相隔层级，>=1',
  PRIMARY KEY (`id`),
  UNIQUE KEY `uniq_anc_desc` (`ancestor`,`descendant`),
  KEY `idx_desc` (`descendant`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8mb4 COMMENT='节点关系表'

图2

node_relation表A作为祖先节点的的关系数据(id 用实际节点描述表示)

ancestor	descendant	distance
A	B	1
A	C	1
A	D	2
A	E	2
A	F	2

再来看查A部门的所有子部门怎么查,只需要一个SQL就搞定了

select descendant from ancestor = A;

闭包表副作用

由于闭包表新增了节点和节点之间的关系，所以在变更树结构的时候，会重构这个关系，想想就觉得复杂。所以数据量少，请谨用闭包表。

如果实在是需要用到闭包表的，那么请继续往下看，本文会为你理清这些关系。

闭包表常见操作

闭包表-查询

1).获取指定A节点的子孙节点

   select descendant from node_relation where  ancestor = A;

2).获取指定节点F的祖先节点

   select ancestor from node_relation where descendant = F;

闭包表-增、删、move

1).新增：在F节点下新增节点H(见图3)

图3

//新增节点H
insert into node (`name`,`parent_id`)  values ("H",F_id);
//记录F、H的闭包关系
insert into node_relation (ancestor,descendant,distance) values(F,H,1); 
;//获取F和祖先闭包关系
select ancestor,descendant,distance from node_relation where descendant = F

H和F的祖先闭包关系很明显可以发现
F的祖先 ，F ，distance = F的祖先，H，distance+1
java 伪代码:

Long HID=999L;
Long FID = 888L;
List<NodeRelationDO> nodeSelectResult = nodeRelationDao.queryAncestor(FID);
List<NodeRelationDO> nodeRelations = new ArrayList<>();
for (NodeRelationDO item : nodeSelectResult) {
    NodeRelationDO nodeRelationDO = new NodeRelationDO();
    nodeRelationDO.setAncestor(item.getAncestor);
    nodeRelationDO.setDescendant(HID);
    nodeRelationDO.setDistance(item.getDistance + 1);
    nodeRelations.add(nodeRelationDO);           
}
nodeRelationDao.batchUpsert(nodeRelations);

2).删除：删除C节点(递归删除)
删除比较简单，主要分以下2个步骤

• 删除节点
• 删除节点闭包表相关数据
  图4
  红色的是需要删除的关系边(见图4)，其实很容易就找出规律，需要删除和删除节点有关的所有关系边

//删除节点闭包表相关数据
delete from node_relation where ancestor in (需要删除集合) 
or  descendant in  (需要删除的集合);

3).变更父节点: 将B节点移到C节点上(见图5)

图5

• 从节点考虑只需要把B节点parent_id 直接更新成C就完成了
• 闭包关系表变化会复杂一些
  接下去介绍下，move过程闭包关系表的变化

1).待删除的边：

select * from node_relation where ancestor in (B的所有祖先) 
and descendant in (B树的所有节点,包含B);

删除后会得到2颗分裂的树,见图6 ,红色边就是等待删除的边

图6
2).重建关系
新增关系：(C及C的所有祖先节点) x （B树的所有节点），这两个节点集合的笛卡尔积就是新增的边(见图7)。
图7