# B+ 树 Bug 修复计划

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

## 当前状态

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

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

### 根本原因分析

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

**错误实现**（原代码）:
```go
pk := make([]byte, el-8)
copy(pk, rl.entries[:el-8])  // 直接取右兄弟第一个条目
```

**问题**: 右兄弟刚创建时，其第一个条目可能不是该子树的全局最小值，导致：
- 内节点 separator 与实际子树范围不匹配
- 路由时进入错误的子树
- 查询失败

**正确实现**（已修复）:
```go
pk := sbtLeftmostKey(handle, rl.info.Hdr.PageID, el)  // 遍历到最左叶获取真正最小值
```

### 为何仍有 0.46% 失败？

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

1. **路由约定不一致**
   - primary.go 使用 `>` (找第一个 > key 的 entry)
   - secondary/string 使用 `<=` (找最后一个 <= key 的 entry)
   - 两种约定对应不同的 separator 语义

2. **父节点分裂时的 separator 提取**
   - 当前使用 `sbtEntry(parent, mid)` 的 key
   - 应该使用右子树的最左键

3. **条目排序验证缺失**
   - 没有断言验证叶节点条目有序
   - 没有验证内节点 separator 与子树范围一致

4. **边界条件未覆盖**
   - 空树插入
   - 单节点满后分裂
   - 根节点分裂
   - 多层递归分裂

## 系统性修复方案

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

#### 1.1 创建 B+ 树验证工具
```go
// 验证 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: 回退到扁平链表
```go
// 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
- 🟢 **低风险**: 回退到扁平链表是安全的临时方案

## 建议行动

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

---

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