B+ 树修复进展报告

本文档为历史修复记录，所述问题已修复，仅留档参考。

当前状态 (2026-09-09)

✅ 已完成

根本原因定位
- 所有三个 B+ 树实现（primary/secondary/string）都有同样的 bug
- 分裂时直接取右兄弟第一个条目作为 separator，而非遍历到最左叶获取真正的最小值
部分修复
- 添加了 btLeftmostKey / sbtLeftmostKey / strBtLeftmostKey 辅助函数
- 修改 secondary.go 和 primary.go 使用正确的 promoKey
- 创建了验证框架 validate.go
测试结果
- 查询失败率：0.46% (10000行中46行)
- 失败模式稳定：User_21, User_65, User_282 等特定索引
- 数据确认存在于叶节点中（暴力扫描可找到），但 B+ 树路由错误

🔍 深入分析

路由约定对比

B+ 树类型	路由函数	比较操作	entry.key 语义
primary.go	btRoute	`>` (找第一个 > key)	child[i] 的上界+1
secondary.go	sbtRoute	`<=` (找最后一个 <= key)	child[i] 的最小 key
string_btree.go	strBtRoute	`<=` (同 secondary)	child[i] 的最小 key

关键发现：primary 和 secondary 使用互斥的路由约定！

已修复的问题

分裂时 promoKey 提取 ✅

// 错误：直接复制右兄弟第一个条目
pk := make([]byte, el-8)
copy(pk, rl.entries[:el-8])
   
// 正确：遍历到最左叶获取真正最小值
pk := sbtLeftmostKey(handle, rl.info.Hdr.PageID, el)

新根创建时的左右 key ⚠️
- secondary.go: 已正确使用 sbtLeftmostKey(leftPID) 和 promoKey
- primary.go: 仍使用相同的 promoKey 用于左右条目（可能有问题）

仍存在的问题

假设: secondary B+ 树使用 <= 路由约定，entry[i].key = child[i] 子树的最小 key

验证:

sbtRoute: 找最后一个 entry.key <= searchKey ✅ 正确
sbtChildIdx: 同样使用 <= ✅ 一致
父节点插入 separator: 找第一个 entry.key >= promoKey 的位置 ✅ 正确

那为什么还有 0.46% 失败？

可能的原因：

叶节点条目排序问题 - sbtLeafPos 二分查找在某些边界条件下返回错误位置
重复 key 处理 - 多个相同 key 的条目插入顺序可能导致排序错乱
父节点分裂时的 separator 提取 - 当前使用 sbtEntry(parent, mid) 的 key，应该使用右子树的最左键
缓存一致性 - sbtSave 后立即 sbtLoad 可能读到旧数据

📋 下一步计划

方案 1: 系统性调试（推荐）

添加断言验证

// 每次插入后验证
func assertBTreesValid(rootPID uint32, handle page.HandleDb) {
   // 1. 验证所有叶节点条目有序
   // 2. 验证内节点 separator 与子树范围一致  
   // 3. 验证每个 key 都能正确路由到包含它的叶节点
}

定位第一次失败
- 逐行插入，每插入一行就验证
- 记录导致失败的精确插入序号和 key
- Dump B+ 树结构分析
修复并回归测试
- 修复发现的 bug
- 重新运行 10K/100K/1M 测试

预计时间: 3-5 天

方案 2: 回退到扁平链表（临时稳定）

如果短期内无法完全修复，建议字符串索引回退到经过验证的扁平链表实现：

// str_handler.go
type StrListHandler struct{}

func (h *StrListHandler) Insert(...) {
    // 线性搜索插入位置 O(n)
    // 保证 100% 正确性
}

func (h *StrListHandler) Search(...) {
    // 线性搜索 O(n)
    // 100% 正确
}

优点: 立即消除所有 bug 缺点: 性能从 O(log n) 降到 O(n)，10万行时明显变慢

决策标准:

如果 10K 行测试失败率 < 0.01%，继续修复 B+ 树
如果失败率 > 0.1%，回退到扁平链表

🎯 建议行动

立即: 运行逐行插入测试，定位第一次失败
今天内: 根据失败模式决定是继续修复还是回退
本周内: 完成修复或回退，确保主分支稳定

最后更新: 2026-09-09
当前失败率: 0.46%
下一步: 逐行插入测试定位第一次失败

BPLUS_TREE_PROGRESS.md 4.2 KB Permalink Verlauf Originalformat