背景
在工作中，开发管理后台时，经常会遇到“拖拽排序”的需求，比如有一个资源列表，在前端可以拖拽来改变资源的顺序。类似于语雀的知识库，用户可以拖拽文档的顺序，如下图所示：
我们项目中实现这个功能的方式是：资源表有一个 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、双向链表方案：插入、更新性能高，查询要做额外处理
关注微信公众号“CodeGo编程笔记”，每周发布编程文章，一起学习共同进步。
