可拖拽树形数据服务器端的一种实现

2023-12-19 09:33:03

树形结构的数据常用于部门管理等有层次结构的场景。目前对于树形结构的UI操作已经有相当多的库了，如ztree、jsTree；一些出名的组件库也都内置的相应的组件，如element-ui。但就目前关于树拖拽操作的后台逻辑实现却少有人提及，特别是在像mysql这种关系型数据下的实现。正好公司前些日子需要这个功能，形成了一个实现方案，整理后放出。

观前提示

非Java警告：案例使用kotlin+springboot写成
非传统ORM警告：ORM框架选用ktorm。别问，问就是开心就好

不了解kotlin基本语法可能看着会有点恼火，毕竟它的糖实在是太多了。查询使用的语句比较简单，不了解ktorm，应该影响不大。
?

案例代码：gitee

业务需求

部分新用户一次性导入大量的部门信息，需要调整部门间层级关系。原有的编辑框操作繁琐也不直观，所以想能不能通过拖拽实现层级关系调整。
?

经过调查，用户导入的部门数量最大在四位数的量级，部门层级最多在5级之内。由于有权限的设定，所以也有查询某部门下所有子部门的需求。
?

总的来说，拖拽功能是较低频的操作，而查询某部门下所有子部门是高频操作。因此功能设计的总体目标也就出来：拖拽可以慢点，查询需要快。
?

数据库设计

在关系型数据存储树形结构通常考虑四种方法：

邻接表（Adjacency List）：保存pId值
路径枚举（Path Enumerations）：记录此节点经过的路径
嵌套表（Nested Sets）：比较麻烦，记录左值、右值，计算方式有点麻烦
闭包表（Closure Table）：用另一张表辅助记录

此次采用前两方式混合。即

CREATE TABLE `tree_node`
(
    `id`          int unsigned NOT NULL AUTO_INCREMENT,
    `create_time` datetime     DEFAULT NULL,
    `name`        varchar(60) NOT NULL,
    `node_path`   varchar(500) DEFAULT NULL,
    `p_id`        int unsigned DEFAULT NULL,
    PRIMARY KEY (`id`)
) ENGINE=InnoDB

p_id记录此节点的上级节点的id值。如果没有上级节点则为空。
node_path记录所有上级节点id值，用 ,分隔，如果没有上级节点则为空。
?

关于根节点

在写此案例时，为了简便，将根节点设定为虚拟的。即在代码设定一个id为null为根节点，数据库中所有p_id为空的节点都此虚拟节点的子节点。
如果不希望出虚拟节点则考虑添加一个标识符，做某些运算注意避开就行。
?

功能实现

此次功能重点在拖拽和查询，其他新增、编辑之类操作就略去。
?

查询

加入node_path字段就是为了提高查询效率的。根据我们的设定，查询任意节点下所有子节点仅需要一次查询，其伪代码如下：

`node_path` like CONCAT(此节点的`node_path`,‘,‘,此节点的id,‘%‘)

当然大部分情况下还需要包含当前指定节点信息，所以还需要再根据id查询一次。对于我们设定有虚拟节点的情况，还需要再加一个if分支，具体可见TreeNodeService#findSubTree方法。

组装树形结构

仅仅查询扁平化的数据是不够的，我们还需要将数据组装成前端可用的数据。
对于我们这个规模的数据组装倒不难。此处用空间换时间，用两个循环和一个map来实现。大体思路为：

将所有数据先遍历到map中去，以节点id为k，节点为value
再次遍历所有节点，并从map中找到它的上级节点，将此节点加入到它上级的childList集合中
最后从map中取出根节点。（这里稍微有点奇怪，只能从map中取根节点，在外面根节点是没有值，不知道是不是kotlin函数仅支持值传递的原因。）

具体可见NodePathUtil#assembleTreeData方法。
?

拖拽

这里是最麻烦。由于拖拽是在页面操作完成，所以需要先了解常用拖拽组件的实现。考察过ztree、iview等组件的拖拽功能后，可以总结出这些组件在拖拽时提供信息，将归纳总结如下：

sourceNode：被拖动的节点
targetNode：拖动到目标节点
direction：相对方向。一般会有三个，如inner 、prev、next表示到目标节点的内部，前面，后面。不同组件下用的单词不一样。但需要注意这仅表示相对方向，即从第一层级拖到第十层级也只会有这三个方向。所以前端组件没办法很好表示跨层级移动。

经过上面的分析，我们得出拖拽动作需要最少数据如下：

data class TreeNodeMoveVO(
    val sourceId: Int,
    val sourcePid: Int?, // 被移动后新的pid
    val targetId: Int?,
    val direction: MoveDirection, // 移动方向枚举
)

正如前面的分析，我们对于节点移动具体信息是不清楚的，没办法知道此节点是从哪一级移到哪一级的（事实上就算知道了对实现也没太大帮助）。大体思路：

加载所有节点信息
找出被移动的节点（sourceNode），并给它设置新pId
根据sourceNode新的pId遍历出新的node_path，并赋值回去
对除sourceNode的节点进行遍历，计算出新的node_path；把有变化的节点的加入待更新列表
更新sourceNode的值和待更新列表中节点信息

具体代码见TreeNodeService#moveNode方法。
?

说明：

为什么要根据pId遍历出新的node_path？

node_path是以字符串的形式保存的，当中间层级节点被移动时，它的所有子节点都需要进行node_path以确保子树查询的正常性。正如之前分析，无法很好地获取节点层级移动信息，所以对node_path更新无论是采用是字符串切分或是正则都会出错。所以才使用此方法。如果有兴趣可以采用其他方法试试。

为什么要所有节点再进行遍历呢？

正如上问题的原因一样，这是为了更新sourceNode它的子节点node_path。虽然可以通过查询直接获取它的子节点，这里的处理就看个人需求了。
?

备注

测试包内TreeNodeDataInit#initData可快速生成一千条三个层次的数据。