Bf-Trees：突破页面壁垒

Source: Dev.to

你好，我是 Maneshwar。我正在打造 FreeDevTools —— 一个在线开源平台，汇集开发工具、速查代码和 TLDR，帮助开发者无需漫无止境的搜索即可轻松找到并使用工具。

真正的问题：页面太大

• 数据库页通常是 4 KB 或 8 KB。
• 每一次更新或读取都会带来大量无关数据：
  • 50 字节的记录更新会重写整整一个 4 KB 页面。
  • 缓存 5 条热点记录的同时也缓存了 200 条冷数据。
  • 范围扫描和点查询争夺同一页级缓存。
• 思考实验： 如果记录大小等于页面大小，这些问题会立刻消失。

Bf‑Tree 的核心思想

Bf‑Tree 打破了缓存页必须与磁盘页相同的假设。

Disk page  !=  Cache page

相反，内存中保存 小页：可变长度的块，只存储真正需要的内容：

• 单个热点记录
• 一个小的键范围
• 缓冲的最近写入
• 需要时用于范围扫描的完整页面

小页会根据工作负载动态增大或缩小，从而彻底改变性能格局。

对比：传统 B‑Tree 与 Bf‑Tree

可变长度缓冲池

为了高效管理小页，Bf‑Tree 在内存中使用循环缓冲区：

• 总大小固定。
• 通过移动尾指针分配小页。
• 空闲空间在空闲列表中跟踪。
• 增长通过写时复制 (RCU) 处理。
• 当满时 → 将靠近头部的小页驱逐回磁盘。

该设计实现了并发分配、调整大小和驱逐，而不会产生碎片灾难。

这带来了什么

• 点查询： 快速，因为小页只缓存热点。
• 范围扫描： 需要时小页会扩展为完整页面。
• 写入： 只修改对应的小页。

数据

评估结果显示：

• 写入速度提升 6 倍 相比 B‑Tree。
• 点查询速度提升 2 倍 相比 B‑Tree 与 LSM。
• 扫描速度提升 2.5 倍 相比 RocksDB（LSM‑Tree）。

简而言之，Bf‑Tree 在所有工作负载下同时超越 B‑Tree 与 LSM‑Tree——这在读写都能提升的情况下极为罕见。

为什么重要

现代系统的数据量已超出 RAM 大小。Bf‑Tree 表明未来不再是二元的 B‑Tree 与 LSM‑Tree 之争，而是 重新思考页面。

下一篇文章

接下来，我将深入探讨三个方向：

1. 理解 LSM‑Tree 的内部机制以及它们的优势与局限。
2. 现代 NVMe SSD 行为如何改变写入成本模型。
3. Bf‑Tree 与小页背后的架构细节。

这些主题将为探索 RCU 的增长/收缩、驱逐策略以及并发保证奠定基础。敬请期待。

👉 查看: FreeDevTools
欢迎任何反馈或贡献！它是在线的、开源的，随时可供使用。
⭐ 在 GitHub 上给它加星: