这是一个创建于 1344 天前的主题，其中的信息可能已经有所发展或是发生改变。
某一个类型 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 的十倍以上，修改节点的时候会非常慢，所以现在没什么思路了，困扰了好几天，求救
 |
1
liprais 2021-03-31 01:01:22 +08:00 via iPhone  1
看起来像是典型的 xy 问题，你用这种数据结构最初是为了解决什么问题？
|
 |
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 每周重启一次集群，一个重要原因也是因为他们没钱烧双缓存 + 那时架构是非云的，只能每周定期重启清空一下内存碎片。 以上只是用计算器估算一下，不一定准确，可能存在错误。 |
 |
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 的节点。 |
 |
4
SjwNo1 2021-03-31 08:16:56 +08:00 via iPhone
典型的类文件系统问题
|
 |
5
optional 2021-03-31 08:44:16 +08:00 via iPhone
在数据库里保存树，要么级联要么路径，这个需求比较适合存路径
a1/a2/a3 需求 1 和需求 2 就变成了路径的前缀匹配和更新 |
 |
6
x66 2021-03-31 09:11:58 +08:00 7
左右值编码树型数据库设计就是解决这两个问题的。
https://www.jianshu.com/p/25def7c92ad9 |
 |
7
justfindu 2021-03-31 09:14:47 +08:00
就是 6 楼的方法, 很方便, 但是重建树时候略麻烦. 适合非频繁插入
|
 |
8
redtea 2021-03-31 09:18:42 +08:00
SQL Server 有个 hierarchyid 数据类型可以存路径
|
|
9
SjwNo1 2021-03-31 09:18:59 +08:00
左右编码比较合适
路径 /拼接是不合理的，数据重叠情况下前缀匹配直接拉垮。。。 |
 |
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 。 或者直接上文件系统。 |
|
12
aguesuka 2021-03-31 09:43:30 +08:00 via Android
这个问题就在《 sql 反模式》第一章讨论过
|
 |
13
goodjike 2021-03-31 09:53:58 +08:00
这种树型结构可以展开进行存储，利用空间来换取查询时间，应该可行。如树的层级为 10 的话，以下示例：
|
|
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: ...}
|
 |
15
clf 2021-03-31 10:02:46 +08:00
这需求就和一些数据库的存储结构长得一样。
|
 |
16
yufpga 2021-03-31 10:11:10 +08:00
对使用传统的关系型数据库来说, 需求 2 非常难以实现, 需要自己维护一个 B->A 的映射表(同时还要在表上做 A 的索引)，类似于倒排索引, 但如果存在频繁的写入操作, 该表也很难维护.
其实楼上该说的基本都说了, 文件系统的方案, 实现功能上没啥问题, 至于效果如何, 没用过不知道. 我的想法比较直接, 其实可以用 ES 这一类方案来处理, 对于每一个节点数据, 我们只要拿两个字段用来分别存储其父节点(我觉得有一个父节点字段有时候会更方便点)和祖先节点, 祖先节点按照固定的规则用逗号或者空格等串成字符串存储就好了. 需求 1 没什么好说的, 需求 2 说白了就是两个条件, 祖先节点包含某个 A 节点, 还有就是按时间排序, 所以就是对祖先节点字段做一个分词搜索，再排个序就好了. 用这类工具的好处其实只有一个，不需要自己去维护这个倒排索引. |
 |
17
xuanbg 2021-03-31 10:22:45 +08:00 2
经典的 id/parentId 已经可以满足需求，子节点需要递归查询。因为层级最多也就 10 来层，递归查询效率还是没问题的。
还有个办法就是设置一个层级编码，但这个需要对每一层的子节点数量有预期，譬如 010203 这样的编码，每层子节点最多只能 100 个，超过 100 就要 3 位数编码。好处是查询时可以用 code like '#{code}%'作为条件一次查出全部子节点。 |
 |
18
SelectLanguage OP 可是这样如果移动一个节点，是不是要修改几百万个数据的值，这样恐怕会很慢
|
|
19
SelectLanguage OP @x66 可是这样如果移动一个节点，是不是要修改几百万个数据的值，这样恐怕会很慢
|
 |
20
bleepbloop 2021-03-31 11:43:11 +08:00
换个思路，用图数据库行不行？
|
 |
21
jorneyr 2021-03-31 12:47:08 +08:00
可以试试存储路径的前缀，用 like 就可以查询出所有后代
|
 |
22
baibaibaibai 2021-03-31 13:07:04 +08:00
拆分功能点
|
 |
23
hjosama 2021-03-31 14:51:51 +08:00
好复杂的需求呀，完全没有头绪。。。只会根据感觉建表
|
 |
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
|
 |
25
buliugu 2021-03-31 17:23:50 +08:00
为什么不试试图数据库呢
|
 |
26
luozic 2021-03-31 17:38:48 +08:00
这建模有问题否？关系数据库性能大部分都是写少读多。
|
 |
27
dongya 2021-03-31 17:47:26 +08:00
看看这种， 不知道你的表会不会炸，https://www.cnblogs.com/wade-luffy/p/7728934.html
|
 |
29
iseki 2021-03-31 19:29:28 +08:00 via Android
感觉需求 2 唯一舒服的办法是堆内存了，把带路径的元数据全堆内存里，可即便是这样父级节点修改时依然会有大量修改操作🤔
|
 |
30
kaneg 2021-03-31 20:00:37 +08:00 via iPhone
这不就是文件系统吗？可以研究下主流的文件系统是如何解决这些问题的。
|
 |
31
HankSmash 2021-03-31 23:02:36 +08:00
可能算是题外话但是看到你这这俩需求，第一反应就是上 Graph DB
|
 |
32
snoopyhai 2021-04-01 08:21:27 +08:00
有更专业的, 就不要为难 sql 了, 丢给 neo4j 不好么?
|
 |
33
cassidyhere 2021-04-01 10:39:30 +08:00
能用 nosql 吗
|
 |
34
lafuerza 2021-04-01 10:53:48 +08:00
请用 PostgreSQL ltree： https://www.postgresql.org/docs/13/ltree.html
|
 |
35
NewConn 2021-04-01 11:15:45 +08:00
需求 1：
每个节点都存储父节点主键 parent_id 和节点路径 id_path，使用 start with…connect by…prior 可以将某个节点的所有子节点都查出来； 难点在修改时，最好使用一个触发器同时修改子节点 |
Select Language