Go llrb 怎样为自定义对象定义有序树比较规则

我第一次把业务对象放进 GoLLRB 时，真正容易出错的不是红黑树本身，而是“什么算相等”没有先定义清楚。GoLLRB 不接收一个独立的比较器；自定义对象要实现 llrb.Item 的 Less(than Item) bool，树再用这套关系完成插入、查找和范围遍历。

最稳妥的做法是把业务排序写成稳定的复合键：先按 Priority，再用唯一的 ID 兜底。这样优先级相同的两个对象仍有确定顺序，Get 和 ReplaceOrInsert 也不会因为比较信息不够而误判。

官方地址：https://pkg.go.dev/github.com/petar/GoLLRB/llrb

把业务对象映射成稳定排序键

这里用一个任务对象举例。优先级越小越靠前，优先级相同时按 ID 的字典序排列。这个顺序既是树的索引，也是“相等”的定义：只有两个字段都相同，才落在同一个排序位置。

用 Less 实现 llrb.Item

GoLLRB 的接口很小，但类型断言和比较完整性必须自己负责。示例使用值类型实现方法，因此插入 Job 值和构造查询键时都能直接满足接口；如果改成指针接收者，就要统一使用 *Job。

package main

import "github.com/petar/GoLLRB/llrb"

type Job struct {
    Priority int
    ID       string
    Payload  string
}

func (a Job) Less(than llrb.Item) bool {
    // 只比较稳定键；Payload 更新不能改变对象在树中的位置。
    b := than.(Job)
    if a.Priority != b.Priority {
        return a.Priority 

这里的 Payload 没有参与比较，所以它可以作为业务内容更新；但 Priority 或 ID 一旦变化，就不是同一个排序键。工程上应先删除旧对象，再按新键重新插入，不能直接修改已经在树里的可变对象。

选择替换还是保留同序对象

GoLLRB 官方 API 把两种需求分开：ReplaceOrInsert 遇到相同排序关系会移除旧对象并返回它；InsertNoReplace 则允许相同排序位置的对象同时存在。前者适合“一个任务 ID 只有一份最新状态”，后者适合允许同键记录共存的场景。

// 相同 Priority + ID 代表同一任务，插入新状态并取得旧值。
old := tree.ReplaceOrInsert(Job{Priority: 10, ID: "compile", Payload: "新描述"})
if old != nil {
    // 旧值可用于记录变更，但这里不把它再次写回树。
    previous := old.(Job)
    _ = previous.Payload
}

// 只有明确需要同序记录时才使用它；否则查询结果会出现多个候选。
tree.InsertNoReplace(Job{Priority: 10, ID: "compile", Payload: "审计副本"})

特别要注意：GoLLRB 判断的不是 Go 的 ==，而是排序关系。若 a.Less(b) 和 b.Less(a) 都为 false，两者就处在同一排序位置。比较函数只看 Priority 时，所有同优先级任务都会撞在一起。

用相同规则完成查询与范围遍历

查询键不必携带完整业务数据，但必须携带 Less 真正使用的字段。下面的键用同样的 Priority + ID 构造；Get 和 Has 才能找到目标，范围查询也才能得到可预期的边界。

// 查询键只填比较字段，Payload 不影响等价判断。
key := Job{Priority: 10, ID: "compile"}
if tree.Has(key) {
    item := tree.Get(key)
    job := item.(Job)
    _ = job.Payload
}

// AscendRange 包含下界，不包含上界；上界键仍按同一规则构造。
lower := Job{Priority: 10, ID: "compile"}
upper := Job{Priority: 20, ID: "test"}
tree.AscendRange(lower, upper, func(item llrb.Item) bool {
    job := item.(Job)
    _ = job.ID
    // 返回 false 可以提前停止遍历；这里返回 true 表示继续。
    return true
})

如果要取“某个优先级的全部任务”，不能只把上下界都写成同一个优先级值，因为 ID 也参与排序。可以使用该优先级下的最小、最大哨兵 ID，或改用明确的分组索引；不要让范围键的写法与 Less 规则脱节。

比较规则的工程边界

第一，Less 应形成稳定、可传递的严格弱序。不要一会儿按时间、一会儿按优先级，也不要把随机数、当前时间或会被后台协程修改的字段放进去。第二，类型断言要和树中的实际类型一致；混入另一种实现后，断言失败会直接触发 panic。

第三，更新排序字段时采用“删除旧键、插入新键”的方式。第四，若业务需要同优先级对象共存，最好在排序键中加入真正唯一的事件 ID，而不是无条件使用 InsertNoReplace 掩盖键设计不足。这样写出来的树才同时具备稳定顺序、可定位查询和可解释的更新语义。

常见问题

为什么自定义结构体实现了 Less 仍然查不到？通常是查询键没有填入 Less 使用的全部字段，导致排序位置不同；先复核复合键，再看插入方法。

ReplaceOrInsert 会按 ID 字段自动判断吗？不会。它只使用你的 Less 结果；ID 只有被写进比较规则，才会参与等价判断。

可以直接修改树中 Job 的 Priority 吗？不建议。修改后对象可能仍挂在旧位置，应先按旧键删除，再按新键插入。