Go llrb 插入后修改排序字段为什么会破坏检索

Go llrb 插入对象时，根据 Less 比较结果确定树内位置。若树中保存的是指针，后来直接修改了参与比较的字段，对象会在原位置呈现新的排序值，树却没有自动重新组织。查找仍按当前比较结果选择分支，因此可能绕过实际存放该对象的节点。

解决办法是在对象仍保持旧排序键时删除旧项，再用新键插入；或者把不可变的排序键快照放进树。不能先改键，再指望按旧键删除仍然可靠。

官方项目地址：https://github.com/petar/GoLLRB。包文档：https://pkg.go.dev/github.com/petar/GoLLRB/llrb。下面做一个内存任务索引的原创小示例，说明更新边界；不把代码推演当成本机运行结果。

先给小索引定一条规则：在树内的排序键保持不变

假设需要按任务分数排序，同时按任务ID更新名称和分数。我的设计选择是：分数与ID共同构成排序键，名称只是附带信息。这样两条分数相同、ID不同的任务仍然能在树中区分。

我会把“在树中期间不改变排序关系”写进索引的接口约定，而不是只提醒调用方别乱改字段。原因很具体：树能感知插入和删除，感知不到另一个变量对共享指针字段的普通赋值。

原地修改为何让查找走向错误子树

在一个满足有序约束的树中，某个值可能因小于祖先而位于其左子树。若直接将它改成大于该祖先的值，它仍留在左子树；用新键查找时，比较却可能指向右子树。这里是二叉搜索树约束的逻辑示意，不声称某个插入序列必然产生这一固定拓扑。

GoLLRB 的 Get 实现通过两个方向的 Less 判断走向；两边都不小于时视为排序等价并返回对象。它不是先按指针身份遍历全树寻找地址，因此“我传的是同一根指针”也不能补救被破坏的顺序。

原地改键后不一定每次查询都立即失败，有时对象恰好在比较路径上，问题会暂时隐藏。树的红黑颜色和高度也不能单独证明排序关系依然正确。风险在于有序前提已失效，后续操作不再可靠。

用值快照实现一个可更新的小索引

这个小索引使用值类型 Entry。字段只有整数和字符串，放入树的是值快照；按ID找到旧快照后，在旧键仍有效时删除，再插入新快照。项目应通过已有 Go module 引入上述包，并在自己的依赖管理中固定所用修订。

package main

import (
    "fmt"

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

type Entry struct {
    Score int
    ID    string
    Name  string
}

// Score相同仍按ID区分，避免把不同业务项视为同一个键。
func (e Entry) Less(other llrb.Item) bool {
    x := other.(Entry)
    if e.Score != x.Score {
        return e.Score 

该示例没有运行。读者在自己环境运行时，可以观察新完整键能否取到任务、旧完整键是否不再匹配，以及总条目数是否仍是一条。这里不提供伪造的输出或性能结论。

与共享指针方案相比，值快照使外部普通赋值不容易直接改变树内排序字段。不过，如果以后把排序字段改成指针、切片或其他引用外部可变数据的形式，就要重新审视快照是否真正隔离了比较数据。

集成时把删除、插入和辅助表视为同一次更新

这份代码只处理单线程内存索引，没有持久化、并发锁和故障恢复事务。接入服务时，我会把树、ID辅助表和更新函数封装在同一个组件里，避免调用方只更新其中一个。

若有并发读写，锁要覆盖读取旧项、删除旧键、插入新键和更新辅助表的整体操作，读取也应遵守相同同步约定。只给对象字段加锁，不能保证读者不会看到两次树操作之间的中间状态。

ReplaceOrInsert 会替换排序等价的旧项，但它不是“按业务ID找到任何旧位置再搬迁”的更新接口。示例中ID参与比较，而且辅助表保证每个ID只有一个受控版本；如果另行设计键冲突策略，必须明确替换意味着什么。

我愿意付出的代价是保留一份ID到旧快照的映射，从而让更新有明确旧键。只用排序树省一份辅助表也可以，但调用方就必须可靠持有旧键，并确保所有修改都遵循同一条规则。

已经改坏的树怎样处理，以及常见疑问

如果已经原地修改过树中的排序字段，不应把“保存了旧值，随后按旧值Delete”当成确定恢复方案：节点当前参与比较的字段已经变化，删除本身仍依赖排序关系。更稳妥的恢复方向是从独立的权威数据构建新树，并在受控边界替换旧索引。

只改名称也危险吗？ 示例的 Less 不读取 Name，单纯改变这类非排序数据不会因比较关系变化而产生同一种问题。但实际 Less 若读取名称、外部状态或全局配置，名称或配置就属于排序依赖，也需要保持稳定。

比较相等就是ID相等吗？ 不是。树看到的是 Less 定义的等价关系。若只比较 Score，同分任务在排序上等价；业务上需要多条任务时，应明确增加稳定的区分字段，或另行选择重复项语义。

重新插入同一个已改键指针能修好吗？ 不应这样做。旧位置未必被移除，结构可能已经失序；重复插入还可能让同一指针出现在多个位置。先预防原地改键，比事后依赖偶然的查询路径更可靠。

参考：GoLLRB 接口文档；GoLLRB 查找与更新实现。