1 概述

在3年前,我写了一篇解决树状结构数据设计的博客:
mysql树状数据的数据库设计

在这篇博客中,树状结构利用"祖先路径"的设计,实现在一行数据中包含所有父代信息.
这种设计,在现在很多场合仍是一个简单且方便的方案.但也不是没有不足.

1. 这种设计,在进行增删改查时,where的后面都有一些计算方法,这样就无法使用索引;
2. 数据量大时,如果只利用sql查询,效能就会比较低;

在设计一些同级数量注定不会很多,级别也不会很高的基础数据时,可以将"祖先路径"交由特殊的"编码"来实现.如:
第一级编码:0001
第二级编码:00010001
第三级编码:000100010001
以此类推.
由于每一级的位数都被限制在了4位,在计算时很多数值都是常量,计算量骤减.
这个折中方案在实际应用中有很不错的表现.

但本文所要说的,是另一种新设计,在查询中where后面不再追加计算方法,从而可以直接使用索引.
简单的说,就是创建一张新表-祖先后代关联表:在原有父子关系的基础上,记录所有的祖先后代关系.

2 数据库设计

还是以部门的继承关系为例,部门t_department表数据如下:

则生成的祖先后台关联表t_ancestor_offspring_relate如下:

其唯一索引是将id和ancestorId的关联.

可以看到,该表将所有的祖先ancestor与后代offspring的关联信息均记录在内.
仍以我们最常见的两种查询作示范:

1. 查询某个节点的所有后代

-- 如要查询名称,根据t_department联查即可
select id from t_ancestor_offspring_relate
where ancestor_id=?

2. 查询某个节点的所有祖先节点

--- 如要查询名称,根据t_department联查即可
select ancestor from t_ancestor_offspring_relate
where id=?

两种常用方法,均没有在where后面使用任何计算,因而可以使用索引.
如果在进行单据查询时的视野限制时,使用此表也可轻松达到想要的目的,如:

-- 这个sql的逻辑是根据当前部门id查询所有后代部门下的单据集合
select tf.* from t_form tf
inner join t_ancestor_offspring_relate taor
on toar.id=tf.department_id
and toar.ancestor_id=?

3 增删改操作

所有的增删改操作,t_ancestor_offspring_relate都是跟着t_department的逻辑进行的.
由于两个表必然是分开处理sql的,故内部方法的事务性是需要保证的.

1. 插入
   譬如要在原有部门的基础上插入一条数据:生产部的中间工程科(id为8,parentId为2).

-- 此处仅列出关系表的数据插入
insert into t_ancestor_offspring_relate
(id,parentId)
(
-- !!! 此处缺少ancestor_id=2的一条数据,需再额外加上
--- 实际执行中,最好通过先查询伪表中的数据,加上2,构成一条原始的insertBatch语句
select * from (
select 8 as id,ancestor_id as parent_id
from t_ancestor_offspring_relate
where id=2
)wt
)

2. 修改
   一般来说,部门是不能应当允许移动的.
   大多数的树状设计结构,都难以实现作为(特别是中间的)节点的迁移.
   如果一定要实现,则需通过几条分离的sql而非一条整体sql来实现.
   譬如,将原来的"售后科"(id为7,parentId为3)挪至已经被插入过的新的部门"品质部"(id为9,parentId为1).

-- [sql]1.查询新部门的所有祖先id,并在java中存到一个集合中lstNewAncestorId
select ancestor_id from t_ancestor_offspring_relate
where id=?

//[java]查询到结果后,追加原本就有的新部门id:9
List<Long> lstNewAncestorId=ancestorOffSpringRelateMapper.selectAncestorIdById(9);
lstNewAncecstorId.add(9);

-- [sql]2.查询旧部门的所有祖先id,并在java中存到一个集合中lstOldAncestorId
-- sql和1一样,故调用mapper中的相同方法
select ancestor_id from t_ancestor_offspring_relate
where id=?

//[java]查询到结果后,追加原本就有的旧部门id:3
List<Long> lstOldAncestorId=ancestorOffSpringRelateMapper.selectAncestorIdById(3);
lstOldAncecstorId.add(3);

-- [sql]3.查询待修改部门的所有后代id,并在java中存到一个集中中lstOffspringId
select id from ancestor_id from t_ancestor_offspring_relate
where ancestor_id=?

//[java]查询到结果后,追加本来要修改的部门id:7
List<Long> lstOffspringId=ancestorOffspringRelateMapper.selectIdByAncestorId(7);
lstOffspringId.add(7);

-- [sql]4.删除掉原有的旧部门祖先id集合
delete from t_ancestor_offspring_relate
-- 此处值取lstOffSpringId
where id in (?,...)
-- 此处值取lstOldAncestorId
and ancestor_id in (?,...)

