算法与数据结构

B+ 树与 LSM 树：外存数据结构

03-树与堆进阶预计 25 分钟B+树LSM存储引擎IO模型
学习状态：

一句话定义

B+ 树（B+ Tree）是把 BST 思想按磁盘块放大成「一节点一块、百路扇出、数据全在叶子」的多路平衡树，让树高即磁盘 IO 次数；LSM 树（Log-Structured Merge Tree）反其道而行，把随机写变成内存表 + 顺序追加 + 后台分层合并，用写性能换读放大。二者是数据库存储引擎的两大骨架。

为什么重要

内存里的「O(log n)」到了磁盘会失效：磁盘一次 IO 的代价相当于内存数十万次运算，瓶颈从「比较次数」变成「读块次数」。B+ 树与 LSM 树展示的是同一件事——按新的硬件代价模型重新设计结构。这是「数据结构选型 = 对硬件代价建模」这一工程方法论的最好教材，也解释了 MySQL InnoDB 与 LevelDB/RocksDB 的根本分野。

前置知识

kp-013（平衡树与旋转思想）；磁盘页（通常 4KB–16KB）与 IO 成本的常识。

核心概念

  • IO 代价模型：复杂度按「IO 次数」计；一个 16KB 页可装数百个键 ⇒ 扇出 m ≈ 数百，n 条记录树高仅 log_m n ≈ 3~4 层。
  • B+ 树结构：内部节点只存键与孩子指针做路标；全部数据在叶子，叶子间以链表串联 ⇒ 范围扫描变成叶子链表顺序读。
  • 节点规模约定：m 阶 B 树内部节点孩子数在 ⌈m/2⌉~m 之间，根例外；插入满则分裂、删除过半则借/合，树高只在根分裂时 +1。
  • LSM 写路径：写 → 内存 memtable（常用跳表）→ 满了冻结为 SSTable 顺序落盘 → 层数逐级 compact 合并去重。
  • LSM 读路径：memtable → L0 → L1… 逐层查，配合每层布隆过滤器（kp-010）挡「不存在」。
  • 三大放大：读放大（一次读要看几层）、写放大（一条写入最终落盘几遍）、空间放大（旧版本未清时的膨胀）；RocksDB 的调优本质是在三者间取舍。

直观类比

B+ 树是图书馆的分层索引牌：每层牌只告诉你去哪个大区（读一块，缩小百倍范围），书全在一楼书架（叶子）且书架之间连着传送带（叶子链表），查一个区间就是顺着传送带走。LSM 是「先往流水账本上按顺序记，记账极快；每隔一段时间把账本誊清合并去重」，代价是查一笔旧账要翻好几本账本。

原理与机制

树高估算（B+ 树为什么 3 层就够）：页 16KB，键 8B + 指针 6B ⇒ 每页约容纳 1000 个路标；三层即 1000 × 1000 × 1000 ≈ 10⁹ 条记录的索引，而一次点查最多 3~4 次页读（含根缓存命中则更少）。LSM 的写放大来源：一条键值对在 L0→L6 的逐层 compact 中平均被重写多次（大小分层策略下与层数同量级），故读少写多选 LSM、读多写少 B+ 树常胜。

图示

B+ 树（扇出 4 简化）:
            [ 17 | 35 ]                ← 内部节点（路标）
           /     |      \
   [5|9|12] [17|21|28] [35|40|46]    ← 叶子（含数据）
      └──────┴─叶子链表─┴────────┘    范围扫描沿链表走

LSM 写路径:  写请求 → memtable(内存) → 冻结SSTable(L0)
           → compact 合并 → L1 → L2 → …（逐层更大、有序）
           读: memtable → L0 → L1…（布隆过滤器提前拦截未命中）

实例或案例

  • MySQL InnoDB、PostgreSQL 主索引：B+ 树；叶子即数据页（聚簇）或行指针（二级索引）。
  • LevelDB / RocksDB / Cassandra / HBase：LSM 系；写吞吐高，适合日志、时序、消息类负载。
  • 文件系统（ext4/xfs 的目录项与 extents 管理）与 MongoDB WiredTiger 同样是 B+/B 树家族。
  • 调优实例：RocksDB 增大 max_background_compactions 缓解写停顿；InnoDB 调整页大小与 buffer pool 命中率。

常见误区

  • 把 B 树当成「二叉树的多叉版」混谈：B+ 树的关键增量是「数据只在叶子 + 叶子链表」，直接决定范围查询性能。
  • 认为 LSM 一切场景更快：读放大在点查密集负载上常把 LSM 打回原形，选型要按读写比。
  • 忽略页大小与扇出的关系：页越小扇出越少树越高，IO 反而更多——结构参数由硬件代价模型决定，不是拍脑袋。
  • 把树高等同于 IO 次数却不考虑缓存：根与上层常驻内存，实际 IO 常只有 1 次（叶层）。

自测题

  1. 扇出 200、1 亿行数据的 B+ 树约几层？一次点查最多几次页读？

答案要点：200² = 4×10⁴，200³ = 8×10⁹ ≥ 10⁸ ⇒ 3 层（含根），最多 3 次页读，缓存命中后常 1 次。

  1. LSM 为什么写快？读慢在哪？

答案要点：写全部转为内存表+顺序追加，无随机 IO；读可能要查 memtable 加多层 SSTable（读放大），靠布隆过滤器与缓存缓解。

  1. 读多写少的报表库应选 B+ 树还是 LSM？为什么？

答案要点：B+ 树；点查与范围读的 IO 路径短且稳定，LSM 的多层读放大在此得不偿失。

与其他知识点的关系

kp-013 的平衡/旋转思想是 B+ 树分裂合并的源头；kp-010 布隆过滤器是 LSM 读路径的标配；kp-023 外部排序的「有序 run + 归并」与 SSTable 的分层合并同构；kp-032 的选型决策树把两者放进同一张表。

延伸阅读

Comer, "Ubiquitous B-Tree"；O'Neil 等 LSM-Tree 论文；Database Internals（Alex Petrov）第一部分。

前置知识点

相关知识点