Golang Go语言中怎么优化红黑树区间查询

发布于 1周前 作者 songsunli 来自 Go语言

肝了好几天, 把 nginx 红黑树移植了过来. 但是我拓展的区间查询方法有点慢.

慢的原因主要是每次只能查出来一个结果, 需要拿上一次的结果进行比较, 如果 limit 10 相当于调用了 10 次查询. 有什么优化办法吗?

仓库地址: https://github.com/lxzan/dao

package main

import (
“github.com/lxzan/dao”
“github.com/lxzan/dao/rbtree”
)


func main() {
var tree = rbtree.Newint, struct{}
for i := 0; i < 10; i++ {
tree.Set(i, struct{}{})
}


var results = tree.
   NewQuery().
   Left(func(key int) bool { return key &gt;= 3 }).
   Right(func(key int) bool { return key &lt;= 5 }).
   Limit(10).
   Order(dao.DESC).
   Do()
for _, item := range results {
   println(item.Key)
}

}


10,000 elements

BenchmarkRBTree_Set-12                       540           219 ns/op          720051 B/op      20001 allocs/op
BenchmarkRBTree_Get-12                      3272            36 ns/op               0 B/op          0 allocs/op
BenchmarkRBTree_Query-12                      60          1809 ns/op         3680048 B/op      60000 allocs/op

Golang Go语言中怎么优化红黑树区间查询

更多关于Golang Go语言中怎么优化红黑树区间查询的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html

Harmonyos Next教程
15 回复

为什么用红黑树？很奇怪的选择。

使用红黑树，可以用一次遍历把区间结果都拿出来。但是你需要把遍历的结果都放到一个 buffer 里，并且你的算法需要能访问树的实现（数据结构）。如果你使用的是封装的第三方实现，可能无法高效完成算法。

算法很简单，先从根节点开始遍历，如果根节点在区间内，把根节点放入 buffer ，然后递归左右子树。如果根节点不在区间内，你只需要递归左树或者右树。
buffer 大小设为 limit 的值，buffer 满了就结束。
如果 limit 还要求排序，把节点放入 buffer 前需要先遍历左树。

更多关于Golang Go语言中怎么优化红黑树区间查询的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html




> 为什么用红黑树

因为我在给红黑树加 feature

如果符合条件的结果非常多，全查出来会非常慢

一个一个地查虽然慢，但耗时非常稳定

红黑树查询的时候不是和普通的二叉树是一样的吗?
这个例子来说, 先 lowerbound 找到 3 , 然后调 next 10 次

如果条件范围比较小，全部查出来再排序是个好办法

调用次数多了会很慢，大量重复计算

首先要保证 limit 行为的正确性。正常来说是先 order by 再 limit ，而不是先 limit 再 order by （结果不一样）。使用中序（ infix ）可以保证得到的是区间内最小的 N 个。

https://github.com/lxzan/dao/blob/11c5d6a2378c27926008752ba04fdef9ebb7f948/rbtree/query.go#L158C3-L158C9
以及 https://github.com/lxzan/dao/blob/11c5d6a2378c27926008752ba04fdef9ebb7f948/rbtree/query.go#L177

已经得到一个节点了，就不要在后续还去 for 遍历一个一个查找了，直接如果找后续比自己大的，则 next()，也就是如果自身是左节点，不断得到父节点以及右节点及右节点的子节点，如果自身是右节点，则不断看自己子节点；

如果找比自己小的，则 prev()，也就是自己是左节点则不断看自己子节点，如果自己是右节点，自己的父节点及左节点然后不断看左节点的子节点。

不从根节点开始找的话，可能会漏掉一些数据，有排序的

ok ，我先去了解一下中序遍历的特性

不会漏的，你应该不太了解红黑树的结构。1 楼说的是对的，我算是重复了。稍微改下 166 和 185 行的成 prev()和 next()就好了

只了解最基本的性质。左子结点比父节点小，右子结点比父节点大



感谢二位, 已经搞定了
在我现有逻辑上稍微改下就行了, 利用中序遍历一次得到多个结果, 减少重复计算. 原来 LIMIT N 要查 N 次, 现在最坏才是 N 次.

GetMin 和 GetMax 也有优化空间，一次 push 就够的，只需要看是否还有左/右子节点

一个递归方法搞定, 从 1809 ns/op 提高到了 883 ns/op

// 降序遍历 中序遍历是有序的
func (c *RBTree[K, V]) rangeDesc(curNode *rbtree_node[K, V], qb *QueryBuilder[K, V]) {
if c.end(curNode) || len(qb.results) >= qb.limit {
return
}

state := 0
if qb.rightFilter(curNode.data.Key) {
state += 1
}
if qb.leftFilter(curNode.data.Key) {
state += 2
}

switch state {
case 3:
c.rangeDesc(curNode.right, qb)
if len(qb.results) < qb.limit {
qb.results = append(qb.results, *curNode.data)
} else {
return
}
c.rangeDesc(curNode.left, qb)
case 2:
c.rangeDesc(curNode.left, qb)
case 1:
c.rangeDesc(curNode.right, qb)
default:
}
}

在Golang中优化红黑树的区间查询，可以从以下几个方面着手：

  1. 平衡性维护：红黑树本身是一种自平衡二叉搜索树，通过旋转和重新着色操作保持O(log n)的高度，从而确保基本的查询、插入和删除操作效率。保持树的平衡是优化区间查询的基础。

  2. 区间分解：在进行区间查询时，可以通过分解查询区间为两个端点查询（如查找大于等于左端点的最小节点和小于等于右端点的最大节点），然后遍历这两个节点之间的所有节点。通过维护辅助信息（如子树大小），可以加速这一过程。

  3. 增量式更新：如果区间查询涉及频繁的数据更新（插入、删除），可以考虑使用增量式算法来更新红黑树的状态，避免不必要的全局重构，从而提高效率。

  4. 内存管理：优化内存分配和释放策略，减少GC（垃圾回收）带来的性能开销。在Go中，使用sync.Pool等机制可以有效复用内存对象。

  5. 并发控制：对于多线程环境下的红黑树操作，使用Go的并发原语（如sync.Mutex或sync.RWMutex）来控制对树的并发访问，但要小心避免死锁和数据竞争。

  6. 算法优化：根据具体应用场景，探索是否有更高效的替代数据结构（如AVL树、B树等）或算法来实现区间查询。

通过上述方法，可以在Go语言中有效地优化红黑树的区间查询性能。

回到顶部