B-Tree 1972 — 磁盘友好的索引结构

是什么

B-Tree 是 1972 年 Bayer 和 McCreight 发明的一种对磁盘 IO 友好的多路平衡树。每个节点能装很多键值，所以树非常浅，查一条记录只要少数几次磁盘读。

日常类比：内存里的二叉树像双向单车——每个路口只能选左或右；B-Tree 像公交车——一节车厢直接装几十个乘客。每次”换车”等于一次磁盘读（机械盘 ~10 ms，SSD 仍比内存慢 1000 倍），少换几次车就是大幅省时间。

举个尺度感：

100 万行的表，平衡二叉树深度约 20 → 最坏 20 次磁盘读
100 万行的表，B+Tree 深度约 3 → 最坏 3 次磁盘读

为什么重要

不理解 B-Tree，下面这些事都说不清楚：

为什么 PostgreSQL / MySQL / Oracle 加 CREATE INDEX 之后查询就快了——它们的默认索引底层就是 B+Tree
为什么 NTFS / ext4 / Btrfs 这些文件系统翻 100 万个文件不卡死——它们也用 B+Tree 组织目录
为什么”B+Tree vs LSM-Tree”几乎是每篇存储引擎设计文章的开头——这是磁盘存储两大派的分水岭
为什么一篇 50 多年前的论文今天还在每个数据库的源码里跑着

核心要点

B-Tree 把”对磁盘读友好”拆成三件事：

多路（Multi-way）：每个节点不是只装 1 个键 + 2 个指针，而是装几百到上千个键 + 对应指针。一个节点正好填满一个磁盘块（典型 4 KB / 8 KB / 16 KB），读一次磁盘 = 拿到几百个键。深度从此从 20 层压到 3 层。
平衡（Balanced）：插入 / 删除时如果节点装满或太空，就分裂或合并，保证从根到任意叶的路径长度差不超过 1。换句话说——不会出现”一边深 20 层、一边深 3 层”的歪斜。
B+Tree 变种：在原始 B-Tree 基础上做两点改造——① 数据只放在叶子节点，内部节点只存键和指针（更紧凑，单节点能装更多键）② 叶子节点之间用链表横向串起来（范围扫描时不用回到根）。今天工业上说”B-Tree 索引”几乎都指 B+Tree。

实践案例

案例 1：3 次磁盘读跨 100 万行

假设 B+Tree 节点能装 200 个键：

第 1 层（根）：1 个节点，200 个键，指向 200 个子树
第 2 层：200 个节点，覆盖 200 × 200 = 40000 个子树
第 3 层（叶）：40000 个节点，每个含 200+ 行 ≈ 800 万行总容量

查 WHERE id = 5000：根 → 中间 → 叶，3 次磁盘读完事。100 万行表绰绰有余。

案例 2：范围查询靠叶子链表

SELECT * FROM orders WHERE id BETWEEN 100 AND 200;

B+Tree 的执行路径：

从根往下定位到 id=100 所在的叶子节点（3 次磁盘读）
顺着叶子链表往后扫，直到 id 超过 200
不用每行都从根重新找

所以 B+Tree 对点查 + 范围查都很快。这是关系数据库默认用它的核心原因。

案例 3：和 LSM 派的分工

维度	B+Tree	LSM-Tree
写延迟	中（要定位 + 可能分裂）	低（追加写日志）
读延迟	稳定（固定 3-4 层）	波动（可能扫多层 SSTable）
写放大	中	高（compaction）
典型用户	OLTP 数据库（PostgreSQL / MySQL InnoDB）	KV 引擎 / 时序（rocksdb-lsm / Cassandra / LevelDB）

简单选型：读多写少 / 范围查 / 事务 → B+Tree；写极多 / append-only → LSM。

踩过的坑

节点大小要匹配磁盘块：节点设成 1 KB 而磁盘块是 4 KB → 一次磁盘读浪费 3/4 容量。InnoDB 默认 16 KB 不是拍脑袋的数字，是和 SSD 页大小对齐过的。
写放大问题：插一行可能触发节点分裂 → 上层指针更新 → 上上层又分裂。最坏情况一次插入引发整条根到叶的连锁写入。这是 LSM 派攻击 B+Tree 的主要点。
范围扫描需要 B+Tree（不是原始 B-Tree）：1972 论文的 B-Tree 把数据散在所有节点上，范围扫描得走中序遍历跨多层。B+Tree 把数据全压到叶子 + 横向链表，才让范围查询线性扫得动。
并发场景的锁竞争：高并发写时根节点会成锁热点。生产数据库用 latch coupling、Bw-Tree、OLFIT 等改造来缓解，但都得针对这点专门设计。

