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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

For Existing Member Sign In

This topic created in 1861 days ago, the information mentioned may be changed or developed.

某一个类型 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 replies • 2021-04-01 11:15:45 +08:00

F281M6Dh8DXpD1g2

Mar 31, 2021 via iPhone

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

gBurnX

Mar 31, 2021

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

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

但需求 2 就不行了。

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

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

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

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

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

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

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

MoHen9

Mar 31, 2021 via Android

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

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

SjwNo1

Mar 31, 2021 via iPhone

典型的类文件系统问题

optional

Mar 31, 2021 via iPhone

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

x66

Mar 31, 2021

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

justfindu

Mar 31, 2021

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

redtea

Mar 31, 2021

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

SjwNo1

Mar 31, 2021

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

x66

Mar 31, 2021

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

aguesuka

Mar 31, 2021 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

Mar 31, 2021 via Android

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

goodjike

Mar 31, 2021

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

goodjike

Mar 31, 2021

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

clf

Mar 31, 2021

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

yufpga

Mar 31, 2021

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

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

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

xuanbg

Mar 31, 2021

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

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

SelectLanguage

Mar 31, 2021

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

SelectLanguage

Mar 31, 2021

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

bleepbloop

Mar 31, 2021

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

jorneyr

Mar 31, 2021

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

baibaibaibai

Mar 31, 2021

拆分功能点

hjosama

Mar 31, 2021

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

liian2019

Mar 31, 2021

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