V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
SelectLanguage
V2EX  ›  Java

一个非常复杂的需求,如何设计表结构

  •  1
     
  •   SelectLanguage · 2021-03-31 00:51:53 +08:00 · 4777 次点击
    这是一个创建于 463 天前的主题,其中的信息可能已经有所发展或是发生改变。

    某一个类型 A 关系可以表示为一颗树,即 A1 可能有 A2,A3 两个子节点,A2 有 A4,A5,A6 等多个子节点…… 这棵树深度最高大概在 10 左右,整棵树的节点数量在 200W 左右,其中 180W 左右是叶子节点 需求 1: 给定某个节点,能迅速查找出所有子节点,且移动某个子节点到另一个节点下时,所有数据能快速变化 需求 2: 每个叶子节点能生成 0~100 个左右的类型 B,求已知某个 A 的节点后找出 A 下所有的叶子节生成的 B

    关于需求 1:现在的做法因为树的层级不高,所以可以把父节点全部保存,比如某个节点 A100 算出他的父级是 A99,A96,A70,A4 直接存到库中,这样坏处就是移动的时候必须批量大量的修改表,不过目前时间上还是能够满足

    关于需求 2:这个目前难住了,原本的做法是从树中每次先找出一部分叶子节点计算(比如先找 A 的前 10 个叶子节点计算所有的 B,然后再找 11~20 个叶子节点计算所有的 B……),但是现在的需求是 B 要按时间排序,因为之前每次只找了一部分所以排序肯定是不准的,如果想像需求 1 一样记录父级节点,又因为 B 的量级可能是 A 的十倍以上,修改节点的时候会非常慢,所以现在没什么思路了,困扰了好几天,求救

    35 条回复    2021-04-01 11:15:45 +08:00
    liprais
        1
    liprais  
       2021-03-31 01:01:22 +08:00 via iPhone   ❤️ 1
    看起来像是典型的 xy 问题,你用这种数据结构最初是为了解决什么问题?
    gBurnX
        2
    gBurnX  
       2021-03-31 03:59:07 +08:00   ❤️ 2
    1.你这问题说白了,其实是机器性能计算问题。

    需求 1 好做,到叶子结点的全部节点数量才两百多万,目前新 CPU 优化一下计算过程,能做到秒级。

    但需求 2 就不行了。

    先看单次查询,节点数量到了 2kw 级别,全部指令周期估算了一下,已经超过新型主流设备的单机秒级的最大指令周期了,查询规模比 12306 还大。一定要做的话,需要集群 + 需求并行化,然后瓶颈就转移到网络带宽与网络延迟上了。

    网络带宽好解决,延迟没办法解决。


    2.到这还只是单次查询。然后业务需要进一步分解为流水线,来承载更多查询,估算一下 50 台最新高频服务器,每 1.5 秒能承载 70-100 次查询。如果查询量大,还需要成倍地部署这种集群。


    3.到这,还只是查询。现在再考虑修改。如果改少,查多,那么用副本集群,把改与查按 2:8 进行分时处理,加个集群事务,让查询性能降低维持在小于 30%以内。但如果改多,就无解了。除非砸重金,集群加一倍做双缓存,主板用高速数据线直接相连,这样查询性能降低维持在小于 60%以内,但可以让改性能提高至少 1 倍。

    看了一下语言是 Java 。如果改 C++,把运行时检查全关了,内存条按斤买插满,把叶子结点那一层按内存块来存储,直接操作内存块,加上双缓存结构来提高一倍性能(浪费内存条),性能估计还能涨一个小数量级。

    到这里,业务就接近 WOW 了,WOW 每周重启一次集群,一个重要原因也是因为他们没钱烧双缓存 + 那时架构是非云的,只能每周定期重启清空一下内存碎片。

    以上只是用计算器估算一下,不一定准确,可能存在错误。
    MoHen9
        3
    MoHen9  
       2021-03-31 08:07:25 +08:00 via Android
    可以用一个独立字段存储节点的路径,比如 A 的路径为 A,A1 的路径为 A:A1,A2 的路径为 A:A1:A2,以此类推,修改的话也只修改此路径。

    类型的话也单独存个类型字段就好了,值为 A 和 B,如果要查 B,就是类型为 B,且路径前缀为 X:X 的节点。
    SjwNo1
        4
    SjwNo1  
       2021-03-31 08:16:56 +08:00 via iPhone
    典型的类文件系统问题
    optional
        5
    optional  
       2021-03-31 08:44:16 +08:00 via iPhone
    在数据库里保存树,要么级联要么路径,这个需求比较适合存路径
    a1/a2/a3
    需求 1 和需求 2 就变成了路径的前缀匹配和更新
    x66
        6
    x66  
       2021-03-31 09:11:58 +08:00   ❤️ 7
    左右值编码树型数据库设计就是解决这两个问题的。
    https://www.jianshu.com/p/25def7c92ad9
    justfindu
        7
    justfindu  
       2021-03-31 09:14:47 +08:00
    就是 6 楼的方法, 很方便, 但是重建树时候略麻烦. 适合非频繁插入
    redtea
        8
    redtea  
       2021-03-31 09:18:42 +08:00
    SQL Server 有个 hierarchyid 数据类型可以存路径
    SjwNo1
        9
    SjwNo1  
       2021-03-31 09:18:59 +08:00
    左右编码比较合适
    路径 /拼接是不合理的,数据重叠情况下前缀匹配直接拉垮。。。
    x66
        10
    x66  
       2021-03-31 09:19:00 +08:00
    @justfindu 第一次麻烦点,后面有节点插入删除的时候只需要把右边所有节点左右值+-2 就好了,可以封装存储过程
    aguesuka
        11
    aguesuka  
       2021-03-31 09:31:46 +08:00 via Android
    A 是文件夹,B 是文件,需求一是 ls 和 mv,需求二是 find 。
    如果用关系数据库,A,B 分表,A 是闭包表(那么数据量不超过节点数量*深度),B 表外键 A(数据量与 B 数量相同),那么需求二就是 from A join B where A.ancestor = :paran,执行计划是 index scan 和 index join 。

    或者直接上文件系统。
    aguesuka
        12
    aguesuka  
       2021-03-31 09:43:30 +08:00 via Android
    这个问题就在《 sql 反模式》第一章讨论过
    goodjike
        13
    goodjike  
       2021-03-31 09:53:58 +08:00
    这种树型结构可以展开进行存储,利用空间来换取查询时间,应该可行。如树的层级为 10 的话,以下示例:
    goodjike
        14
    goodjike  
       2021-03-31 09:56:10 +08:00
    类型 A:{nodeId: A, level: 0, index:0,othersInfo: ...}, {nodeId: A1, level: 1, index:0,othersInfo: ...}, {nodeId: A2, level: 1, index:1,othersInfo: ...}
    clf
        15
    clf  
       2021-03-31 10:02:46 +08:00
    这需求就和一些数据库的存储结构长得一样。
    yufpga
        16
    yufpga  
       2021-03-31 10:11:10 +08:00
    对使用传统的关系型数据库来说, 需求 2 非常难以实现, 需要自己维护一个 B->A 的映射表(同时还要在表上做 A 的索引),类似于倒排索引, 但如果存在频繁的写入操作, 该表也很难维护.
    其实楼上该说的基本都说了, 文件系统的方案, 实现功能上没啥问题, 至于效果如何, 没用过不知道.

    我的想法比较直接, 其实可以用 ES 这一类方案来处理, 对于每一个节点数据, 我们只要拿两个字段用来分别存储其父节点(我觉得有一个父节点字段有时候会更方便点)和祖先节点, 祖先节点按照固定的规则用逗号或者空格等串成字符串存储就好了. 需求 1 没什么好说的, 需求 2 说白了就是两个条件, 祖先节点包含某个 A 节点, 还有就是按时间排序, 所以就是对祖先节点字段做一个分词搜索,再排个序就好了.

    用这类工具的好处其实只有一个,不需要自己去维护这个倒排索引.
    xuanbg
        17
    xuanbg  
       2021-03-31 10:22:45 +08:00   ❤️ 2
    经典的 id/parentId 已经可以满足需求,子节点需要递归查询。因为层级最多也就 10 来层,递归查询效率还是没问题的。

    还有个办法就是设置一个层级编码,但这个需要对每一层的子节点数量有预期,譬如 010203 这样的编码,每层子节点最多只能 100 个,超过 100 就要 3 位数编码。好处是查询时可以用 code like '#{code}%'作为条件一次查出全部子节点。
    SelectLanguage
        18
    SelectLanguage  
    OP
       2021-03-31 11:18:54 +08:00
    可是这样如果移动一个节点,是不是要修改几百万个数据的值,这样恐怕会很慢
    SelectLanguage
        19
    SelectLanguage  
    OP
       2021-03-31 11:19:15 +08:00
    @x66 可是这样如果移动一个节点,是不是要修改几百万个数据的值,这样恐怕会很慢
    bleepbloop
        20
    bleepbloop  
       2021-03-31 11:43:11 +08:00
    换个思路,用图数据库行不行?
    jorneyr
        21
    jorneyr  
       2021-03-31 12:47:08 +08:00
    可以试试存储路径的前缀,用 like 就可以查询出所有后代
    baibaibaibai
        22
    baibaibaibai  
       2021-03-31 13:07:04 +08:00
    拆分功能点
    hjosama
        23
    hjosama  
       2021-03-31 14:51:51 +08:00
    好复杂的需求呀,完全没有头绪。。。只会根据感觉建表
    liian2019
        24
    liian2019  
       2021-03-31 15:14:01 +08:00
    之前我弄过类似的,但是树没有 10 层这么深。假设每一层的节点都不超过 100 个,顶级节点 A 的 NODE ID=99,那 A 的子节点的 NODE ID 就是 9901,9902 这样递增的,9901 的子节点就是 990101 这样的。然后要查某一个节点的子节点只要 NODE_ID like '99%'。要移动节点的话也只要改一下 NODE_ID
    buliugu
        25
    buliugu  
       2021-03-31 17:23:50 +08:00
    为什么不试试图数据库呢
    luozic
        26
    luozic  
       2021-03-31 17:38:48 +08:00
    这建模有问题否?关系数据库性能大部分都是写少读多。
    dongya
        27
    dongya  
       2021-03-31 17:47:26 +08:00
    看看这种, 不知道你的表会不会炸,https://www.cnblogs.com/wade-luffy/p/7728934.html
    iseki
        28
    iseki  
       2021-03-31 19:23:20 +08:00 via Android
    @x66 “只”😮
    iseki
        29
    iseki  
       2021-03-31 19:29:28 +08:00 via Android
    感觉需求 2 唯一舒服的办法是堆内存了,把带路径的元数据全堆内存里,可即便是这样父级节点修改时依然会有大量修改操作🤔
    kaneg
        30
    kaneg  
       2021-03-31 20:00:37 +08:00 via iPhone
    这不就是文件系统吗?可以研究下主流的文件系统是如何解决这些问题的。
    HankSmash
        31
    HankSmash  
       2021-03-31 23:02:36 +08:00
    可能算是题外话但是看到你这这俩需求,第一反应就是上 Graph DB
    snoopyhai
        32
    snoopyhai  
       2021-04-01 08:21:27 +08:00
    有更专业的, 就不要为难 sql 了, 丢给 neo4j 不好么?
    cassidyhere
        33
    cassidyhere  
       2021-04-01 10:39:30 +08:00
    能用 nosql 吗
    lafuerza
        34
    lafuerza  
       2021-04-01 10:53:48 +08:00
    NewConn
        35
    NewConn  
       2021-04-01 11:15:45 +08:00
    需求 1:
    每个节点都存储父节点主键 parent_id 和节点路径 id_path,使用 start with…connect by…prior 可以将某个节点的所有子节点都查出来;
    难点在修改时,最好使用一个触发器同时修改子节点
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3049 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 00:57 · PVG 08:57 · LAX 17:57 · JFK 20:57
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.