Go iter.Seq2 怎么为树形索引暴露键值遍历

树形索引要对外提供遍历时，最容易先写成“递归收集到切片再返回”。这样做能用，但会复制全部键值，还会把“只看前几项”的请求变成完整遍历。Go 1.23 的 iter.Seq2[K, V] 更贴合这个接口：让 All() 返回一个键值序列，调用方直接用 for key, value := range index.All() 消费；一旦 break，递归 walker 立即停止。

实现时真正要盯住的不是泛型签名，而是停止信号：每次调用 yield(key, value) 都要检查布尔返回值，并把 false 从当前节点一路返回到根节点。否则调用方虽然写了 break，树的其余分支仍可能继续被访问。

原来的接口为什么不够顺手

假设索引内部是二叉搜索树，节点保存 key、value、left 和 right。对外暴露遍历通常有三种做法：

树形索引的公共 API 通常只需要暴露键值对，不应该让调用方看到 node{key,value} 这类内部节点。iter.Seq2[K, V] 的定义正是一个接收 yield(K, V) bool 的函数，约定每个序列元素产生两个值，常用于 key-value 或 index-value。

把内部节点换成 Seq2 API

下面先只定义节点、树和 All()。键类型没有出现在遍历比较中，因此这个方法本身不需要额外的有序约束；插入逻辑可以在树的其他方法中按实际索引规则处理。

package treeindex

import "iter"

type node[K, V any] struct {
    key         K
    value       V
    left, right *node[K, V]
}

type Tree[K, V any] struct {
    root *node[K, V]
}

// All 按中序关系暴露键值对，不把内部节点交给调用方。
func (t *Tree[K, V]) All() iter.Seq2[K, V] {
    return func(yield func(K, V) bool) {
        var walk func(*node[K, V]) bool

        walk = func(n *node[K, V]) bool {
            // 空分支没有元素，返回 true 表示仍可继续遍历。
            if n == nil {
                return true
            }

            // 左子树若收到停止信号，当前节点和右子树都不再访问。
            if !walk(n.left) {
                return false
            }

            // yield 返回 false，说明 range 已 break 或调用方要求停止。
            if !yield(n.key, n.value) {
                return false
            }

            // 右子树的停止结果继续向父节点传播。
            return walk(n.right)
        }

        // 顶层无需使用返回值；false 已经让所有递归层退出。
        walk(t.root)
    }
}

这里的遍历顺序是“左子树—当前节点—右子树”。如果插入逻辑始终维持左侧 key 小于当前 key、右侧 key 大于当前 key 的搜索树不变量，那么 All() 会按 key 的升序产生元素；如果内部只是普通二叉树，它只保证中序关系，不应在文档里声称有序。

让 break 真正停止整棵树

我第一次检查这类代码时，最容易漏掉的是递归函数的返回值。只在当前节点写 if !yield(...) { return } 还不够，因为包裹它的父级 walker 必须知道子树已经停止。让 walker 返回 bool，可以把 yield=false 转换为 walker=false，再逐层退出。

可以用下面三个检查点快速判断实现是否正确：

• 递归访问左子树后，是否检查了返回值；
• 调用 yield(k, v) 后，是否在 false 时立即返回；
• 访问右子树时，是否把它的 bool 结果原样返回给父级。

官方 iter 文档还明确规定：yield 返回 false 后，迭代器必须停止；如果之后再次调用这个 yield，会触发 panic。因此“收到 false 后继续扫描，只是不再处理结果”也不符合协议。

调用方可以直接 range，也可以 Pull2

最自然的消费方式是 range over function。调用方不需要知道树的节点类型，遇到目标后直接 break：

package main

import "fmt"

func printFirstThree(index interface {
    All() func(func(string, int) bool)
}) {
    count := 0
    for key, value := range index.All() {
        // 调用方只接收公开的键和值，不接触树节点。
        fmt.Println(key, value)
        count++
        if count == 3 {
            // break 会让底层 yield 返回 false。
            break
        }
    }
}

示例中的函数类型与 iter.Seq2[string, int] 的底层类型一致；在真实 API 中，建议直接写明确的 iter.Seq2[K, V]，可读性更好，也方便与标准迭代器适配。

如果业务不是循环消费，而是一次拉取一个键值对，可以使用 iter.Pull2。提前结束时必须调用 stop，惯用写法是立即 defer stop()：

next, stop := iter.Pull2(index.All())
defer stop() // 未消费完整个序列时，确保迭代器能够结束

key, value, ok := next()
if ok {
    // 这里只取第一个键值对，后续由 defer stop 负责收尾。
    fmt.Println(key, value)
}

Pull2 返回的 next 会给出 key、value 和有效性 bool。不要从多个 goroutine 同时调用同一组 next/stop；官方文档把这种并发调用定义为错误。

遍历边界要在 API 文档里说清

Seq2 解决的是遍历形状，不会自动替你决定一致性和并发策略。树形索引至少要补充下面几项约定：

• 顺序：说明是中序、前序、后序还是按其他索引顺序；只有维护了搜索树不变量，才能承诺按 key 排序。
• 复用：上面的 All() 每次调用都会从根节点重新遍历，属于可重复使用的序列，不是单次数据流。
• 修改：只读迭代器不应把节点指针暴露出去。需要遍历中删除或更新时，应另设位置类型与受控方法，而不是让 value 暗中携带可变节点。
• 并发：如果遍历期间允许写入，必须单独定义锁或快照语义。不要简单地在调用 yield 时长期持有写锁，因为回调可能重新进入索引并造成死锁。
• 值语义：V 如果包含指针、切片或 map，复制键值对并不等于深拷贝；文档应说明调用方是否可以修改其指向的数据。

常见错误怎么定位

break 之后仍然访问了更多节点

先看 walker 是否返回 bool，再检查左子树、yield 和右子树三个位置是否都传播 false。只在最内层 return、父层却继续递归，是最常见原因。

遍历结果不是按 key 排序

中序遍历本身不创造排序。应检查插入、旋转或重建操作有没有维持搜索树不变量；如果索引允许重复 key，还要定义相同 key 的稳定顺序。

为什么不直接返回 map

map 会丢失树的遍历顺序，还需要把全部元素复制到新容器。若调用方只读取一部分，Seq2 可以保持惰性并支持提前停止。

结论

为树形索引暴露键值遍历时，让 All() 返回 iter.Seq2[K, V]，既能隐藏节点结构，又能让调用方使用熟悉的 for range。实现的关键是把递归 walker 设计成返回 bool，并完整传播 yield=false。再把顺序、复用、并发和修改语义写进 API 约定，这个遍历接口就不会只是“能跑”，而是一个可长期维护的集合边界。