目标

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

查找节点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 nodeSelectResult = nodeRelationDao.queryAncestor(FID);

List 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