从零开始构建：后端实现拖拽排序功能

👉 这是一个或许对你有用的社群

🐱 一对一交流/面试小册/简历优化/求职解惑，欢迎加入「芋道快速开发平台」知识星球。下面是星球提供的部分资料： 

• 《项目实战（视频）》：从书中学，往事中“练”
• 《互联网高频面试题》：面朝简历学习，春暖花开
• 《架构 x 系统设计》：摧枯拉朽，掌控面试高频场景题
• 《精进 Java 学习指南》：系统学习，互联网主流技术栈
• 《必读 Java 源码专栏》：知其然，知其所以然

• 背景
• 方案1- 数组
• 方案2- 双向链表
• 语雀的方案
• 总结

背景

在工作中，开发管理后台时，经常会遇到“拖拽排序”的需求，比如有一个资源列表，在前端可以拖拽来改变资源的顺序。类似于语雀的知识库，用户可以拖拽文档的顺序，如下图所示：

我们项目中实现这个功能的方式是：资源表有一个 position 字段，前端查询时，根据该字段进行升序或降序排列，拖拽时修改表中涉及到的记录的 position 字段值。

然而，这个方案有一个问题：我们每次只是拖拽一条记录，却对多条记录进行 UPDATE 操作，有没有更好的方案？下面介绍两个自己思考的方案。

基于 Spring Boot + MyBatis Plus + Vue & Element 实现的后台管理系统 + 用户小程序，支持 RBAC 动态权限、多租户、数据权限、工作流、三方登录、支付、短信、商城等功能

• 项目地址：https://github.com/YunaiV/ruoyi-vue-pro
• 视频教程：https://doc.iocoder.cn/video/

方案1- 数组

在资源表中设置一个 position 字段来表示记录的位置，MySQL 的 DDL如下：

CREATE TABLE `activity` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT 'ID',
  `position` int(11) DEFAULT '0' COMMENT '位置值',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

前端查询数据列表时，按照 position ASC 或 DESC 排序：

SELECT * FROM activity ORDER BY position ASC;

拖拽一条记录时，前端传入该记录的 id 值和新的位置值 new_position，服务端根据 id 查询出资源原本的 position 值（为 old_position），比较 old_position 和 new_position，分为以下三种情况：

1、old_position == new_position

处理方式：保持不变

2、old_position ≠ new_position

• old_position < new_position：把记录向后拖拽了
• old_position > new_position：把记录向前拖拽了

需要修改的数据范围有：所有 position >= new_position 的记录，把这些数据的 position 值加1。MySQL 语句如下：

UPDATE activity SET position = position + 1 WHERE position >= #{new_position}

存在的问题

每次拖拽都要修改很多行数据，如果把一条记录拖拽到第一行，要修改表中所有数据的 position 值，会给数据表加上一个表锁（X锁），导致数据库并发性能降低。

之所以会出现这个问题，是因为这种方式本质上是以“数组结构“来组织数据，每次拖拽一条记录时，相当于把一个元素插入到数组中某个位置。

数组的性质就是：在插入元素时，要把插入位置后面的元素集体后移。如下图所示，把元素10插入位置2时，要把位置2以及之后的元素向后移动：

基于 Spring Cloud Alibaba + Gateway + Nacos + RocketMQ + Vue & Element 实现的后台管理系统 + 用户小程序，支持 RBAC 动态权限、多租户、数据权限、工作流、三方登录、支付、短信、商城等功能

• 项目地址：https://github.com/YunaiV/yudao-cloud
• 视频教程：https://doc.iocoder.cn/video/

方案2- 双向链表

与数组相比，链表更适合元素插入，每次插入一个元素，只需要移动元素的前后指针，如下图所示，把 NewNode 插入到 Node1 和 Node2 之间，只需要改变三者的前后指针：

我们在数据库里，增加两个字段 prev_id、sibling_id（这里参考的是语雀的命名，见后面介绍），分别表示前后指针，DDL如下：

