Open isayme opened 5 years ago
假设一个 TODO 应用需要展示一组任务(Task), 任务从属于一个清单(List).
每个清单下的任务展示必然带来一个需求: 排序
简单做法是软件提供多种预定义的排序规则. 比如 按照创建实际降序排; 按照截止时间降序排.
固定排序实现简单, 但不一定符合用户灵活的场景. 自定义排序的能力能够让用户拥有更大的自由度.
为了记录排序信息, 实践中存在几种方案:
// List Item { "tasks": [task1, task3, task2] }
清单上使用数组类型字段记录了任务的顺序.
数据模型通俗易懂. 需要调整顺序时告诉服务端需要放到指定任务之后即可.
这个方案存在几个问题:
tasks
总结: 任何可能导致排序变化的场景都要更新tasks字段; 高并发时很容易导致数据不一致(tasks记录的信息与实际清单下的任务数不一致);
// Task Item { prevTask: task2 // 记录前一个任务信息 }
经典的链表结构. 根据prevTask构建完链表即完成排序.
prevTask
链表的问题是不能断, 在排序变化时需要慎重更新相关任务的prevTask, 避免短链:
之前在知乎上有个简单的介绍: teambition的任务卡排序,数据是怎么存储的? - 知乎
// Task Item { pos: 12345 // 记录任务的相对位置 }
整个排序按照pos值升序.
pos
为了确保在两个任务间插入新任务时有可用的pos取值范围, 期望任意两个相邻任务的pos差值尽可能大, 但又不能太大(最大利用int32/int64取值范围以记录更多的任务排序信息)
缺点:
假设一个 TODO 应用需要展示一组任务(Task), 任务从属于一个清单(List).
每个清单下的任务展示必然带来一个需求: 排序
固定排序
简单做法是软件提供多种预定义的排序规则. 比如 按照创建实际降序排; 按照截止时间降序排.
自定义排序
固定排序实现简单, 但不一定符合用户灵活的场景. 自定义排序的能力能够让用户拥有更大的自由度.
为了记录排序信息, 实践中存在几种方案:
排序信息记录在清单上
清单上使用数组类型字段记录了任务的顺序.
数据模型通俗易懂. 需要调整顺序时告诉服务端需要放到指定任务之后即可.
这个方案存在几个问题:
tasks
字段, 不然就会存在无效数据;tasks
字段, 不然就会无新任务的排序信息;tasks
信息过大; (mongodb 会限制一个 Document 的大小)tasks
字段;tasks
严重依赖与任务, 复制清单的操作必须先复制任务;tasks
数据更新问题(数组更新不够原子atomic)总结: 任何可能导致排序变化的场景都要更新
tasks
字段; 高并发时很容易导致数据不一致(tasks记录的信息与实际清单下的任务数不一致);排序信息记录在任务上: 链表式
经典的链表结构. 根据
prevTask
构建完链表即完成排序.链表的问题是不能断, 在排序变化时需要慎重更新相关任务的
prevTask
, 避免短链:排序信息记录在任务上: 位置信息
之前在知乎上有个简单的介绍: teambition的任务卡排序,数据是怎么存储的? - 知乎
整个排序按照
pos
值升序.为了确保在两个任务间插入新任务时有可用的
pos
取值范围, 期望任意两个相邻任务的pos
差值尽可能大, 但又不能太大(最大利用int32/int64取值范围以记录更多的任务排序信息)缺点:
pos
差值不足以容纳新的任务, 需要重排整个清单, 重排期间的任务写入也会带来风险;