总阅读量:次

⭐⭐⭐ Spring Boot 项目实战 ⭐⭐⭐ Spring Cloud 项目实战
《Dubbo 实现原理与源码解析 —— 精品合集》 《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》 《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》 《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》 《Java 面试题 + Java 学习指南》

摘要: 原创出处 juejin.cn/post/6999977878045589512 「我键盘侠吧」欢迎转载，保留摘要，谢谢！

🙂🙂🙂关注微信公众号：【芋道源码】有福利：

  1. RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表
  2. RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址
  3. 您对于源码的疑问每条留言都将得到认真回复。甚至不知道如何读源码也可以请教噢。
  4. 新的源码解析文章实时收到通知。每周更新一篇左右。
  5. 认真的源码交流微信群。

背景

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

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

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

方案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以及之后的元素向后移动：

方案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、双向链表方案：插入、更新性能高，查询要做额外处理

文章目录
  1. 1. 背景
  2. 2. 方案1- 数组
    1. 2.0.1. 存在的问题
  • 3. 方案2- 双向链表
    1. 3.0.1. moveAfter
    2. 3.0.2. moveBefore
    3. 3.0.3. 存在的问题和改进
  • 4. 语雀的方案
  • 5. 总结