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

[SelectLanguage]

某一个类型 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 的十倍以上，修改节点的时候会非常慢，所以现在没什么思路了，困扰了好几天，求救

[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: ...}

[clf]

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

[yufpga]

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

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

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

[xuanbg]

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

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

[SelectLanguage]

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

[SelectLanguage]

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

[bleepbloop]

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