适用 vs 不适用场景

适用：

关系数据库的主键索引 / 二级索引（OLTP 场景）
文件系统目录索引（ext4 的 HTree / NTFS / Btrfs）
范围查询多 + 事务一致性要求高的场景

不适用：

写远多于读（日志、时序数据）→ LSM-Tree 更合适
数据全在内存，磁盘 IO 不是瓶颈 → 红黑树 / 跳表更轻
只查点不查范围 → 哈希索引更快（O(1) vs O(log n)）
数据量极小（< 1 万行）→ 顺序扫就够，建索引反而慢

历史小故事（可跳过）

1972 年：Rudolf Bayer 和 Edward McCreight 在波音研究室发表论文 Organization and Maintenance of Large Ordered Indexes。问题背景是大型机磁盘越来越大但内存就那么点，得想办法让磁盘上的索引”对 IO 友好”。
1979 年：IBM System R 把 B-Tree 当默认索引（selinger-1979 的查询优化器代价模型就建立在这个假设上），第一个商业关系数据库的奠基。
1990 年代：Oracle / DB2 / Sybase / SQL Server 全部跟进，B+Tree 成事实标准。
2000 年代：MySQL InnoDB 把 B+Tree 调到极致，SQLite 文件格式直接是 B-Tree。
2010 年代之后：LSM-Tree 派崛起（LevelDB / RocksDB / Cassandra），但 B+Tree 在 OLTP 没被替代——读稳定 + 事务原生支持是它的护城河。

50 多年过去，每天数十亿次 SQL 查询的底下都是这棵树。

学到什么

算法要为硬件特性设计：B-Tree 不是数学上”最优”的搜索树（红黑树深度更小），它的优势在于把”一次磁盘读”这个昂贵操作的价值榨干——这是系统层算法的典型套路。
多路 + 平衡 + 叶链 是 B+Tree 三件套，缺一不可。
写慢读快 vs 写快读慢 是存储引擎的经典权衡，B+Tree 和 LSM 各占一边，新引擎多在两端之间挪。
50 年仍未被替代：好的数据结构不是被淘汰，而是被分工。
节点大小贴合 IO 单元：节点定 4 KB / 8 KB 不是随便选——和磁盘 page、文件系统块、SSD 擦写单元对齐才能把每次 IO 的字节数榨干，这条原则今天仍在新存储引擎里反复出现。
范围扫描决定形态：B+Tree 把数据全压到叶子并加链表，直接换来”范围查询” 的线性扫描；这条结构性选择把它和 hash index 的命运彻底分开——索引选型本质是”查询模式” 选型。

关联

knuth-taocp —— TAOCP 第 3 卷《排序与查找》详细讲了多路平衡树的家族谱系

反向链接

aries-1992 —— ARIES 1992 — 数据库崩溃后怎么把账目对回来
art-2013 —— ART 自适应基数树 — 内存数据库为主索引重新选材
comer-1979-btree —— Comer 1979 — B-Tree 综述：为什么这棵树到处都有
diskann-2019 —— DiskANN — 单机十亿向量近邻检索（图存 SSD）
ingres-1976 —— INGRES 1976 — Berkeley 平行实现的关系数据库
knuth-taocp —— Knuth TAOCP — 计算机程序设计艺术
lmdb-2011 —— LMDB 2011 — 把数据库直接 mmap 进内存的嵌入式 KV 存储
rocksdb-2017 —— RocksDB 2017 — 把 LSM-Tree 的”空间放大”压到极低的工业经验
rocksdb-lsm —— LSM-tree 与 RocksDB — 把所有写都变成顺序写
selinger-1979 —— Selinger 1979 — 基于代价的查询优化
sequel-1974 —— SEQUEL 1974 — 让数据库”听懂”近似英语的查询
silt-2011 —— SILT — 0.7 字节内存索引一条记录的 flash 键值存储
skip-list-1990 —— Skip List — 用抛硬币代替平衡树
sqlite-2022 —— SQLite — 嵌入式数据库 30 年怎么活下来的
system-r-1976 —— System R 1976 — 第一个跑起来的关系数据库