CREATE TABLE `activity` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT 'ID',
  `prev_id` int(11) DEFAULT NULL COMMENT '前一个元素的ID',
  `sibling_id` int(11) DEFAULT NULL COMMENT '后一个元素的ID',
  `position` FLOAT(6,2) DEFAULT '0.0' COMMENT '顺序位置',
  PRIMARY KEY (`id`),
  KEY `idx_prev_id` (`prev_id`),
  KEY `idx_sibling_id` (`prev_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

因为现在记录之间是通过前后指针建立关系，拖拽是把记录拖拽到某条记录后面，或拖拽到第一条记录的前面，所以下面分别介绍这两种情况。

moveAfter

拖拽记录到某个记录后面。

前端传入该记录的 id 和它新的 prev_id（前一个记录的ID），后端根据 id 和 prev_id 更新数据，更新过程如下：

1、根据 id 查询出当前记录数据 curActivity

curActivity : SELECT * FROM activity WHERE id = #{id};

2、更新 curActivity 前后记录的指针

UPDATE activity SET prev_id = #{curActivity.prev_id} WHERE id = #{curActivity.sibling_id};
UPDATE activity SET sibling_id = #{curActivity.sibling_id} WHERE id = #{curActivity.prev_id};

3、根据 prev_id 查询出前一个记录数据 prevActivity

prevActivity : SELECT * FROM activity WHERE id = #{prev_id};

4、设置 prevActivity 的指针和后续记录的指针

UPDATE activity SET prev_id = #{id} WHERE id = #{prevActivity.slibling_id};
UPDATE activity SET sibling_id = #{prevActivity.slibling_id} WHERE id = #{id};

UPDATE activity SET prev_id = #{prev_id} WHERE id = #{id};
UPDATE activity SET sibling_id = #{id} WHERE id = #{prev_id};

把一条记录拖拽到某条记录之后，只需要执行6次 UPDATE 操作。

moveBefore

拖拽记录到第一条记录前面。

前端传入该资源的 id 和它的 sibling_id（后一个资源的ID），后端根据 id 和 sibling_id 更新数据，更新过程如下：

1、根据 id 查询出当前记录数据 curActivity

curActivity : SELECT * FROM activity WHERE id = #{id};

2、更新 curActivity 前后记录的指针

UPDATE activity SET prev_id = #{curActivity.prev_id} WHERE id = #{curActivity.sibling_id};
UPDATE activity SET sibling_id = #{curActivity.sibling_id} WHERE id = #{curActivity.prev_id};

3、根据 sibling_id 更新后一个记录的 prev_id

UPDATE activity SET prev_id = #{id} WHERE id = #{slibling_id};

4、更新 curActivity 的 slibling_id

UPDATE activity SET slibling_id = #{slibling_id} WHERE id = #{id};

把一条记录拖拽到第一条之前，只需要执行 4 次 UPDATE 操作。

可以发现，方案2使用前后指针，每次拖拽操作的需要执行的 UPDATE 记录数（最多执行6次UPDATE，影响5条记录），平均下来是小于方案1的；而且方案2对数据表加的是行锁，对数据库并发性能的影响小于方案1。

存在的问题和改进

虽然方案2适合插入记录，但是也有链表的缺陷：不适合遍历查询，要先查询出链表的一条记录，然后根据 sibling_id 不断把下一条记录查询出来。方案2记录只适合于“全量查询”的场景，无法像方案1那样，根据 position 做排序和分页查询

怎么能让方案2页支持排序和分页？

有一个粗糙的方案：

在方案2的 DDL 中，设置了一个浮点字段 position，在移动记录时，更新 position = (前一个记录的 position + 后一个记录的 position) / 2。这样在查询的时候，依然可以根据 position 字段排序，具体 position 字段的精度，可以根据业务中，调整的频繁程度进行选择。

语雀的方案

这里是根据语雀接口的参数，对它的实现方案的一个猜测，不一定准确。

我们在语雀上，把文档拖拽到另一个文档之后，查看接口调用：

PUT /api/catalog_nodes

传入的参数如下：

{
    "book_id":10922139,
    "format":"list",
    "action":"moveAfter",
    "target_uuid":"88bJcaqwdyEx2_KN",
    "node_uuid":"yJAhTFEUOfOVEFOo"
}

使用的就是方案2的双向链表，传入了参数：action、target_uuid 、node_uuid 分别表示：向后移动、prev_id、id；并且接口返回的结果中也有 prev_uuid、sibling_uuid，如下图所示，接口返回的数据顺序和我们页面上显示的顺序是相同的：

方案2不适合做分页查询，所以语雀的文档都是全量查询的，没有做分页，应该是在内存里排序后返回给前端。

总结

介绍了两种拖拽排序的后端实现方案：

1、数组结构方案：插入、更新性能差，查询方便

2、双向链表方案：插入、更新性能高，查询要做额外处理