B+树变体：存储引擎优化方案

可视化演示

数据库存储引擎实现中的B+树变体。你将学习B+树的常见变体（B*Tree/CoW B-Tree/Fractal... 切换模式查看不同维度。

变体与动机

管理员复盘时发现，问题不在于书架不好用，而在于“每本新书都要立刻精确归位”这件事实在太重了。传统 B+树非常擅长读：从根目录牌一层层往下找，最终在叶子链表里顺序扫一遍，就能高效回答区间查询。可一旦遇到高频随机写，每插入一条记录都可能触发叶子节点分裂、父节点更新，甚至向上蔓延到根，物理上要写多个页面。

在存储引擎里，“写放大”就是物理写入量与逻辑写入量的比值。逻辑写一次，物理却写了好几个页，这就是放大。与它对应，读放大是一次查询读取的页数远多于有效数据；空间放大则是旧版本数据和空页没有被及时回收。B+树的每一种变体，本质上都是在调整这三个指标。

管理员终于明白，所有变体都是在“上架成本、找书速度、空位占用”之间做交易。接下来看到的每个方案，都只是换了种交易方式。

B*Tree

管理员的第一个改进来自一位老馆员的经验：书架满了，不一定急着开新书架。B*Tree 的策略是，当节点满时，先尝试把一部分记录借给相邻的兄弟节点；只有当兄弟节点也满时，才将原来的节点分裂成三个新节点。这样既推迟了树高度的增长，又能让节点平均填充率达到约 2/3。

对写放大来说，B*Tree 减少了由分裂引发的连锁更新。一次分裂本来要新建节点、改写父节点指针，现在可能只需要在兄弟之间移动几条记录。而且叶子节点和内部节点都保持有序，范围读依旧可以在叶子链表上进行。代价是插入逻辑变得更复杂，需要维护兄弟指针，还要处理借位后的边界条件，工程实现比 B+树更繁琐。

不过，B*Tree 的优化依然建立在“读多写少”的基础上。它把书架的利用率提高，却没改变“每本书必须尽快精确上架”的根本假设。如果写入压力继续增大，管理员还需要更彻底的方案。

CoW B-Tree

第二个方案更激进：不再擦改旧目录，而是每次修改时沿着路径复制一份目录牌，改好后把大厅的总目录指针原子地指向新版本。CoW B-Tree 因此让读操作永远看到修改前的完整快照，读完全不需要加锁。修改路径上有 h 个节点，就要复制 h 个页面。

CoW 的代价是旧版本页面不会立刻消失，需要后台按照版本号和安全水位回收不可达页面。这就像图书馆每次改版都要留下旧目录，等确认没人再看后才能销毁。优点是并发读非常平滑，特别适合快照隔离、多版本并发控制等场景。

Fractal Tree

第三个方案来自前台灵感：还书高峰时，管理员不立刻上架，而是把书放进待办箱，贴上便签。Fractal Tree 在每个内部节点里放一个“消息缓冲”，单条写操作被包装成消息，并不立即下钻到叶子，而是积攒到一定量后再批量地向下一层传递。

这种设计把多次随机写合并成一次批量写，磁盘 I/O 次数大幅下降。如果把 B+树的一次插入看成“每次都要跑到叶子书架”，Fractal Tree 则像“先在每层目录牌上贴便签，攒够一批再统一整理”。它还允许更大的扇出，因为在节点中留出了缓冲空间。代价是读一个值时要同时检查缓冲区消息和真实数据，工程实现也远比其他变体复杂。

Fractal Tree 在读写两边都试图做到不错，但复杂的缓冲管理让它主要出现在少数追求极致写性能的存储引擎中。对大多数团队来说，它是一个值得参考的思路，而不是默认选项。

LSM-Tree

第四个方案最像流水账：管理员在小本子上记下每笔还书，等本子写满再誊抄成正式书架。LSM-Tree 的所有写操作先进入内存表（memtable），内存表满后刷成不可变文件，后台定期把多层文件压缩合并。由于写不直接修改已有大文件，随机写被转换为顺序写，写入极快。

LSM 用读放大换取低写放大：读一个键可能要查内存表和多层文件，压缩时还会重新写一遍旧数据。因此它特别适合日志、监控、消息队列等写多读少、且不要求超低点查延迟的场景。

Flash 友好设计

