2020 年了，现在对于拖拽排序有什么更好的存储方案？

[raysonlu]

记得以前设计 CMS 系统的时候接触过这个问题，

文章表加一个 sort，然后让用户自己填写 sort 值，越大就越靠前，再加个 id 排序解决同样 sort 值问题，这种很适合翻页排序（特别是翻页后不显示其他页内容），但需要用户自己填写数值感觉不太友好。

后来出现了“拖拽排序”的交互，这种填值方式就走不通了，置顶和置尾还可以前端自动填值，中间的移动就没办法了，除非移动后把后面所有文章的 sort 值都 update 一次，少量文章还可以，量大了而且还可能涉及到多人同时操作的话，要不得。

寻求过其他方法，很多都说用“除二法”， 就是每个文章排序号中间有间距（ 100 和 200)，每往中间拖一个，sort 值就改为前后间距的二分一(150)，如此类推，一直除下去将会是浮点数。 且不说浮点数精准度会不会出现问题，乍看这个方案貌似有“次数限制”，如果不停地往“某个中间”拖入一个，浮点数的长度就是限制？后来想到一个法子规避这个次数限制，用定时任务方法定期优化一下排序数字，这算是个可行但很难的方案吧~~~

现在又遇到一个类似的开发需求，想咨询一下 2020 年了有无更好的解决方案？

[weixiangzhe]

那不用数字成不成
1. 原始序号是 1,2,3,4,5
2. ‘5’拉到 1,2 之间变为 1@1
3. ‘4’再到 1,2 之间变为 1@2
4. ‘3’ 再拉到'1','2'之间为 1@1@1
5. 最后再按 @分割排序

[keepeye]

其实也不用更新太多吧？一页能有几条数据，只要更新两个位置中间的行就可以了

[Shy07]

文章 id 单独保存一个排序数组，简单暴力

[flipped598]

同意二楼所说的，不用更新后边全部的，只更新两个位置中间所说的就行了，一页也没有多少数据。我们系统的后台就有这样的需求，由于基本上没有并发操作，目前也是这么实现的。

[star7th]

我还真的是这么做的，不觉得有什么问题。我在 showdoc 的实现排序机制有两种，github.com/star7th/showdoc ，一种是用户操作后，就把目录 /页面的数字排序都更新一遍。一种是项目排序，简单地保存整个数组，然后读取的时候，在代码里根据这个数组进行重排。目前没遇到啥问题。你上面考虑的性能问题，算法问题，我觉得是多虑了的。不会有那么多人并发操作，也不会 update 得特别慢。就这么简单处理就好。

[fancy2020]

正好现在做的项目<橙子简历> https://wonderfulcv.com 在编辑简历的部分有拖拽排序的功能，我是单独用一张表存储排序 id，数据量不大的话这样做比较省心

[damngood]

我一般是用 double

[index90]

你拖拽的跨度有多大？
假设你一个页面有一百条数据，那么每次拖拽用交换排序，最多更新一百条数据的索引值。

[yc8332]

如果都有排序，其实只要更新交换的两个而已，如果没有排序或者有些值是一样的，那可能会多更新几个。。。这个我做过

[SakuraKuma]

拖拽排序问题不大, 对比原序号和新序号 patch 一下就好, 现系统就是这么搞的.
问题是跨分页排序, 不分页嘛, 数据太多, 分页嘛, 跨分页拖拽不了.

有大佬提供下好思路嘛~

[lookas2001]

实现一个序列，支持 O(logn)插入、删除（类似文字编辑器），典型的算法题啊，用平衡树，即使在最坏情况下也能保证时间。
不过我觉得一般情况下，你最后提出的解决方案已经能很好的解决问题了，码量也不大。

[lookas2001]

平衡树也有实现，如果使用 js，可以看看这个库 https://github.com/mourner/bbtree

[hronro]

@lookas2001 问的是储存方案，最后应该是要和数据库挂钩的

[raysonlu]

@keepeye
@Shy07
“只更新两个位置中间”，是指那个“除二法”吗？那个确实没有批量更新和并发锁行的问题，但理论上会出现了次数限制啊，另外这个法子和一页多少条数据无关吧，只要往同一个位置拖入，那个位置不断除二，就出现次数限制了。

[raysonlu]

