自定义排序

背景

新增功能时发现 修改个 栏目 修改了2秒多 速度很慢

查找了下代码 原来是 自定义 栏目排序的 order

同事写的逻辑

查出所有的 栏目 再一个个 Update 数量一多就会慢的要死

借鉴下网上其他人的思路

偏代码角度描述方案(link)

方法一 全量更新元素位置法

适用场景：排序元素数量较少

原理：每个元素拥有一个字段，表示元素当前排序的位置。通过前端排序，将排好的元素位置，一次性发送到后端。然后，后端统一更新所有元素的位置。

具体实现

实体设计：增加排序字段 sort，表示元素当前的位置。例如，sort = 1，则表示元素处于第一位。

接口设计：

// 排序接口
POST /courses/sorting

// 格式：JSON
// 数组中为元素的ID
// 元素在数组中的序号，表示了元素的位置
// 例如，ID为3的元素，排序为 1，ID为2的元素，排序为2
[3, 2, 4, 1]

前端逻辑：当前端排序后，或删除元素后，将剩余元素ID，以数组的形式发送给后端。数组的索引序号，则表示元素当前的排序。

后端实现逻辑：

• 删除不存在前端数组中的ID。将前端 ids，与服务器端的 ids 进行对比。删除服务器端存在但前端不存在的 ids。
• 按照数组的排序，更新所有元素排序。

总结，此方法仅适用于排序元素较少（例如，总元素为5~15个）的场景。对于大量数据排序并不适用，适合首页轮播图管理、任务卡片管理。leangoo 的看板卡片管理就是采用这种方式。

方法二 取中值法（推荐）

原理与实现步骤：

1. 创建元素时给元素赋默认位置（pos字段记录该值）。赋值规则为，当创建第一个元素时，默认位置赋值为65536，第二个元素为 2 * 65536 = 13172，增加第N个元素时，位置赋值为N*65536。
2. 当拖拽改变元素位置时，更新 pos。更新规则如下：

