AI技术
Bf-Tree 中的负查找：缓存不存在的东西
✍️ zhirenhun
📅 2026/5/29
👁 62 阅读
⏱ 3 分钟
当查询反复寻找不存在的数据
大多数缓存系统都为快速查找记录而优化。但当查询反复询问一个不存在的键时，会发生什么？
SELECT * WHERE id = 999999;传统的记录缓存在这里遇到了困难。如果一条记录在缓存中缺失，系统无法判断：该记录从未被缓存过，还是该记录确实不存在？于是它回退到磁盘，再次检查叶子页面。反复的负向查找变成了反复的 I/O。
Bf-Tree 也缓存缺失的记录
Bf-Tree 将失败的查找视为有用信息。当一个键被搜索并确认不存在时，它会在 mini-page 中插入一条 phantom record（幻影记录）：
查找键=42
↓
磁盘上未找到
↓
存储 phantom record
后续查找：
查找键=42
↓
找到 phantom record
↓
返回"未找到"无需访问叶子页面。数据的缺失成为了缓存状态。
Mini-Page 中的四种记录类型
| 类型 | 脏标记 | 存在 |
|---|---|---|
| Insert（插入） | 是 | 是 |
| Cache（缓存） | 否 | 是 |
| Tombstone（墓碑） | 是 | 否 |
| Phantom（幻影） | 否 | 否 |
phantom record 的本质就是："我们已经查过了。这个键不存在。"对于频繁发生失败查找的工作负载来说，这个特性出奇地有用。
恢复机制依然熟悉
尽管引入了 mini-page 和 phantom record，持久化机制仍然是传统的。Bf-Tree 使用：
- 预写日志（WAL） —— 提交前写入
- 检查点/快照 —— 持久化状态
- 通过 WAL 重放恢复
崩溃恢复流程：加载快照 -> 重建内存页面 -> 重放 WAL -> 恢复最新状态。
Bf-Tree 将"记录不存在"视为值得缓存的信息。
文章来源：Negative Lookups in Bf-Tree: Caching Things That Don't Exist — dev.to
——
🧑💻
zhirenhun
一个热爱技术的程序员，喜欢分享前沿AI知识和开发经验。
