V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
MySQL 5.5 Community Server
MySQL 5.6 Community Server
Percona Configuration Wizard
XtraBackup 搭建主从复制
Great Sites on MySQL
Percona
MySQL Performance Blog
Severalnines
推荐管理工具
Sequel Pro
phpMyAdmin
推荐书目
MySQL Cookbook
MySQL 相关项目
MariaDB
Drizzle
参考文档
http://mysql-python.sourceforge.net/MySQLdb.html
phony2r
V2EX  ›  MySQL

MySQL 如何保存有顺序的列表?

  •  
  •   phony2r · 2021-05-24 12:44:08 +08:00 · 4061 次点击
    这是一个创建于 1264 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有一个表表示一个列表的每一小项 id/name/order, 其中 order 表示小项在列表中的顺序

    现在这个列表是可以拖动进行排序的, 这样的话每次排序都会产生大量的 order 变化, 比如 1 移到 4, 就会产生 2->1 / 3->2 / 4->3 / 1->4 一共 4 个 order 变化

    类似的, 加入 1 移到 100 的话就会产生 100 个 order 变化

    如果批量更新的话, MySQL 的性能是个问题, 而且也无法保证原子性(部分更新 order 成功部分失败)

    像这种带顺序的列表应该怎么设计?

    23 条回复    2021-05-25 16:15:04 +08:00
    wangritian
        1
    wangritian  
       2021-05-24 13:00:45 +08:00
    我会选择全量更新,一个 varchar 字段保存整个列表的表头,用 json 数组或逗号隔开
    renmu123
        2
    renmu123  
       2021-05-24 13:02:56 +08:00 via Android
    设计 order 为 0,10000,20000 如果有变化,就设置 order 为前后两个 order 的一半
    yeqizhang
        3
    yeqizhang  
       2021-05-24 13:06:15 +08:00 via Android
    放一个事务里没有你说的原子性问题。

    你从 1 拖到 100 拖到很长了,大量数据要求拖拽排序的业务场景很难想象是什么,像信息流之类的不如给个权重设置。

    有请后面大佬给出方案
    phony2r
        4
    phony2r  
    OP
       2021-05-24 13:10:30 +08:00
    @wangritian 没理解
    phony2r
        5
    phony2r  
    OP
       2021-05-24 13:11:00 +08:00
    @renmu123 这样设计的话更新次数有限制 达到一定次数就失效了
    phony2r
        6
    phony2r  
    OP
       2021-05-24 13:12:09 +08:00
    @yeqizhang 比如歌单里面音乐的顺序
    SorcererXW
        7
    SorcererXW  
       2021-05-24 13:14:03 +08:00   ❤️ 3
    可以用联合索引( order + last_order_timestamp )排序

    1->4 的话, 就把 1 的 order 字段更新为 4, last_order_timestamp 设置为当前时间戳
    排序的时候优先按 order 升序, 再按 last_order_timestamp 降序排

    这样每次更新只需要更新一行
    renmu123
        8
    renmu123  
       2021-05-24 13:18:50 +08:00 via Android
    @phony2r 为什么会失效?小数点也可以比大小啊
    timethinker
        9
    timethinker  
       2021-05-24 13:21:16 +08:00
    取决于是读多还是写多,另外跟数据量也有关系,假如说按照最坏的情况,修改序列会导致上 W 条的记录被修改,那么单独维护一张表存储序列是一个不错的方案,里面的内容是一个字符串,用分隔符组装 ID 列表,这样在变更序列的时候仅需要修改这一条数据(一对多,这里序列表 ID 就是主表的 ID,比如歌单 ID,评论文章 ID,小说 ID 等等)。

    不过在读取的时候可能会遇到条件过滤+分页的问题,还是取决于场景,可以在更新序列表后异步的更新表数据( order ),此时数据表上的 order 字段只是一个冗余,在修改过后可能会遇到延迟的情况,在关键的地方还是要从序列表当中取出正确的排序,不过大多数情况下是可以接受的。
    yeqizhang
        10
    yeqizhang  
       2021-05-24 13:27:01 +08:00 via Android
    我想了下,觉得全量没毛病的,其实全量也是更新一个区间的数据,具体多少就是拖拽了多少个位置,性能上问题也不是很大,限制一下一次最多能拖多长就行
    lujjjh
        11
    lujjjh  
       2021-05-24 13:28:29 +08:00
    https://www.zhihu.com/question/55789722/answer/146650607

    teambition 是类似 #2 的做法,但是有极小概率会 fallback 到 slow path (整个分组任务重算)。
    jorneyr
        12
    jorneyr  
       2021-05-24 13:29:23 +08:00
    我们是用浮点数表示顺序 (初始赋值为创建时候的时间戳),2 个浮点数求平均值就可以了。
    est
        13
    est  
       2021-05-24 13:33:50 +08:00
    > 现在这个列表是可以拖动进行排序的, 这样的话每次排序都会产生大量的 order 变化, 比如 1 移到 4, 就会产生 2->1 / 3->2 / 4->3 / 1->4 一共 4 个 order 变化


    保存为 float 。23333

    1 2 3 4 把 1 移动到 4,改成
    2 3 4 4.1
    tairan2006
        14
    tairan2006  
       2021-05-24 13:35:07 +08:00   ❤️ 1
    如果列表很小的话:设 order 是一个 bigint 字段,前端传入 front 节点,令拖动节点 order=front+1,并 update 所有 order>front 的 order=order+1

    如果列表比较大:设 order 是一个 decimal 字段,插入时两个间隔大一点,拖动后取 order=(front+after)/2 。日取其半,万世不竭(才怪,会达到精度上限)
    yeqizhang
        15
    yeqizhang  
       2021-05-24 13:35:52 +08:00 via Android
    @est 太大了,拖不了几次,得是 4.0000001🐶
    NULL2020
        16
    NULL2020  
       2021-05-24 14:03:29 +08:00
    改用 redis list,前端每次更新都全量发过来,后端直接保存就行了
    neoblackcap
        17
    neoblackcap  
       2021-05-24 14:13:29 +08:00
    实际上这需求我觉得传统的关系型数据库不好搞。你用一个内存数据库作为缓存层,定时将结果全量同步回数据库就可以了。
    no1xsyzy
        18
    no1xsyzy  
       2021-05-24 14:24:33 +08:00   ❤️ 1
    @SorcererXW 时间这个想法很好,但想到一个问题(以下表示为 元素=(order, time))
    a=(1,0) b=(2,0) c=(3,0) d=(4,0)
    d 移到 ab 之间
    a=(1,0) d=(2,1) b=(2,0) c=(3,0)
    然后尝试 c 移到 db 之间,那样就无法正确找到这个间隔了。
    love
        19
    love  
       2021-05-24 15:36:28 +08:00   ❤️ 1
    有一个方法很好用,就是另建一个表保存列表顺序,就一个 varchar 字段,里面是那个有序列表的 id 列表,用逗号分隔
    这样只要保存一条记录就可
    akira
        20
    akira  
       2021-05-25 03:14:19 +08:00
    对连续的数据进行位置调整,要变动最小的话,那可以考虑链表呀。

    例如 表结构改为 id/name/pre-id ,这样你每次调整排序,最多只需要改 2 个数了。
    cwang22
        21
    cwang22  
       2021-05-25 07:28:36 +08:00
    数据可以试试 Jira 排序 ticket 的做法 LexoRank

    排序 key 的格式大概是`2|i019qh`,更新读取都是 O(1),后台任务定期 rebalance


    https://tmcalm.nl/blog/lexorank-jira-ranking-system-explained/
    crclz
        22
    crclz  
       2021-05-25 11:29:04 +08:00
    使用 mysql 的 json 类型。
    CEBBCAT
        23
    CEBBCAT  
       2021-05-25 16:15:04 +08:00
    @crclz #22 可以仔细讲讲吗?没听懂
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2333 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 15:56 · PVG 23:56 · LAX 07:56 · JFK 10:56
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.