B+ 树 Bug 修复计划

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

当前状态

已知问题

查询失败率: 约 0.46% (10000行中46行查询失败)
失败模式: User_21, User_65, User_282 等特定索引无法找到
影响范围: 所有 B+ 树索引（primary/secondary/string）

已完成修复

✅ 添加 btLeftmostKey / sbtLeftmostKey / strBtLeftmostKey 辅助函数
✅ 分裂时使用正确的 promoKey（右子树最左叶的最小 key）
✅ Update key 传递 bug 修复

根本原因分析

B+ 树分裂时，separator（分隔键）的提取逻辑存在缺陷：

错误实现（原代码）:

pk := make([]byte, el-8)
copy(pk, rl.entries[:el-8])  // 直接取右兄弟第一个条目

问题: 右兄弟刚创建时，其第一个条目可能不是该子树的全局最小值，导致：

内节点 separator 与实际子树范围不匹配
路由时进入错误的子树
查询失败

正确实现（已修复）:

pk := sbtLeftmostKey(handle, rl.info.Hdr.PageID, el)  // 遍历到最左叶获取真正最小值

为何仍有 0.46% 失败？

经过多次尝试修复，失败率从 0.4% → 7% → 0.46% 波动，说明存在多个相互作用的 bug：

路由约定不一致
- primary.go 使用 > (找第一个 > key 的 entry)
- secondary/string 使用 <= (找最后一个 <= key 的 entry)
- 两种约定对应不同的 separator 语义
父节点分裂时的 separator 提取
- 当前使用 sbtEntry(parent, mid) 的 key
- 应该使用右子树的最左键
条目排序验证缺失
- 没有断言验证叶节点条目有序
- 没有验证内节点 separator 与子树范围一致
边界条件未覆盖
- 空树插入
- 单节点满后分裂
- 根节点分裂
- 多层递归分裂

系统性修复方案

阶段 1: 建立测试基础设施

1.1 创建 B+ 树验证工具

// 验证 B+ 树不变量
func ValidateBTree(rootPID uint32, handle page.HandleDb) error {
    // 1. 验证所有叶节点条目有序
    // 2. 验证内节点 separator 与子树范围一致
    // 3. 验证叶节点链表完整
    // 4. 验证所有 key 都能正确路由
}

1.2 自动化回归测试

每插入 N 行就全量验证
记录第一次失败的插入序号
Dump B+ 树结构用于调试

阶段 2: 统一路由约定

选择一种路由约定并全局统一：

方案 A: 使用 <= 约定（推荐）

entry[i].key = child[i] 子树的最小 key
child[i] 覆盖 [entry[i].key, entry[i+1].key)
路由: 找最后一个 entry.key <= searchKey

方案 B: 使用 > 约定

entry[i].key = child[i] 子树的最大 key + 1
child[i] 覆盖 (entry[i-1].key, entry[i].key]
路由: 找第一个 entry.key > searchKey

阶段 3: 逐层验证修复

3.1 叶节点操作

btLeafFind / sbtLeafFind: 二分查找正确性
btLeafPos / sbtLeafPos: 插入位置计算
条目复制时保持有序

3.2 分裂逻辑

合并旧条目+新条目到临时数组
平分数组到左右兄弟
提取正确的 promoKey（使用 leftmostKey）
更新叶节点链表指针

3.3 父节点更新

在正确位置插入 separator
父节点分裂时递归提升
新根创建时使用正确的左右 key

3.4 路由逻辑

btRoute / sbtRoute 与 separator 语义一致
btChildIdx / sbtChildIdx 正确定位子节点

阶段 4: 压力测试

10K 行插入 + 全量验证
100K 行插入 + 随机查询验证
1M 行插入 + 抽样验证
删除操作验证
更新操作验证
范围扫描验证

临时稳定方案

如果短期内无法完全修复，建议：

方案 B: 回退到扁平链表

// str_handler.go 改回使用扁平链表
type StrListHandler struct{}

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

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

优点:

经过验证，100% 正确
实现简单，无复杂边界条件

缺点:

插入/查询性能 O(n) vs B+ 树 O(log n)
10万行时性能下降明显

决策标准

如果 10K 行测试失败率 < 0.01%，继续使用 B+ 树
如果失败率 > 0.1%，回退到扁平链表
同时并行开发新的 B+ 树实现

时间估算

阶段	工作量	预计时间
阶段 1: 测试基础设施	2天	建立验证框架
阶段 2: 统一路由约定	1天	代码重构
阶段 3: 逐层验证修复	3-5天	核心修复
阶段 4: 压力测试	2天	全面验证
总计	8-10天	2周

风险评估

🔴 高风险: B+ 树 bug 可能导致数据丢失或查询错误
🟡 中风险: 修复过程可能引入新 bug
🟢 低风险: 回退到扁平链表是安全的临时方案

建议行动

立即执行: 运行 10K 行测试，确认当前失败率
短期（1周内）: 如果失败率 > 0.1%，回退到扁平链表
中期（2周内）: 系统性重写 B+ 树，建立完整测试
长期: 考虑使用成熟的第三方 B+ 树库（如 boltdb）

最后更新: 2026-09-09
当前失败率: 0.46% (10000行中46行)
下一步: 决定是继续修复还是回退到扁平链表

BPLUS_TREE_FIX_PLAN.md 5.4 KB Permalink Riwayat Mentahan