Mini-Pages：重新思考叶页边界

Source: Dev.to

你好，我是Maneshwar。 我正在开发 FreeDevTools online，目前正在构建 一个集所有开发工具、技巧代码和 TLDR 于一体的地方 —— 一个免费、开源的中心，开发者可以快速找到并使用工具，而无需在互联网上四处搜索。

在昨天的文章中，我们探讨了为什么 B‑Tree 和 LSM‑Tree 都难以充分利用现代硬件——前者受缓存污染困扰，后者则受压实、放大以及操作复杂性的制约。

今天我们将超越这些结构为何不足的原因，看看 用什么来取代页面本身。

Bf‑Tree 的答案：Mini‑Pages

Bf‑Tree 的答案不是另一个缓存、缓冲区或调优技巧，而是对 叶子节点的结构性重新思考。
这次重新设计的核心是一种新原语：mini‑page（小页）。

• mini‑page 是 叶子页的轻量级、内存版，范围严格、专门构建。
• 与缓冲池页或 LSM memtable 不同，mini‑page 仅存在于叶子节点，且 每个叶子页只能有一个 mini‑page。

此设计选择是有意为之。mini‑pages 不是通用缓存；它们是 叶子页的精确扩展，旨在：

1. 缓冲最近的更新
2. 缓存经常访问的记录

关键是，它们在 不将完整页拉入内存 的情况下实现上述功能。

吸收写入而不产生页级放大

当写入目标是叶子页时，Bf‑Tree 不会立即触碰磁盘上的页。相反，写入会被插入到该叶子的 mini‑page 中：

• 若不存在 mini‑page，则 创建一个极小的页面（小至 64 字节，按缓存行对齐）。
• mini‑page 内的记录保持 有序，以保留空间局部性。
• 插入使用 二分查找，而不是指针追踪。

随着更新的累积，mini‑page 会动态增长：

• 当满时 大小翻倍。
• 增长一直进行，直至达到上限（最高可达 4 KB）。

当 mini‑page 达到该上限或必须被驱逐时，系统会 批量合并 mini‑page 到磁盘上的基础叶子页。

这同时实现了两件事：

• 写入 在内存中被吸收并合并。
• 磁盘写入以 更大、更高效的批次 进行。

没有 delta 链，没有对多个结构的每次更新日志，也没有后台压缩管道。更新保持局部、有序且友好缓存。

在不缓存页的情况下缓存热点记录

读取遵循同样严格的路径。磁盘访问前，查找会 对 mini‑page 进行二分查找：

• 命中：记录立即返回。
• 未命中：从磁盘读取对应的叶子页。

加载记录后，Bf‑Tree 可能会 以概率方式（例如 1 % 的概率）将其缓存回 mini‑page。这避免了冷数据充斥 mini‑page，同时让热点记录自然累积。

关键区别： mini‑pages 缓存的是记录，而不是页。
传统 B‑Tree 缓存整页，即使只有一条记录是热点。LSM 系统将缓存拆分为行缓存和块缓存，各自拥有独立的内存预算和调优参数。mini‑pages 避免了这两种极端。

通过缓存间隙适配范围扫描

仅记录级缓存不足以支撑范围扫描。范围扫描依赖 空间局部性，而缓存孤立记录会破坏这种局部性。Bf‑Tree 通过一个优雅的枢纽来解决此问题。

当 mini‑page 增长到满大小时，它可以 合并并提升为完整的叶子页表示，与磁盘上的布局相同。此时：

• mini‑page 实际上成为 页级缓存。
• 范围扫描恢复空间局部性。
• 不再需要额外的缓存层。

因此，同一内存预算可以灵活支持：

• 点查询（通过小型 mini‑pages）
• 范围扫描（通过完整大小的页）

不同于需要在行缓存和块缓存之间 静态划分 的系统，Bf‑Tree 能自动随工作负载模式的变化而调整。

单一布局，两种角色

mini‑pages 与叶子页共享 完全相同的物理布局；唯一的区别是大小。

• 两者都存储有序的键‑值对并支持高效查找。
• mini‑pages 允许可变长度，而叶子页在磁盘上保持固定大小。

这种统一布局：

• 降低实现复杂度
• 避免重复逻辑
• 使针对内存和磁盘的优化能够统一应用

在内部，每页都以紧凑的节点元数据头开始，随后是元数据条目以及从相对两端打包的实际键‑值数据。插入时移动的是元数据，而不是完整的页面结构。

records，保持操作快速且缓存友好。

在不破坏并发性的情况下映射页面

叶子页始终位于磁盘上；小页位于内存中。两者都通过相同的 逻辑页面 ID 进行引用。

Bf‑Tree 使用 内存映射表 将此页面 ID 转换为以下任意一种：

• 内存地址（小页），或
• 磁盘偏移（叶子页）

映射表还在页面地址旁边嵌入了 读写锁，并打包为单个 64 位字。由于小页及其对应的叶子页共享相同的页面 ID：

• 锁定其中一个会隐式锁定另一个。
• 并发模型保持简洁。
• 不需要额外的协调层。

这种间接层将页面位置与页面身份解耦，使得页面可以在内存和磁盘之间移动，而无需在整棵树中重写指针。

为什么 Mini‑Pages 很重要

Mini‑pages 不是缓存调优；它们是对页面概念的 根本重新定义。它们在保持顺序、局部性和可预测性的同时，模糊了内存与磁盘的界限。

• 写入变为局部。
• 读取变为选择性。
• 范围扫描重新获得效率——无需后台压缩、多层探测或缓存分区。

这就是 Bf‑Tree…（根据需要继续）。

- **Tree** stops being a “better B‑Tree” and starts looking like a **new storage primitive**—one that finally aligns data structures with modern hardware realities.

[![FreeDevTools](https://media2.dev.to/dynamic/image/width=800,height=,fit=scale-down,gravity=auto,format=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fo5e57lh7rtwwwe2d694n.png)](https://hexmos.com/freedevtools/)

👉 **Check out:** [FreeDevTools](https://hexmos.com/freedevtools/)

Any feedback or contributors are welcome!  

It’s online, open‑source, and ready for anyone to use.

⭐ **Star it on GitHub:** [FreeDevTools](https://github.com/HexmosTech/FreeDevTools)