这是一个创建于 858 天前的主题，其中的信息可能已经有所发展或是发生改变。
肝了好几天, 把 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  | 1 kneo 2023 年 12 月 19 日 via Android 为什么用红黑树？很奇怪的选择。 使用红黑树，可以用一次遍历把区间结果都拿出来。但是你需要把遍历的结果都放到一个 buffer 里，并且你的算法需要能访问树的实现（数据结构）。如果你使用的是封装的第三方实现，可能无法高效完成算法。 算法很简单，先从根节点开始遍历，如果根节点在区间内，把根节点放入 buffer ，然后递归左右子树。如果根节点不在区间内，你只需要递归左树或者右树。 buffer 大小设为 limit 的值，buffer 满了就结束。 如果 limit 还要求排序，把节点放入 buffer 前需要先遍历左树。 |
 | 2 Nazz OP |
 | 3 MoYi123 2023 年 12 月 19 日 红黑树查询的时候不是和普通的二叉树是一样的吗? 这个例子来说, 先 lowerbound 找到 3 , 然后调 next 10 次 |
| 6 kneo 2023 年 12 月 19 日 via Android  1 @Nazz 首先要保证 limit 行为的正确性。正常来说是先 order by 再 limit ，而不是先 limit 再 order by （结果不一样）。使用中序（ infix ）可以保证得到的是区间内最小的 N 个。 |
 | 7 cchq 2023 年 12 月 19 日 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()，也就是自己是左节点则不断看自己子节点，如果自己是右节点，自己的父节点及左节点然后不断看左节点的子节点。 |
| 10 cchq 2023 年 12 月 19 日 1 不会漏的，你应该不太了解红黑树的结构。1 楼说的是对的，我算是重复了。稍微改下 166 和 185 行的成 prev()和 next()就好了 |
| 12 Nazz OP |
| 13 cchq 2023 年 12 月 20 日 GetMin 和 GetMax 也有优化空间，一次 push 就够的，只需要看是否还有左/右子节点 |
| 14 Nazz OP @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: } } |
Select Language