这是一个创建于 653 天前的主题，其中的信息可能已经有所发展或是发生改变。
- 有许多颗不断生长的树 千万级结点，百级的深度
- 某些结点会自身变色导致其子孙节点受影响变为相同的颜色 如 Node2_2 、Node3_2 自身变色 导致其子孙全部跟随变色
- 受父结点影响已经变色过的子孙节点有可能会再度变色，如 Node4_2
- 节点也有可能失色 如 Node2_2 、Node4_2 失色后恢复其原本或继承自上级的颜色
- 请教一下大家，有什么方案能在
快速查询节点颜色的基础上，对变色和失色也有较好的性能
第 1 条附言 · 2023-02-16 18:35:24 +08:00
原谅我没表达清楚，这些节点和颜色属性要持久化保存并支持事务级别(可以非强一致性)的变色&失色操作
 |
1
seawing 2023-02-16 17:10:42 +08:00
树配一个 hash 表？
|
 |
2
MoYi123 2023-02-16 17:16:03 +08:00  2
可以参考 线段树的懒标记 的做法
|
 |
3
zhy0216 2023-02-16 17:29:34 +08:00 via Android
没什么好优化的吧 本来这个查询就只有 log （ n ）的复杂度
|
 |
4
tool2d 2023-02-16 17:30:16 +08:00
可以考虑多根节点。比如 Node3_2 有两个父节点，即属于 Node2_1 ，又属于红色节点。
|
 |
5
JasonLaw 2023-02-16 17:37:10 +08:00 via iPhone
我觉得你应该说明“不同操作发生的次数”，这会影响最佳方案。
|
 |
6
baptismOfTime OP 感谢各位回复，千万级别的节点 需要持久化各个节点的颜色和位置属性，查询操作大概有 3-4k 的 qps ，变色和失色频率比较低，tps 在 20 以内
|
|
7
baptismOfTime OP 棘手的地方在于每次变色和失色要考虑到向根 /子级追溯十几个层级、几万个节点的数据；有没有熟悉 neo4j 的大佬，请教一下在这种场景里把颜色当做边，节点当顶点，查询节点颜色实现为用边查询受关联影响的直接顶点属性，但是节点变色和失色的场景下会进行大量的边修改 这个理论上能否可行？
|
 |
8
airwalkers 2023-02-16 18:37:01 +08:00
节点配一个时间戳，查询节点到跟路径上最新时间戳的颜色
|
|
9
zhy0216 2023-02-16 20:14:37 +08:00
想到一个 O （ log K ） 的办法 K 是节点上有颜色的 node
首先构造 id, id 是这个树在这一层的排序的 index 每多一层 加一个“-” 区分 比如 root 节点是 0 Node2_1 是 0-1 然后用字典树把这个每一层的 id 和颜色记录下来 当查询一个新的 node 的时候 就是查询字典树中的值 （最大前缀） |
 |
10
Maboroshii 2023-02-16 20:26:36 +08:00
给每个节点加一个日志，记录主动变色的历史。 子节点递归查找父节点的日志。 子节点的变色时间在父节点变色时间之前，那么和父节点同色，否则保持自己的颜色？
|
 |
11
wlsnx 2023-02-16 21:00:01 +08:00
用一个 hash 表存到节点的指针，这样就可以快速找到这个节点，然后只有两种情况：节点本身有颜色，返回这个颜色；节点没颜色，向上找第一个有颜色的父节点。增加、删除、移动节点时要同步更新 hash 表。
|
 |
12
Nazz 2023-02-16 21:13:31 +08:00 via Android
更新的时候只更新本节点颜色，记录下操作序列号(单调递增); 获取节点颜色需要递归到根节点，取最大序列号节点的颜色. 更新 O(1), 查找 O(logN)
|
 |
13
robbaa 2023-02-16 21:41:11 +08:00
其实，主要是无限层级遍历问题。
分享 2 个方案，一个是看来的，另外一个算是改进，好不好不好说。 方案一： 每个节点 4 个属性： id：编号 name：名称 parent：父节点编号 left：左子节点排序编号 right：右边子节点排序编号 1. 先构建树 2. 然后按照，先序遍历对每个节点的 left 、right 设值，每次加 1. |
|
14
robbaa 2023-02-16 21:41:23 +08:00
大致如下：
root: 0,25 node2_1:1,18 node3_1:2,3 node3_2:4,15 node4_1:5,8 node5_1:6,7 ndoe4_2:9,14 node5_2:10,11 node5_3:12,13 node3_3:16,17 node2_2:19,22 node3_4:20,21 node2_3:23,24 需求 1：查询某节点下所有节点 select * from nodes where left > {left} and right < {right} 需求 2：查询某元素上级节点 select * from nodes where left < {left} and right > {right} order by left ASC 缺陷代价： 元素的添加与删除，都会导致大量 left 、right 值的更新。 |
|
15
robbaa 2023-02-16 21:41:38 +08:00
方案二：
基于方案一改良，把 left 和 right 的值换成 float 或 double ，不再递增只保证数值增加的。 新增元素，用两侧兄弟元素 right(leftNodeRight)与 left(rightNodeLeft)的值去计算新节点的 left 、right 。 left=(rightNodeLeft-leftNodeRight)/4+leftNodeRight right=rightNodeLeft - (rightNodeLeft-leftNodeRight)/4 计算公式不一定，只要能保证有“足够空间”都可以，定时做好“空间”回收就行。 |
 |
16
aragakiyuii 2023-02-16 23:03:17 +08:00
左右值
|
 |
17
xiangyuecn 2023-02-17 00:46:51 +08:00
你看到的不一定是真的
所以，完全可以作假，前端视觉欺骗，点一下搞个几秒的动画 比如转个 5 秒的圈，夸张点，几百万人同时操作，都在那转圈迷惑一下，服务器将变更收集起来，几秒内只实际计算更新一次，随便搞 |
 |
18
CapNemo 2023-02-17 17:45:41 +08:00
1. 删除颜色操作可以视为染成父节点颜色
2. 指定合适的遍历顺序时，树可以用数组表示 3. 因此应当搜索区间染色问题 |
Select Language