@star7th
@fanchangyong
@index90
当数据量大，比如有 10W(或更多）个文章，把开头第十个拖到第五个下面，那么就要更新其他文章（ 10W-5 个）的排序号？

[raysonlu]

@lookas2001 定时器方案确实能解决，但这的确太奇葩，我思考着我以后项目交接接手人看到这个定时任务会一脸懵逼，毕竟我刚在小组提出这个问题，几乎全部人一来就表示“这不是很简单吗”。平衡树我也有用来解决过一些需求，但这里无法应用啊，毕竟基本场景是数据库查表。

@hronro 当然如果有其他曲线方案能解决也比较好，比如数据库纯天然般支持这种排序需求

[fancy2020]

@raysonlu 我的回复里说过了，我的数据量不大所以才这样做，我需要排序的数据只有个位数(每个简历里的教育经历等的排序)。十万这种的肯定就需要其他方案了

[DavidNineRoc]

数据量大要处理的问题:
加入排序位置是
1 10 100 100

1. 把第三位放到第一位的处理方案
2. 之后把末尾放到第一位的解决方案
3. 重复以上两个步骤一百次.

[DavidNineRoc]

如果对于用户级别的排序没有分页可以考虑使用双链表, 全部的排序另说

[index90]

@raysonlu 怎么会呢？
假设你当前页有十条数据，你现在把第 7 条数据拖到第 4 条数据前，那么需要变更的数据有 D，E，F，G：
1 A--A
2 B--B
3 C--C
4 D--G
5 E--D
6 F--E
7 G--F
8 H--H
9 I--I
10 J--J

所以结合场景，如果你一页所展示的数据大小为 100 条数据，那么最坏的情况下，你要变更 100 条数据，无论你的总量是多少。
但如果你支持跨页拖拽，你就当我没说。

[sarvatathagata]

作为一个 OIer，一般用替罪羊树做动态标号就行了。

[Akkuman]

100/(2^1000)=9.3326362e-300

DOUBLE——一个双精度浮点数。支持 -1.7976931348623157E+308 到-2.2250738585072014E-308，0 和 2.2250738585072014E- 308 到 1.7976931348623157E+308 。如果是 FLOAT，UNSIGNED 不会改变正数范围，但负数是不允许的。
• DOUBLE PRECISION——同 DOUBLE
• REAL——同 DOUBLE
• DECIMAL——将一个数像字符串那样存储，每个字符占一个字节
• DEC——同 DECIMAL
• NUMERIC——同 DECIMAL

也就是说，你往同一个地方不停地得拖动一千多次，才会出现次数限制，现实场景好像并不多，如果担心可以用 decimal

[index90]

？？？
是我理解错题目了？
难道不是在一个 10W 个元素的数组中，把第 10 个元素移动到第 5 个元素的位置吗？那么只要重排 5~10 位置上的元素就可以啦。跟第 11，12，13，第 10 万的元素有什么关系呢？时间复杂度就是元素移动的距离。
好像还有置顶和置尾功能？用标记就好啦，查询的时候用 where 过滤一下。

越看评论越觉得我弱智了，是我理解错了吗？

[agagega]

别用浮点数，用字符串。A 和 B 中间的，就是 AA

[Shy07]

@raysonlu
我说的文章 id 单独保存一个排序数组是指：id 1~5 的文章就单独保存一个 [1...5] 的数组 a

分页显示 [1, 2, 3] ，排序后是 [3, 2, 1] 的话，就更新数组 a page 和 pageSize 范围内的值。

这样的好处是不用修改文章数据，你在排序的时候，别人也可以编辑文章内容；同时文章本身是如何存储的、顺序如何数组 a 完全不 care.

[px920906]

之前正好也搜过相关的方案，teambition 就是“除二法”，每次请求后都检查一遍，不满足相邻最小差值就重新计算并返回新的值给前端 -> https://www.zhihu.com/question/55789722/answer/146650607
（回答好像写错了吧

[raysonlu]

@index90 不好意思，我那个举例的确有一些问题，如你所说“时间复杂度就是元素移动的距离”是正确的，但我初衷也是想解决这个问题。
也的确要“支持跨页拖拽”，按我的理解，出现了“拖拽”这个交互后，仅仅显示一页的内容让用户拖拽排序是没意义的吧（比如把下一页的第一个拖拽到这一页中间），这时候一般做下拉式分页展示，也因此，跨度距离就变得不可控（想象中的交互场景：用户抓起某个文章，移动到靠上(下)的位置，页面不停往上(下)滚动，然后找到位置放下）

[mazhan465]

为啥不用链表呢，或者跳表？

[raysonlu]

@mazhan465 链表方案也有看过，但这种不好在数据库里查找吧？

[mazhan465]

@raysonlu 表加个 next 字段，保存下个节点的 id，比如当前顺序 1,2,3,4,5，将 5 拖到 2,3 之间，查 next=3 的改为 next=5,next=5 的改为 5 的 next，也就是 NULL 或者 0

[mazhan465]

@mazhan465 这样做的缺点就是不把数据全倒出来无完成排序

[raysonlu]

@mazhan465 #13 是啊，分页排序本是类似“把数据全倒出来”的活儿，只是数据库的 order 帮我们优美地干了，但这种链表的方案，就只能做在业务代码层了，这就”真·全倒出来“了~

[no1xsyzy]

@Akkuman #22 你必须往 0 附近拖动导致指数不断改变才能这么算，不然双精度最多 51 次二分。

[no1xsyzy]

不太确定还需要何种访问方式，盲狙一个 B-tree

[raysonlu]

@no1xsyzy 请教如何实现

[no1xsyzy]

@raysonlu #35 做一张表来实现，表的一行代表 B-tree 的一个节点，用 id 来引用
其实各种树都可以这么玩，只不过访问数据库次数比较关键，选访问次数比较低的树吧，宽度比较大的 B-tree 会比较好。
只不过 “给定项目，获知其在第几个位置” 的查询比较麻烦

更加元分析地：一维数组，处理序相关问题基本就是树和桶，访问次数低的就是 B-tree 和 “二除法”。
盲狙一个 B-tree 没错的，不过也就是盲狙，并没有相应场景的实际的演练。
桶其实大部分情况下可以用了，遇到极限情况进行重建就行。就算是定时任务，做好注释问题不大。
如果不能满足要求那就是树了。

也可能不是你自己实现，采用数据库内已经是树方式实现的索引方式也是可以的，访问次数也很低。