后来图书馆换了一批电子书架，管理员发现电子卡片不能随便涂改：闪存介质要按页读写、按块擦除，随机写不仅慢，还会减少寿命。存储引擎因此更偏好顺序写、追加写，尽量避免原地覆盖。CoW、LSM 这类变体的“新版本替换旧版本”思路，恰好和闪存天然契合。

如果一块由 P_block 个页组成，随机改写其中一页最坏也要重写整个块，所以介质层的写放大最大可到 P_block。

这让“少动原位置”成为闪存时代的第一原则。管理员最终发现，只要把书按顺序写进新书架，避免反复抽出插入，电子书架的寿命和写入速度都会明显提升。

存储引擎应用

不同图书馆最终选择了不同管理模式。MySQL 的 InnoDB 保留经典 B+树，因为它面对的是大量点查和范围查询，读多写少；RocksDB 选择 LSM-Tree，在日志、缓存、消息队列等写密集场景大放异彩；MongoDB 的 WiredTiger 默认用 B+树，同时可选 LSM；一些早期存储引擎曾用 Fractal Tree，试图在读写之间找到更平滑的折中。

选型的核心是读写比与延迟要求：读多写少选 B+树或 B*Tree，写多读少选 LSM，高并发读且需要快照隔离时 CoW 也有独特价值。好比图书馆先统计读者画像：如果是老年社区，大家喜欢慢慢翻书，精确上架最稳妥；如果是数据机房，每秒都在产生新记录，流水账加定期归档才是正道。

没有一种变体是绝对最优。存储引擎的选型，本质上是在“读快一点、写快一点、省一点空间”三个愿望中挑选优先级，然后接受相应的代价。

性能评估优化

最后，管理员在办公室挂了一张指标看板：上架成本、找书速度、空位占用。存储引擎的评估也是如此。空间放大用物理占用与逻辑数据的比值来衡量。

除了放大率，还要看端到端延迟和吞吐曲线，调优参数包括页大小、内存缓冲、合并触发频率和压缩算法。管理员最终不再寻找“完美书架”，而是用数据回答：在这个图书馆，哪些请求更重要，愿意为它们牺牲什么。

AI 应用场景

Python 演示

import bisect class LSMStore:    def __init__(self, mem_size=4, max_runs=2):        self.mem_size = mem_size        self.max_runs = max_runs        self.mem = {}        self.levels = [[]]        self.physical_writes = 0        self.logical_writes = 0     def _ensure_level(self, level):        while len(self.levels) <= level:            self.levels.append([])     def put(self, key, value):        self.mem[key] = value        self.logical_writes += 1        if len(self.mem) >= self.mem_size:            self._flush()     def _flush(self):        run = sorted(self.mem.items())        self.mem = {}        self.physical_writes += len(run)        self._place_run(0, run)     def _place_run(self, level, run):        self._ensure_level(level)        self.levels[level].append(run)        if len(self.levels[level]) >= self.max_runs:            merged = self._merge_runs(self.levels[level])            self.physical_writes += len(merged)            self.levels[level] = []            self._place_run(level + 1, merged)     def _merge_runs(self, runs):        keys = {}        for run in reversed(runs):            for k, v in run:                keys[k] = v        return sorted(keys.items())     def get(self, key):        if key in self.mem:            return self.mem[key]        for level in self.levels:            for run in reversed(level):                i = bisect.bisect_left(run, (key,))                if i < len(run) and run[i][0] == key:                    return run[i][1]        return None     def write_amplification(self):        return self.physical_writes / max(self.logical_writes, 1)  if __name__ == "__main__":    db = LSMStore()    for i in range(12):        db.put(i, "v%d" % i)    print("levels:", [[len(r) for r in level] for level in db.levels])    print("get(5) =", db.get(5))    print("write amplification = %.2f" % db.write_amplification())

1. self.mem[key] = value所有写操作都先进入内存表，对应“先记在流水账本上”。
2. if len(self.mem) >= self.mem_size:内存表达到阈值，触发一次刷盘。
3. run = sorted(self.mem.items())内存表排序后变成一段不可变的有序数据，对应一次 flush。
4. self.physical_writes += len(run)每次刷盘都要按页面数量累计物理写入。
5. merged = self._merge_runs(self.levels[level])合并当前层所有 run，是 LSM 后台压缩的核心动作。
6. return self.physical_writes / max(self.logical_writes, 1)返回写放大系数，直观展示 LSM 的写成本。

常见误区

面试题