怎么优化红黑树区间查询

[Nazz]

肝了好几天, 把 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.New[int, struct{}]()
    for i := 0; i < 10; i++ {
       tree.Set(i, struct{}{})
    }

    var results = tree.
       NewQuery().
       Left(func(key int) bool { return key >= 3 }).
       Right(func(key int) bool { return key <= 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

[kneo]

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

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

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

[Nazz]

@kneo

> 为什么用红黑树

因为我在给红黑树加 feature

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

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

[MoYi123]

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

[Nazz]

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

[Nazz]

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

[kneo]

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

[cchq]

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()，也就是自己是左节点则不断看自己子节点，如果自己是右节点，自己的父节点及左节点然后不断看左节点的子节点。

[Nazz]

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

[Nazz]

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

[cchq]

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

[Nazz]

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

[Nazz]

@kneo @cchq

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

[cchq]

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

[Nazz]

@cchq 一个递归方法搞定, 从 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:
}
}