• 调整一个元素到两个元素中间时，(pre_item.pos + after_item.pos）/ 2 = pos
• 调整一个元素到第一个元素时， old_first_item.pos / 2 = pos
• 调整一个元素到最后一个元素时， old_last_item.post + 65536 = pos

1. 当前后两个元素的数值，不满足整数时，更新所有元素的排序。依次给每个元素的 pos赋新值。例如，第一位赋值65536，第二位为2 * 65536，第N位赋值N*65536。

通过取中值的方法，改变元素的位置。当需要按序获取时，只需要对 pos进行排序，就可以获取元素的位置。

关于中值重排的问题，解决方法有多种。例如，我们可以使用浮点数储存 pos，但是需要考虑数据库存储的精度问题。而且，数值过小，会在前端丢失精度，元素排序会出现问题。当然，如果在接口层，当检测到中值过小，则对所有元素进行重排，接口相应速度会存在问题（如果是后端管理系统就不用考虑性能问题了）。

有人提出，利用定时任务每天对所有元素定时重排，来解决单次接口的性能问题。个人觉得这个方法，还是存在问题。若定时任务不及时，那么排序由于精度问题，发生了排序错乱的问题。那么，定时重排已经无意义。

方法三 单表单列

每个元素，都有一个字段index，表示元素的排序信息。
规定元素从0开始递增。
基本操作如下：

• 增加数据。 新增元素时，序号为当前元素数据总量值。
• 删除元素。删除元素时，将大于该元素的序号，都减1。
• 修改元素排序。当元素从 x 移动到 y 时，
  • 若 x < y 时，则将(x, y)范围内的元素都减1
  • 若 x > y 时，则将(y, x)范围内的元素都加1
• 查询元素。展示列表时，按照 index 字段进行排序即可。若需要查第n位元素时，元素位置为 index = n - 1。

这种方式优点是，查询快，修改慢。而且，修改接口的逻辑较重，处理起来比较麻烦。我们很多项目都是采用这种模式。在接口设计方面，我们让前端传给后端是一个偏移值（offset），offset = y - x。当元素向排序大的方向移动时，offset的为正值；若往排序小的方向移动时，offset`为负值。

偏数据库角度描述方案(link)

1. 单表单列结构（数组结构）

此设计是使用一个表中的一列来表示数据的序号，通常我们使用的方法就是这种。

数据表tb_data(n)：

data	index
···	0
···	1
···	2

这里规定序号从0开始递增。

其基本数据操作如下：

• 增 → 当增加一个数据时，定义data的序号为数据总数量值。
• 删 → 当删除一个数据时，将大于该序号的数据的序号都减1。
• 改 → 当修改位置将数据a从x移动到y时，若x小于y，则将(x,y]范围内的数据序号都减1；若x大于y，则将[y,x)范围内的数据序号都加1（注：修改数据库时，要先将a的序号x修改为未被使用的序号z，然后再修改范围内的数据，最后再将z修改为y，顺序不能乱）。
• 查 → 当查找数据时添加 order by index 即可得到自定义排列的数据，查找第n个数据时查找条件为 index=n-1 即可。

总结：此方法查找速度最快，修改速度最慢。

2.单表双列结构（链表结构）

此设计是使用一个表中的两列来表示数据的序号，一列表示该数据的前置id，一列表示该数据的后置序id（id为数据表本身的自增序号），即相当于我们经常使用的双向链表。

数据表tb_data(n)：

id	data	pre_no	next_no
0	···	-1	1
1	···	0	2
2	···	1	3
3	···	2	-1

这里规定第一个数据的pre_no为-1，最后一个数据的next_no为-1。

其基本数据操作如下：

• 增 → 当增加一个数据a时，先查找出最后一个数据b的id号，a的pre_no定义为b的id号（若此数据为第一个则定义为-1），next_no定义为-1，再将b的next_no定义为a的id号。
• 删 → 当删除一个数据a时，取出a的pre_no和next_no，将pre_no对应的id的数据的next_no修改为a的next_no，将next_no对应的id的数据的pre_no修改为a的pre_no。
• 改 → 令位置x-1、x+1数据分别为b、c，位置y-1、y、y+1的数据分别为d、e、f，现修改位置将数据a从x移动到y时，
  当x小于y时，修改b的next_no为c的id，修改c的pre_no为b的id，修改e的next_no为a的id，修改f的pre_no为a的id，最后修改a的pre_no为e的id，next_no为f的id；
  当x大于y时，修改b的next_no为c的id，修改c的pre_no为b的id，修改d的next_no为a的id，修改e的pre_no为a的id，最后修改a的pre_no为d的id，next_no为e的id。
• 查 → 当查找第n个数据时，需要先查找出第一个数据，在根据第一个数据逐个往后查找数据的next_no，查找n次后得到第n个数据。

总结：此方法查找速度最慢，修改速度最快。

3.双表双列结构（分页结构）

此设计是使用一个页码表记录全部页码和页码的序号范围，另一个数据表来记录基本数据、自身序号和页码，通过在一个表中给数据设置不同的序号和页码来达到分页排序的效果。

页码表tb_page：

tb_name	page	start_index	end_index
tb_data0	0	1	1000
tb_data0	1	1	1000
tb_data0	2	1	120
tb_data1	0	1	1000
tb_data1	1	1	130

table_name为一个基本数据表的表名，对于每一个table_name，其对应的page都从0开始递增且不能重复，每个page有一定的数据范围（这里设定为一页有1000条数据），则每个数据表对应的数据总量即可计算出来。

基本数据表tb_data(n)：

data	page	index
···	0	1
···	0	···
···	0	1000
···	1	1
···	1	···
···	1	1000
···	2	1
···	2	···
···	2	120

data为数据域，记录基本数据，对于每一个不相同的data都有对应的page和index，通过page、index和每一页的数据范围即可计算出对应的全局序号。

其基本数据操作如下：

• 增 → 当增加一个数据时，先从页码表中查找出最后的page及其对应的start_index和end_index，若end_index-start_index+1没有数据超出范围，则插入数据的page不变，index为end_index+1，若超出范围，则需在页码表中新建一页，插入数据的page自加一，index赋值初始值。
• 删 → 当删除一个数据时，因为需要保证除末页以外的页码的数据范围都为规定值，所以需要对删除数据对应的页码及以上页码的数据进行调整，对于删除数据的页码，可以通过对比该数据在页码中的相对位置来调整较小数据量的一方数据执行加减1，对于大于其的页码，可以将每一页的首数据调整为上一页的末数据（末页数量为0即可将末页删除）。
• 改 → 当修改位置将数据a从x移动到y，计算x、y对应的页码，当x、y的页码相同时，只需调整该页数据，可通过对比x到y的数量和页码数量来决定调整x、y范围内还是范围外的数据信息；当x、y页码不同时，可通过对x、y在页码中的相对位置来调整较小数据量的一方数据执行加减1，若x小于y，(x,y]范围内的页的首数据调整为上一页的末数据，若x大于y，[y,x)范围内的页的末数据调整为下一页的首数据。
• 查 → 当查找数据总量时，可以通过查找页码表计算得出；当查找序号为n的数据时，可以通过页码表计算得到对应的page和index，然后再通过查找数据表取得数据（由于页码表的数据会经常使用，所以最好从数据库取出一次后保存在内存中再进行使用即可提高速度）。

总结：此方法查找速度和修改速度比较均衡，适合大多数情况使用。

其他方案

手动控制加数值or减数值 +1/-1 +10/-10

按照数值大小排序

和指定 数值 差不多的逻辑