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

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

  •  1
     
  •   SelectLanguage · 244 天前 · 4511 次点击
    这是一个创建于 244 天前的主题,其中的信息可能已经有所发展或是发生改变。

    某一个类型 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   244 天前 via iPhone   ❤️ 1
    看起来像是典型的 xy 问题,你用这种数据结构最初是为了解决什么问题?
    gBurnX
        2
    gBurnX   243 天前   ❤️ 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   243 天前 via Android
    可以用一个独立字段存储节点的路径,比如 A 的路径为 A,A1 的路径为 A:A1,A2 的路径为 A:A1:A2,以此类推,修改的话也只修改此路径。

    类型的话也单独存个类型字段就好了,值为 A 和 B,如果要查 B,就是类型为 B,且路径前缀为 X:X 的节点。
    SjwNo1
        4
    SjwNo1   243 天前 via iPhone
    典型的类文件系统问题
    optional
        5
    optional   243 天前 via iPhone
    在数据库里保存树,要么级联要么路径,这个需求比较适合存路径
    a1/a2/a3
    需求 1 和需求 2 就变成了路径的前缀匹配和更新
    x66
        6
    x66   243 天前   ❤️ 7
    左右值编码树型数据库设计就是解决这两个问题的。
    https://www.jianshu.com/p/25def7c92ad9
    justfindu
        7
    justfindu   243 天前
    就是 6 楼的方法, 很方便, 但是重建树时候略麻烦. 适合非频繁插入
    redtea
        8
    redtea   243 天前
    SQL Server 有个 hierarchyid 数据类型可以存路径
    SjwNo1
        9
    SjwNo1   243 天前
    左右编码比较合适
    路径 /拼接是不合理的,数据重叠情况下前缀匹配直接拉垮。。。
    x66
        10
    x66   243 天前
    @justfindu 第一次麻烦点,后面有节点插入删除的时候只需要把右边所有节点左右值+-2 就好了,可以封装存储过程
    aguesuka
        11
    aguesuka   243 天前 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   243 天前 via Android
    这个问题就在《 sql 反模式》第一章讨论过
    goodjike
        13
    goodjike   243 天前
    这种树型结构可以展开进行存储,利用空间来换取查询时间,应该可行。如树的层级为 10 的话,以下示例:
    goodjike
        14
    goodjike   243 天前
    类型 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   243 天前
    这需求就和一些数据库的存储结构长得一样。
    yufpga
        16
    yufpga   243 天前
    对使用传统的关系型数据库来说, 需求 2 非常难以实现, 需要自己维护一个 B->A 的映射表(同时还要在表上做 A 的索引),类似于倒排索引, 但如果存在频繁的写入操作, 该表也很难维护.
    其实楼上该说的基本都说了, 文件系统的方案, 实现功能上没啥问题, 至于效果如何, 没用过不知道.

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

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

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