# B+ 树修复进展报告

## 当前状态 (2026-09-09)

### ✅ 已完成
1. **根本原因定位**
   - 所有三个 B+ 树实现（primary/secondary/string）都有同样的 bug
   - 分裂时直接取右兄弟第一个条目作为 separator，而非遍历到最左叶获取真正的最小值
   
2. **部分修复**
   - 添加了 `btLeftmostKey` / `sbtLeftmostKey` / `strBtLeftmostKey` 辅助函数
   - 修改 secondary.go 和 primary.go 使用正确的 promoKey
   - 创建了验证框架 validate.go

3. **测试结果**
   - 查询失败率：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 使用**互斥的路由约定**！

#### 已修复的问题

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

2. **新根创建时的左右 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% 失败？**

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

### 📋 下一步计划

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

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

2. **定位第一次失败**
   - 逐行插入，每插入一行就验证
   - 记录导致失败的精确插入序号和 key
   - Dump B+ 树结构分析

3. **修复并回归测试**
   - 修复发现的 bug
   - 重新运行 10K/100K/1M 测试

**预计时间**: 3-5 天

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

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

```go
// 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%，回退到扁平链表

### 🎯 建议行动

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

---

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