# 不比谁快：B+树只为少读一次磁盘
## 为什么这个视频值得你花 30 分钟
几乎所有后端工程师都"知道"数据库用 B+ 树做索引。但你若追问一句"为什么不直接用哈希表？为什么不是红黑树？为什么是 B+ 树而不是 B 树？"——十个人里有九个答不上来。我们习惯把 B+ 树当成一条"数据库就是这么做"的公理去背诵，却从没真正理解它要解决的**那个唯一的问题**。
Arpit Bhayani 的这支视频《Why do databases store data in B+ trees?》做了件很少讲解者愿意做的事：它不先讲 B+ 树长什么样，而是先把你脑子里的误区拆掉。视频最核心的论点可以用一句话概括——**数据库选 B+ 树，根本不是因为它"比较快"，而是因为它能把你访问磁盘的次数压到最少**。这听起来像是文字游戏，但当你真正看懂存储层次之间的延迟鸿沟，会发现整个索引设计的逻辑瞬间自洽：我们一直在优化一个 CPU 根本不关心的东西。
这篇解读会沿着视频的思路往下挖，补上视频没展开的延迟数字、扇出（fanout）的数学、B 树与 B+ 树那一个"+"号背后的工程取舍，并把它和你已经熟悉的 LSM 树放在一起对照——你会发现，读写优化的两条路线，其实在回答同一个问题。
## 视频背景卡片
| 项目 | 内容 |
|------|------|
| 视频标题 | Why do databases store data in B+ trees? |
| 频道 | Arpit Bhayani（知名系统架构博主，前 Google 工程师） |
| 时长 | 29 分 43 秒 |
| 播放量 | 约 10 万 + |
| 发布日期 | 2023 年 3 月 19 日 |
| 核心主题 | 数据库为何选择 B+ 树——真正的瓶颈是磁盘 I/O，而不是比较次数 |
## 核心内容拆解
### 一、被掩盖的前提：瓶颈从来不在 CPU
视频开头就抛出了一个被绝大多数教程跳过的数字：**内存访问和磁盘访问之间的延迟差距是 10⁵ 量级**。这是理解后面所有内容的地基，所以我们把它说清楚。
L1 缓存访问大约 **1 纳秒**，主存（DRAM）访问大约 **100 纳秒**，而一次 SSD 的随机读取大约 **100 微秒**（10 万纳秒），机械硬盘（HDD）更是要 **10 毫秒**（1000 万纳秒）。换句话说，CPU 去主存取一次数据，像是从书桌上伸手拿本书；CPU 去硬盘取一次数据，则是安排一趟出差——CPU 在这趟出差的"路上"可以做完上百万次加减法。
视频反复强调（这是原话级别的核心论点）：**当我们讨论"索引快不快"时，省下一次磁盘读取，价值远大于省下一千次内存里的比较。** 所以数据库索引设计的目标函数，根本不是"让算法在 Big-O 意义上更优"，而是"**让一次查询物理上碰到的磁盘页（page / block）数量最少**"。每一次磁盘 I/O 都要付出一次出差的代价，索引的全部存在意义，就是减少出差次数。
> 这是我的延伸：很多人把"索引让查询变快"理解成"索引让数据库更聪明地比较数据"。方向反了。索引让查询变快，是因为它让数据库**少出差**。一旦你把心智模型从"比谁算得快"切换成"比谁跑腿少"，后面 B+ 树、LSM 树、缓冲池的所有设计就全都串起来了。
### 二、为什么不直接用哈希表？
既然目标是"一次命中"，哈希表看起来是完美答案——O(1) 的查找复杂度，听起来吊打一切树结构。视频专门停下来否定了这个直觉，理由非常现实。
哈希表的致命伤不在速度，而在**语义**：它只能做**精确匹配（equality）**查询。`WHERE id = 42` 没问题，但 `WHERE id > 42`、`WHERE name LIKE 'A%'`、`ORDER BY created_at`、`BETWEEN`、范围聚合——哈希结构一概做不了。哈希函数把相邻的键打散到完全无关的桶里，**数据的顺序信息被彻底抹掉**。
而真实业务里，排序、范围、前缀匹配恰恰是最高频的查询模式。时间线要按时间倒序、排行榜要按分数取前 N、报表要按区间聚合。一个只支持等值查询、无法遍历的索引结构，在 OLTP/OLAP 场景里几乎是废的。所以哈希索引（比如 MySQL Memory 引擎、PostgreSQL 早期的 hash index）始终是配角，绝大多数生产数据库的主索引都拒绝它。
> 补充背景：PostgreSQL 从 10 版本开始给 hash index 做了 WAL 支持使其可崩溃恢复，但官方文档依旧建议"通用场景用 B-tree"。Redis 这种纯 KV 场景才适合哈希，因为它根本不需要顺序。
### 三、为什么不选二叉平衡树（BST / AVL / 红黑树）？
这是视频里最有冲击力的一段，也是大多数人真正卡住的地方。平衡二叉树查找是 O(log₂ N)，理论上足够好，为什么不行？
问题出在**"每访问一层就要读一次磁盘"**上。一个节点在二叉树里只存一个键和两个指针，体积极小，但数据库为了对齐磁盘块，至少要给它分配一个完整的页（通常 4–16KB）。于是**一个 4KB 的磁盘页里，99% 的空间是空的，只装着一个键**。对 10 亿行数据，log₂(10⁹) ≈ **30 层**，意味着一次点查要做 **30 次随机磁盘读取**。按 SSD 每次 100μs 算，光索引遍历就要 3 毫秒——而且这还只是找到一行。
更深的问题是**浪费**：磁盘最讨厌的就是"读了一大块，只用了一点点"。二叉树把宝贵的页空间利用率压到 1% 以下，等于每一次出差都只取回一张便签纸。视频用一个直白的对比点醒你：**树越高，磁盘读得越多；要让树变矮，就让每个节点装下尽可能多的键。**
> 我的延伸：这也是为什么面试题里"数据库索引为什么不用红黑树"的标准答案不该停在"红黑树太高"——准确的答案是"红黑树的**节点度数太低**，导致树太高，从而磁盘 I/O 太多"。度数（fanout）才是关键变量，高度只是它的结果。
### 四、B+ 树的精髓：把一个磁盘页撑满
顺着上一节的逻辑，B+ 树的设计哲学呼之欲出：**既然每次 I/O 都要付一个页的代价，那就让一个页里塞进尽可能多的键，把树的每一层"压扁"。**
一个 16KB 的页，如果每个索引项大约 14 字节，一个节点就能装下约 **1000 个键**。于是扇出（fanout）≈ 1000，10 亿行的树高变成 log₁₀₀₀(10⁹) ≈ **3 层**，一万亿（10¹²）行也才 **4 层**。一次点查从二叉树的 30 次磁盘读取，骤降到 **3–4 次**。这就是 B+ 树"看起来魔法般快"的全部秘密——它没有让比较变聪明，它只是让**每一次昂贵的磁盘出差都满载而归**。
视频在这里反复用一个比喻（值得记住）：B+ 树不是一棵"更聪明的搜索树"，而是一棵"**为磁盘页尺寸量身定做的扁平目录**"。你买的不是更快的算法，而是更高的"出差性价比"。
> 数据补充：实际生产中，InnoDB 默认页大小 16KB，PostgreSQL 默认 8KB。InnoDB 的非叶子节点若存主键（聚簇索引），扇出通常在数百到上千，这就是为什么 InnoDB 表即便有几亿行，绝大多数查询也只需要 3–4 层就触达数据。
### 五、B+ 树 vs B 树：那一个 "+" 号值多少钱
很多人分不清 B 树和 B+ 树，视频专门做了区分，这是实战中真正影响性能决策的细节。
普通 B 树的**每个节点都既存键、也存数据**；而 B+ 树把**所有真实数据（行 / 值）只放在叶子节点**，非叶子节点**只存键用于路由**。这个看似微小的差别带来两个巨大收益：
1. **非叶子节点更"瘦"、更密**——因为不背数据载荷，同样大小的页能塞进更多键 → 扇出更高 → 树更矮 → 磁盘读得更少。
2. **叶子节点用双向链表串起来**——这让范围查询（`WHERE id BETWEEN a AND b`）、`ORDER BY`、limit 扫描变得极便宜：定位到起点叶子后，**顺着链表横向走**即可，根本不用回头爬树。这是 B 树做不到的，因为 B 树的数据散落在每一层。
那个 "+" 号的本质，就是**"数据下沉到叶子 + 叶子横向成链"**这两条工程约定。它牺牲了一点点的写入复杂度（要维护链表和分裂逻辑），换来的是范围扫描和扇出的双重胜利——而这正是数据库 90% 查询最需要的。
> 冷知识延伸：B 树的"B"到底代表什么，至今没有官方答案。发明者 Rudolf Bayer 和 Edward McCreight 1970 年在波音科研实验室（Boeing Scientific Research Labs）提出，McCreight 后来调侃说"你越认真琢磨 B 代表什么，就越懂 B 树"。候选答案有 Boeing、Bayer、Balanced、Broad——但都不重要，重要的是它对"页"这个抽象的极致利用。
### 六、写入的代价：写多了就得换 LSM 树
视频主要聚焦读取，但我要补上它没展开的另一半——**B+ 树的写入并不便宜**，这正是理解整个存储引擎谱系的关键。
每次插入都要把新键放进**有序**位置，这意味着大量随机写。当一个页装满，就要**分裂（split）**成两个页，触发写放大：为了插一行，可能要重写好几个 16KB 的页。对于写多读少的场景（日志、时序、IM 消息），B+ 树的随机写会成为瓶颈。
于是业界有了**LSM 树（Log-Structured Merge Tree）**——它把所有写入先追加到内存表，再批量、顺序地刷盘合并。顺序写比随机写快一两个数量级，所以 LSM 在写吞吐上碾压 B+ 树；代价是读取时要查多层 SSTable，需要布隆过滤器和压实（compaction）来兜底。
这就形成了一个漂亮的对偶，值得你画进脑子：
- **B+ 树 = 读优先**：数据就地更新、有序可范围扫，读快、写有放大。MySQL/InnoDB、PostgreSQL、Oracle、SQL Server 走这条线。
- **LSM 树 = 写优先**：写入顺序追加、读时合并，写快、读需多跳。Cassandra、HBase、RocksDB、LevelDB 走这条线。
> 这正好对应你已经熟悉的那条"LSM 树从不真的修改"的洞察——它和 B+ 树不是谁取代谁，而是同一条读写权衡曲线上相反的两端。视频讲的是读端，那条讲的是写端，拼起来才是完整的存储引擎图景。
### 七、缓冲池的魔法：四层树常常只读一两层
最后补一个视频点到但没说透的现实因素：**你算出来的"3–4 次磁盘读取"，在生产里往往只剩 1–2 次**，原因是缓冲池（buffer pool / page cache）。
B+ 树的根节点和上面几层几乎永远驻留在内存里——它们体积小、被访问频率极高，天然是热数据。所以一次真实的点查，命中的常常是：根节点（内存）→ 第二层（内存）→ 第三层（内存）→ 叶子（可能要读盘）。也就是说，那 3–4 次理论上要出差的页，有 2–3 次其实"出差"到内存就返回了。这也是为什么即使表有数十亿行，热查询依然能在亚毫秒级返回。
但请注意这个机制的**不对称风险**：冷数据查询、首次访问、或者缓冲池被冲刷时，那"理论 4 次"会一次性全部变成真实磁盘读，延迟可能从 0.5ms 跳到 5ms。这也是 DBA 们对 buffer pool hit ratio、对预热、对内存大小如此敏感的根本原因——**B+ 树的快，建立在一部分树常驻内存的假设上**。
## 知识结构图
下面这张图把"为什么是 B+ 树"的整条推理链画出来——它本质上是一个不断淘汰候选结构、逼近"最少磁盘读"的过程：
```mermaid
flowchart TD
Goal["目标：一次查询
尽量少碰磁盘页"]
Goal --> Q1{"候选结构"}
Q1 --> H["哈希表
O(1) 等值查找"]
H -->|✗ 无法范围/排序/前缀| Reject1["淘汰：丢失顺序语义"]
Q1 --> B["二叉平衡树
O(log₂ N)"]
B -->|✗ 一个节点只存 1 键
页空间浪费 99%
10亿行 = 30层 = 30次读盘| Reject2["淘汰：树太高
磁盘 I/O 太多"]
Q1 --> BT["B 树
节点都存数据"]
BT -->|✗ 非叶节点背数据
扇出不极致
范围扫描要回爬| Reject3["半淘汰：扇出与范围均不优"]
Q1 --> BPT["B+ 树"]
BPT --> A1["数据全在叶子"]
BPT --> A2["非叶节点只存键 → 扇出↑
树高↓ → 10亿行仅 3-4 层"]
A2 --> A3["叶子双向链表
范围/ORDER BY 横向走"]
A1 --> Win["✓ 一次点查仅 3-4 次读盘
缓冲池常驻后仅 1-2 次"]
Reject1 --> BPT
Reject2 --> BPT
Reject3 --> BPT
Win --> Contrast{"写多了怎么办？"}
Contrast -->|读优先 就地更新| RO["B+ 树
InnoDB/PG/Oracle"]
Contrast -->|写优先 顺序追加合并| WO["LSM 树
Cassandra/RocksDB"]
style Goal fill:#fff3cd,stroke:#856404
style Win fill:#d4edda,stroke:#155724
style Reject1 fill:#f8d7da,stroke:#721c24
style Reject2 fill:#f8d7da,stroke:#721c24
style Reject3 fill:#ffe0b2,stroke:#8a5a00
```
## 实战启示
**1. 看到 EXPLAIN 里的索引选择，心里要有"读盘次数"这把尺子。**
当你发现一个查询走了全表扫描而不是索引，不要只想到"缺索引"，而要问：这个查询**逻辑上要出几次差**？如果一个二级索引的选择性很低（大量重复值），数据库可能宁可全表扫也不走索引——因为走低效索引反而要做更多随机读 + 回表。理解了"读盘次数"，你才能真正读懂优化器的决策，而不是只会无脑 `CREATE INDEX`。
**2. 覆盖索引的本质，是省掉一次"回表出差"。**
在 InnoDB 里，二级索引的叶子存的是主键，找到后还要再去聚簇（主键）B+ 树里取完整行——这叫回表（bookmark lookup），等于**多一整次树遍历**。覆盖索引（covering index）把查询需要的列全放进二级索引的叶子，让查询在二级索引这一层就"出差完成"，不用回表。这不是优化技巧，这是对"每一次读盘都贵"的精算。下次你设计索引，先想清楚能不能把高频查询变成覆盖查询。
**3. 选存储引擎，先问读写比，再问一致性要求。**
如果你的负载是读多写少、需要强一致和事务、大量范围查询——B+ 树（InnoDB/PostgreSQL）几乎是无脑选择。如果是写多读少、可接受最终一致、海量数据低价值——LSM（RocksDB/Cassandra）更划算。这没有银弹，只有权衡曲线上你站的位置。理解 B+ 树和 LSM 是同一问题的两端，你就不会再问"哪个更好"，而是问"我的业务在曲线的哪一点"。
**4. 别把"用索引"当万能药。**
索引让读快，但每次写入都要维护所有相关索引的有序性（可能触发页分裂）。索引越多，写越慢、占空间越大。一个表建十几个索引、却只在两个列上查，剩下的索引纯粹在拖慢写入和吃磁盘。定期审视 `pg_stat_user_indexes` / `sys.schema_unused_indexes`，砍掉没人用的索引——这是"少出差"哲学的反面应用：**减少无用的维护开销**。
## 延伸学习路径
1. **Arpit Bhayani 频道其余"系统底层"系列** —— 同一作者关于 LSM 树、布隆过滤器、一致性哈希的讲解，正好和本视频构成存储引擎的完整拼图。强烈建议配套观看，理解读写权衡的全貌。
2. **《Database Internals》— Alex Petrov（O'Reilly, 2019）** —— 目前最系统的存储引擎与数据库架构入门书，B 树、LSM 树、页结构、WAL、压缩算法全部讲透，是工程实践和理论之间的最佳桥梁。
3. **CMU 15-445《Database Systems》公开课（Andy Pavlo）** —— 卡内基梅隆的数据库王牌课程，YouTube 全部免费，B+ 树的插入/分裂/并发控制（crabbing protocol）讲得极其扎实，配合本视频食用效果最佳。
4. **"The Ubiquitous B-Tree" — Douglas Comer（ACM Computing Surveys, 1979）** —— 经典综述论文，把 B 树家族一网打尽。读完你会明白为什么半个世纪的存储系统都没能绕开它。
5. **PostgreSQL / InnoDB 官方文档的"物理存储"章节** —— 直接看生产级实现：`pageinspect` 扩展能让你亲眼看到 8KB/16KB 页里键的排列，把抽象的 B+ 树变成可触摸的字节。
## 一句话总结
**数据库选 B+ 树，不是因为它比谁都聪明地比较数据，而是因为它把每一次昂贵的磁盘"出差"都压到了最少——索引的全部秘密，就是让树矮到只够放进三层内存、外加一次真正的读盘。**
## 参考来源
1. [Why do databases store data in B+ trees? — Arpit Bhayani](https://www.youtube.com/watch?v=09E-tVAUqQw) — 本文分析的核心视频
2. [Database Internals — Alex Petrov (O'Reilly)](https://www.databass.dev/) — 存储引擎权威著作，B 树与 LSM 树深度对照
3. [CMU 15-445 Database Systems — Andy Pavlo](https://15445.courses.cs.cmu.edu/) — B+ 树实现与并发控制的系统讲解
4. [The Ubiquitous B-Tree — Douglas Comer, ACM Computing Surveys 1979](https://dl.acm.org/doi/10.1145/356770.356776) — B 树家族经典综述
5. [PostgreSQL Documentation: Database Physical Storage](https://www.postgresql.org/docs/current/storage.html) — 生产级页结构与 B-tree 实现参考
---
> 本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵**爱卫生**（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。
> 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。
> [!tip] 51学通信知识星球
> **星主：爱卫生**（微信：gprshome201101）——公众号「51学通信」创办者，19 年通信行业运维与讲师经验，著有《GPRS网络信令实例详解》《EPC原理与实践》《5G核心网原理与实践》三本纸质书（各大电商平台有售）。
> **星球定位**：深耕 5G 核心网、IMS、NFV/AI、云原生等 ICT 领域，主打运维岗位与信令分析。
> **当前规模**：5200 篇主题 / 990 个回答，198 元/年。
> **加入福利**：加入星球后请加爱卫生微信，拉您进知识星球年度陪伴与答疑群——不限量回复您的各种问题，另有群内分享。
> **AI 加持**：51学通信知识星球已作为 skill 接入 WorkBuddy，使用 deepseek-4-flash 在海量星球帖子中精准找贴、找视频、找 FAQ 和案例，做总结、找文档和 PPT 等场景全覆盖。
