未分類
2 4 月 2021

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

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

資深大佬 : SelectLanguage 0

某一个类型 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)

  • 資深大佬 : liprais

    看起来像是典型的 xy 问题，你用这种数据结构最初是为了解决什么问题？

  • 資深大佬 : gBurnX

    1.你这问题说白了，其实是机器性能计算问题。

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

    但需求 2 就不行了。

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

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

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

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

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

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

    以上只是用计算器估算一下，不一定准确，可能存在错误。

  • 資深大佬 : MoHen9

    可以用一个独立字段存储节点的路径，比如 A 的路径为 A，A1 的路径为 A:A1，A2 的路径为 A:A1:A2，以此类推，修改的话也只修改此路径。

    类型的话也单独存个类型字段就好了，值为 A 和 B，如果要查 B，就是类型为 B，且路径前缀为 X:X 的节点。

  • 資深大佬 : SjwNo1

    典型的类文件系统问题

  • 資深大佬 : optional

    在数据库里保存树，要么级联要么路径，这个需求比较适合存路径
    a1/a2/a3
    需求 1 和需求 2 就变成了路径的前缀匹配和更新

  • 資深大佬 : x66

    左右值编码树型数据库设计就是解决这两个问题的。
    https://www.jianshu.com/p/25def7c92ad9

  • 資深大佬 : justfindu

    就是 6 的方法, 很方便, 但是重建树时候略麻烦. 适合非频繁插入

  • 資深大佬 : redtea

    SQL Server 有个 hierarchyid 数据类型可以存路径

  • 資深大佬 : SjwNo1

    左右编码比较合适
    路径 /拼接是不合理的，数据重叠情况下前缀匹配直接拉垮。。。

  • 資深大佬 : x66

    @justfindu 第一次麻烦点，后面有节点插入删除的时候只需要把右边所有节点左右值+-2 就好了，可以封装存储过程

  • 資深大佬 : aguesuka

    A 是文件夹，B 是文件，需求一是 ls 和 mv，需求二是 find 。
    如果用关系数据库，A,B 分表，A 是闭包表(那么数据量不超过节点数量*深度)，B 表外键 A(数据量与 B 数量相同)，那么需求二就是 from A join B where A.ancestor = :paran，执行计划是 index scan 和 index join 。

    或者直接上文件系统。

  • 資深大佬 : aguesuka

    这个问题就在《 sql 反模式》第一章讨论过

  • 資深大佬 : goodjike

    这种树型结构可以展开进行存储，利用空间来换取查询时间，应该可行。如树的层级为 10 的话，以下示例：

  • 資深大佬 : goodjike

    类型 A：{nodeId: A, level: 0, index:0,othersInfo: …}, {nodeId: A1, level: 1, index:0,othersInfo: …}, {nodeId: A2, level: 1, index:1,othersInfo: …}

  • 資深大佬 : lychs1998

    这需求就和一些数据库的存储结构长得一样。

  • 資深大佬 : yufpga

    对使用传统的关系型数据库来说, 需求 2 非常难以实现, 需要自己维护一个 B->A 的映射表(同时还要在表上做 A 的索引)，类似于倒排索引, 但如果存在频繁的写入操作, 该表也很难维护.
    其实上该说的基本都说了, 文件系统的方案, 实现功能上没啥问题, 至于效果如何, 没用过不知道.

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

    用这类工具的好处其实只有一个，不需要自己去维护这个倒排索引.

  • 資深大佬 : xuanbg

    经典的 id/parentId 已经可以满足需求，子节点需要递归查询。因为层级最多也就 10 来层，递归查询效率还是没问题的。

    还有个办法就是设置一个层级编码，但这个需要对每一层的子节点数量有预期，譬如 010203 这样的编码，每层子节点最多只能 100 个，超过 100 就要 3 位数编码。好处是查询时可以用 code like ‘#{code}%’作为条件一次查出全部子节点。

  • 主 資深大佬 : SelectLanguage

    可是这样如果移动一个节点，是不是要修改几百万个数据的值，这样恐怕会很慢

  • 主 資深大佬 : SelectLanguage

    @x66 可是这样如果移动一个节点，是不是要修改几百万个数据的值，这样恐怕会很慢

  • 資深大佬 : bleepbloop

    换个思路，用图数据库行不行？

  • 資深大佬 : jorneyr

    可以试试存储路径的前缀，用 like 就可以查询出所有后代

  • 資深大佬 : baibaibaibai

    拆分功能点

  • 資深大佬 : hjosama

    好复杂的需求呀，完全没有头绪。。。只会根据感觉建表

  • 資深大佬 : liian2019

    之前我弄过类似的，但是树没有 10 层这么深。假设每一层的节点都不超过 100 个，顶级节点 A 的 NODE ID=99，那 A 的子节点的 NODE ID 就是 9901，9902 这样递增的,9901 的子节点就是 990101 这样的。然后要查某一个节点的子节点只要 NODE_ID like ‘99%’。要移动节点的话也只要改一下 NODE_ID

  • 資深大佬 : buliugu

    为什么不试试图数据库呢

  • 資深大佬 : luozic

    这建模有问题否？关系数据库性能大部分都是写少读多。

  • 資深大佬 : dongya

    看看这种， 不知道你的表会不会炸，https://www.cnblogs.com/wade-luffy/p/7728934.html

  • 資深大佬 : iseki

    @x66 “只”

  • 資深大佬 : iseki

    感觉需求 2 唯一舒服的办法是堆内存了，把带路径的元数据全堆内存里，可即便是这样父级节点修改时依然会有大量修改操作

  • 資深大佬 : kaneg

    这不就是文件系统吗？可以研究下主流的文件系统是如何解决这些问题的。

  • 資深大佬 : HankSmash

    可能算是题外话但是看到你这这俩需求，第一反应就是上 Graph DB

  • 資深大佬 : snoopyhai

    有更专业的, 就不要为难 sql 了, 丢给 neo4j 不好么?

  • 資深大佬 : cassidyhere

    能用 nosql 吗

  • 資深大佬 : lafuerza

    请用 PostgreSQL ltree： https://www.postgresql.org/docs/13/ltree.html

  • 資深大佬 : NewConn

    需求 1：
    每个节点都存储父节点主键 parent_id 和节点路径 id_path，使用 start with…connect by…prior 可以将某个节点的所有子节点都查出来；
    难点在修改时，最好使用一个触发器同时修改子节点