-- [sql]5.插入新的部门祖先id集合
insert into t_ancestor_offspring_relate
(id,ancestor_id)
values
-- 此处的集合,为lstOffSpringId与lstNewAncestorId的笛卡尔乘积对象
(?..),(?,...)...

虽然代码量看着很多,实际执行速度还是很快的.

3. 删除(含子节点)
   如果你已经看完更新代码,了解其中的逻辑,那么删除(含子节点)的代码就很容易理解了.

-- 1.先获取所有后代id,含自身,存至lstIdDelete(在java中追加自身id)
select id from t_ancestor_offspring_relate 
where ancestor_id=?

-- 2.利用已经查询到的lstIdDelete,删除部门和部门关联表
delete * from t_department
where id in (?,...);
-- 这里不用使用delete联查,因为要删除部门数据本身
delete * from t_ancestor_offspring_relate
where id in (?,...);

以上增删改查操作,和"祖先路径"设计方案对比,性能上是有较大提升的,特别是在数据量较大的情况下.

4 数据初始化

如果你想要使用这种方案,但现在在开发的系统已经使用了一段时间,想要知道已有的数据怎么按照这种逻辑初始化,就需要看看这里.
这里仅将实现逻辑按照步骤列举出来,而非全部代码.

4.1 祖先递归后代法

1. 寻找虚拟祖先节点id

虚拟祖先节点id,就是某些(或全部)节点的共有祖先节点id,但自身并不对应实体的节点.
文章中开始提供的数据中,虚拟祖先节点id就是0,它是所有节点的祖先节点id,但没有对应实体的节点.

找寻虚拟祖先节点id的方法:
查找所有的祖先节点id,再从中去掉那些同时是后代节点id的数据.

譬如在本例中,祖先节点id中包含:0,1,2,3.但只有0不是后代节点,因而就是虚拟祖先节点id. 此步骤,建议在java中执行,在mysql中执行效率比较低.

//java ver1.8
//1.查找所有父id,并去重
List<Long> lstParentId=departmentMapper.selectAllParentId();
Set<Long> setParentId=new Set<>(lstParentId);
//2.查找所有子id
List<Long> lstId=departmentMapper.selectAllId();
//3.父id过滤
List<Long> lstVisualAncestorId=new Array<>();
for(Long lngParentId:lstParentId){
    if(lstId.stream().anyMatch(i->!i.equals(lngParentId)){
        lstVisualAncestorId.add(lngParentId);
    }
}

2. 根据虚拟祖先节点,递归查找对应的子节点id,并生成对应的批量关系数据

//TODO 此步代码略(以后有时间补充).

4.2 排序分批插入法

1. 将节点顺序,根据祖先->后代的关系进行排序
   如果你能确保节点数据中的先后顺序,必然是祖先->后代,则此步可以省略.

//此步详细代码略(大致思想参考如下)
//1.先确定虚拟祖先节点(确定方法参考4.1.1),另所有虚拟祖先节点下的节点,level设置为1
//2.遍历节点,当发现parentId为1级节点时,设置节点的level为2
//3.以此类推.当所有节点的level均被设置后,或者某一次遍历出现没有给任何节点设置level的情况时,遍历停止
//4.将节点数据根据level进行排序

2. 依次批量生成关系数据

//假定lstDepartmentSorted是排过序后的集合
//List<Department> lstDepartmentSorted;
Map<Long,List<Long>> mapOffspringAncestorIdList=new HashMap<>();
for(Department o:lstDepartmentSorted){
    List<Long> lstAncestorId=mapOffspringAncestorIdList.get(o.getId);
    if(lstAncestorId==null){
        List<Long> lstIdInit=new ArrayList<>();
        lstIdInit.add(o.getParentId);
        mapOffspringAncestorIdList.put(o.getId,lstIdInit);
    }else{
        //这里用到了hutool的clone方法
        List<Long> lstIdClone=ObjectUtil.clone(lstAncestorId);
        lstIdClone.add(o.getParentId);
        mapOffspringAncestorIdList.put(o.getId,lstIdClone);
    }
}
List<AncestorOffspringRelate> lstRelate=new ArrayList<>();
for(Long lngOffspringId:mapOffspringAncestorIdList.keySet()){
    List<AncestorOffspringRelate> lstRelateEach=mapOffspringAncestorIdList.get(lngOffspringId).stream().map(i->{
        AncestorOffspringRelate mRelate=new AncestorOffspringRelate();
        mRelate.setId(lngOffspringId);
        mRelate.setAncestorId(i);
        return mRelate;
    }).collect(Collectors.toList());
    lstRelate.addAll(lstRelateEach);
}
//批量插入
ancestorOffspringRelateMapper.insertBatch(lstRelate);

注:
不论是先从祖先节点触发,还是要求排序必须是祖先->后代,这样做的原因,是为了避免出现循环嵌套的情况出现.
譬如最简单的情况,a部门的上级是b部门,b部门的上级是a部门.
两种方法的前置步骤均是为了规避这种情况的出现.

end