# 十月第二轮开发与审查（2026-10-03）

## 【1. 总体评价】

追加修订保留原始知识时间，适合事后勘误和追溯。本轮新增整批增量分页、多键联合有值区间。复查发现查询键 helper 先复制并排序全部输入，重复键多时无必要地占 O(q) 内存；已改为边扫描边检查唯一键预算，再仅排序唯一键。原文件保留在 `docs/archive/20261003/snapshot_timeline.mbt.txt`。

分页初始游标使用 `None`，能包含最小 Int64 时间的首批，继续读取使用 `Some(time)`；无时间戳加一的溢出。资料稿 20 行，参赛者空白。外部验收条件仍待推送/发布核验。

## 【2. 算法与性能分析】

- 方法名称：有界去重后排序。原 helper 时间 O(q log q)、额外空间 O(q)，新实现期望时间 O(q + u log u)、额外空间 O(u)，u 为不同键数；保留词法顺序和唯一键限额语义。哈希操作成本不含字符串本身长度；散列最坏情况不宣称常数。
- 整批分页：二分定位知识时间，扫描完整提交分组，先检查修订预算再复制；时间 O(log n + p + b)，p 为实际返回修订数，b 为下一未能装入页的批次扫描量，空间 O(p+返回批次数)。首批过大报错，不制造不能前进的空页；最多返回 max_batches 个完整组。
- 联合区间：复用每键事件排序/堆时间线，得到排序的最大有值区间，再双指针求交。各键历史 h_i 的时间线构建 O(h_i log(h_i+1))，额外历史事件 O(max h_i)，求交时间为各轮两个区间列表长度之和，结果 O(max_segments)。不将总体误写为只需 O(键数)。
- 实现代价：分页不提供事务传输/落盘；联合有值不等于权限允许。空键集为全 bounds，重复键不重复查询。

## 【3. 具体优化步骤】

1. 保留查询 helper 原文件，以 Map 去重，在插入新键前检查预算。
2. 初始/继续游标用 Option 区分，以二分比较避免最小/最大 Int64 哨兵错误。
3. 页面只有完整组；首组超过预算报错，后续组过大停止并设置 has_more。
4. 多键查询先统一验证键预算，再通过现有 matching_spans 和双指针求交。
5. 加入逐时刻参考对照、追页和极值测试；示例与 CI 覆盖组合功能。

## 【4. 推荐修改后的代码】

实现见 `batch_page.mbt`、`joint_coverage.mbt`、`snapshot_timeline.mbt`，集成见 `examples/maintenance/main.mbt`。

```text
page = ledger.batches_since(None, budgets)
处理 page.batches；有后续则传 page.next_known_at() 读取下一页
available = [bounds]
对每个唯一键：available = intersection(available, matching_spans(Assigned))
```

## 【5. 测试建议与已执行证据】

- 正常：多页追读不重复/漏批，多键区间与逐时刻点查询相符。
- 边界：首批恰好预算、空尾页、最小/最大 Int64 知识时间、开放右端、空键集。
- 异常：首批过大、max_batches=0、唯一键超限；回溯删除与无主张区间。
- 大规模：10,000 个相同输入键在 max_keys=1 下通过，避免复制整个请求数组。
- 新增 `batch_page_wbtest.mbt` 4 项；完整四后端各 85 项通过。
- 全后端 check/build 通过，新示例 wasm-gc 通过。后续性能建议固定 u 增大 q，以及多键相交碎片的预算压力测试；不承诺未测量的吞吐改善。