几乎所有后端工程师都"知道"数据库用 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，而不是比较次数 |
视频开头就抛出了一个被绝大多数教程跳过的数字：内存访问和磁盘访问之间的延迟差距是 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 场景才适合哈希，因为它根本不需要顺序。
这是视频里最有冲击力的一段，也是大多数人真正卡住的地方。平衡二叉树查找是 O(log₂ N)，理论上足够好，为什么不行？
问题出在"每访问一层就要读一次磁盘"上。一个节点在二叉树里只存一个键和两个指针，体积极小，但数据库为了对齐磁盘块，至少要给它分配一个完整的页（通常 4–16KB）。于是一个 4KB 的磁盘页里，99% 的空间是空的，只装着一个键。对 10 亿行数据，log₂(10⁹) ≈ 30 层，意味着一次点查要做 30 次随机磁盘读取。按 SSD 每次 100μs 算，光索引遍历就要 3 毫秒——而且这还只是找到一行。
更深的问题是浪费：磁盘最讨厌的就是"读了一大块，只用了一点点"。二叉树把宝贵的页空间利用率压到 1% 以下，等于每一次出差都只取回一张便签纸。视频用一个直白的对比点醒你：树越高，磁盘读得越多；要让树变矮，就让每个节点装下尽可能多的键。
我的延伸：这也是为什么面试题里"数据库索引为什么不用红黑树"的标准答案不该停在"红黑树太高"——准确的答案是"红黑树的节点度数太低，导致树太高，从而磁盘 I/O 太多"。度数（fanout）才是关键变量，高度只是它的结果。
顺着上一节的逻辑，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 树和 B+ 树，视频专门做了区分，这是实战中真正影响性能决策的细节。
普通 B 树的每个节点都既存键、也存数据；而 B+ 树把所有真实数据（行 / 值）只放在叶子节点，非叶子节点只存键用于路由。这个看似微小的差别带来两个巨大收益：
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——但都不重要，重要的是它对"页"这个抽象的极致利用。
视频主要聚焦读取，但我要补上它没展开的另一半——B+ 树的写入并不便宜，这正是理解整个存储引擎谱系的关键。
每次插入都要把新键放进有序位置，这意味着大量随机写。当一个页装满，就要分裂（split）成两个页，触发写放大：为了插一行，可能要重写好几个 16KB 的页。对于写多读少的场景（日志、时序、IM 消息），B+ 树的随机写会成为瓶颈。
于是业界有了LSM 树（Log-Structured Merge Tree）——它把所有写入先追加到内存表，再批量、顺序地刷盘合并。顺序写比随机写快一两个数量级，所以 LSM 在写吞吐上碾压 B+ 树；代价是读取时要查多层 SSTable，需要布隆过滤器和压实（compaction）来兜底。
这就形成了一个漂亮的对偶，值得你画进脑子：
这正好对应你已经熟悉的那条"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+ 树"的整条推理链画出来——它本质上是一个不断淘汰候选结构、逼近"最少磁盘读"的过程：
flowchart TD
Goal["目标：一次查询<br/>尽量少碰磁盘页"]
Goal --> Q1{"候选结构"}
Q1 --> H["哈希表<br/>O(1) 等值查找"]
H -->|✗ 无法范围/排序/前缀| Reject1["淘汰：丢失顺序语义"]
Q1 --> B["二叉平衡树<br/>O(log₂ N)"]
B -->|✗ 一个节点只存 1 键<br/>页空间浪费 99%<br/>10亿行 = 30层 = 30次读盘| Reject2["淘汰：树太高<br/>磁盘 I/O 太多"]
Q1 --> BT["B 树<br/>节点都存数据"]
BT -->|✗ 非叶节点背数据<br/>扇出不极致<br/>范围扫描要回爬| Reject3["半淘汰：扇出与范围均不优"]
Q1 --> BPT["B+ 树"]
BPT --> A1["数据全在叶子"]
BPT --> A2["非叶节点只存键 → 扇出↑<br/>树高↓ → 10亿行仅 3-4 层"]
A2 --> A3["叶子双向链表<br/>范围/ORDER BY 横向走"]
A1 --> Win["✓ 一次点查仅 3-4 次读盘<br/>缓冲池常驻后仅 1-2 次"]
Reject1 --> BPT
Reject2 --> BPT
Reject3 --> BPT
Win --> Contrast{"写多了怎么办？"}
Contrast -->|读优先 就地更新| RO["B+ 树<br/>InnoDB/PG/Oracle"]
Contrast -->|写优先 顺序追加合并| WO["LSM 树<br/>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，砍掉没人用的索引——这是"少出差"哲学的反面应用：减少无用的维护开销。
pageinspect 扩展能让你亲眼看到 8KB/16KB 页里键的排列，把抽象的 B+ 树变成可触摸的字节。数据库选 B+ 树，不是因为它比谁都聪明地比较数据，而是因为它把每一次昂贵的磁盘"出差"都压到了最少——索引的全部秘密，就是让树矮到只够放进三层内存、外加一次真正的读盘。
本文由「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 等场景全覆盖。