目標(biāo)

在一顆樹中快速查找到子孫節(jié)點(diǎn)、祖先節(jié)點(diǎn)

查找節(jié)點(diǎn)A的所有子孫節(jié)點(diǎn)

圖1

CREATE TABLE `node` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT '' COMMENT '節(jié)點(diǎn)名稱',
  `parent_id` bigint(20) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4

node表的數(shù)據(jù)

查找節(jié)點(diǎn)A的子孫節(jié)點(diǎn)，可以用以下3個(gè)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

可以看到隨著節(jié)點(diǎn)深度的增加，獲取子孫節(jié)點(diǎn)SQL條數(shù)會(huì)越來越多。
如何進(jìn)行優(yōu)化，來避免和SQL的多次交互？閉包表一次就能獲取節(jié)點(diǎn)的子孫部門或者祖先部門

什么是閉包表

一張記錄樹中所有節(jié)點(diǎn)的關(guān)系表。記錄節(jié)點(diǎn)之間距離的關(guān)系表，注意:這次討論的閉包關(guān)系表不包含自身的關(guān)系，例如 (ancestor,descendant,distance) => (A,A,0)
表結(jié)構(gòu)如下:

CREATE TABLE `node_relation` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT '自增ID',
  `ancestor` int(10) unsigned NOT NULL DEFAULT '0' COMMENT '祖先節(jié)點(diǎn)',
  `descendant` int(10) unsigned NOT NULL DEFAULT '0' COMMENT '后代節(jié)點(diǎn)',
  `distance` tinyint(3) unsigned NOT NULL DEFAULT '0' COMMENT '相隔層級(jí)，>=1',
  PRIMARY KEY (`id`),
  UNIQUE KEY `uniq_anc_desc` (`ancestor`,`descendant`),
  KEY `idx_desc` (`descendant`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8mb4 COMMENT='節(jié)點(diǎn)關(guān)系表'

圖2

node_relation表A作為祖先節(jié)點(diǎn)的的關(guān)系數(shù)據(jù)(id 用實(shí)際節(jié)點(diǎn)描述表示)

再來看查A部門的所有子部門怎么查,只需要一個(gè)SQL就搞定了

select descendant from ancestor = A;

閉包表副作用

由于閉包表新增了節(jié)點(diǎn)和節(jié)點(diǎn)之間的關(guān)系，所以在變更樹結(jié)構(gòu)的時(shí)候，會(huì)重構(gòu)這個(gè)關(guān)系，想想就覺得復(fù)雜。所以數(shù)據(jù)量少，請謹(jǐn)用閉包表。

如果實(shí)在是需要用到閉包表的，那么請繼續(xù)往下看，本文會(huì)為你理清這些關(guān)系。

閉包表常見操作

閉包表-查詢

1).獲取指定A節(jié)點(diǎn)的子孫節(jié)點(diǎn)

   select descendant from node_relation where  ancestor = A;

2).獲取指定節(jié)點(diǎn)F的祖先節(jié)點(diǎn)

   select ancestor from node_relation where descendant = F;

閉包表-增、刪、move

1).新增：在F節(jié)點(diǎn)下新增節(jié)點(diǎn)H(見圖3)

圖3

//新增節(jié)點(diǎn)H
insert into node (`name`,`parent_id`)  values ("H",F_id);
//記錄F、H的閉包關(guān)系
insert into node_relation (ancestor,descendant,distance) values(F,H,1); 
;//獲取F和祖先閉包關(guān)系
select ancestor,descendant,distance from node_relation where descendant = F

H和F的祖先閉包關(guān)系很明顯可以發(fā)現(xiàn)
F的祖先 ，F(xiàn) ，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節(jié)點(diǎn)(遞歸刪除)
刪除比較簡單，主要分以下2個(gè)步驟

• 刪除節(jié)點(diǎn)
• 刪除節(jié)點(diǎn)閉包表相關(guān)數(shù)據(jù)
  
  圖4
  
  紅色的是需要?jiǎng)h除的關(guān)系邊(見圖4)，其實(shí)很容易就找出規(guī)律，需要?jiǎng)h除和刪除節(jié)點(diǎn)有關(guān)的所有關(guān)系邊

//刪除節(jié)點(diǎn)閉包表相關(guān)數(shù)據(jù)
delete from node_relation where ancestor in (需要?jiǎng)h除集合) 
or  descendant in  (需要?jiǎng)h除的集合);

3).變更父節(jié)點(diǎn): 將B節(jié)點(diǎn)移到C節(jié)點(diǎn)上(見圖5)

圖5

• 從節(jié)點(diǎn)考慮只需要把B節(jié)點(diǎn)parent_id 直接更新成C就完成了
• 閉包關(guān)系表變化會(huì)復(fù)雜一些
  接下去介紹下，move過程閉包關(guān)系表的變化

1).待刪除的邊：

select * from node_relation where ancestor in (B的所有祖先) 
and descendant in (B樹的所有節(jié)點(diǎn),包含B);

刪除后會(huì)得到2顆分裂的樹,見圖6 ,紅色邊就是等待刪除的邊

圖6

圖7