# 路牌不带货：B+树三四层装下百亿 ## 导语 如果你写过几年后端，多半听过这条经验："查询慢？加个索引。"——然后你 `CREATE INDEX`，查询从 3 秒变成 3 毫秒，仿佛施了魔法。但很少有人追问：索引到底是什么？它为什么能让查找"瞬间"完成？而那些"加了索引反而更慢""索引没用上"的诡异 bug，又源自哪里？ Hussein Nasser（后端工程领域最有影响力的 YouTuber 之一，频道订阅近 50 万）这期 **"B-tree vs B+ tree in Database Systems"**，没教你怎么写 SQL，而是掀开数据库引擎的引擎盖，给你看里面那棵"看不见的树"。他要回答的核心问题是：为什么 MySQL、PostgreSQL、SQL Server、Oracle——几乎所有主流关系型数据库——都把同一种数据结构（B+ 树）当作索引的底座，而把它的"前辈" B 树无情抛弃？ 这期视频值得看，不是因为它讲了 B+ 树，而是因为它讲清了一个被大多数人误读的事实：**索引之所以快，不是因为"树"，而是因为"树很矮"——而树之所以矮，是因为它的每一层都被刻意设计成了不带货的"纯路牌"。** 这篇文章会在视频的基础上，把这道"小学算术题"算给你看，并补上 Hussein 来不及展开的 InnoDB 实现细节、回表代价和写放大账单。 ## 视频背景卡片 | 项目 | 内容 | |------|------| | 视频标题 | B-tree vs B+ tree in Database Systems | | 频道 | Hussein Nasser（@hnasr） | | 频道订阅 | 约 49.3 万 | | 时长 | 约 15 分钟（聚焦型长讲解） | | 播放量 | 频道为头部后端工程频道（精确播放量因限流未能核实） | | 核心主题 | 为什么数据库用 B+ 树而非 B 树；B+ 树的内部节点是纯路由键，数据只存叶子 | ## 核心内容拆解 ### 一、索引不是魔法，是"排好序的副本" 视频一开始，Hussein 先打掉一个误解：很多人以为索引是数据库"加速"原始表的方式，好像给表装了个涡轮增压。真相是——**索引根本不是表的一部分，它是一份独立的、按某个字段排好序的"数据副本"。** 想象一本 1000 页的字典，正文按"收录顺序"乱排，你想查"apple"只能从第 1 页翻到第 1000 页（这就是全表扫描，`full table scan`）。如果你在最后附一个按字母排序的目录，告诉你"apple 在第 837 页"，你只需要先查目录、再翻一次页——目录就是索引。 这个比喻揭示了索引的三个本质代价，Hussein 没有直接说，但我想点破： 1. **占空间**：目录本身要印几十页，索引也要额外占磁盘。一个表加 10 个索引，存储可能翻几倍。 2. **写变慢**：每次正文新增一个词，目录就要重新插入并保持有序——这就是后面要讲的"写放大"。 3. **它只对"建了索引的那一列"有用**：你按字母排了目录，想按"页数多少"查，目录帮不上忙。 所以"加索引"本质上是一个**用存储和写入成本，换取查询速度**的交易。没有免费午餐——这是理解后续一切的底色。 ### 二、B 树 vs B+ 树：数据库为什么抛弃了 B 树 既然索引要"有序"，那为什么不直接用二叉搜索树、红黑树、跳表？Hussein 给出的关键答案是两个字：**磁盘**。 内存里，二叉树挺好的。但数据库的数据动辄几个 GB 到几 TB，不可能全放进内存，必须存在磁盘上。磁盘的致命弱点是：**随机读一次（一次 I/O）非常慢**（机械盘要移动磁头，SSD 也要跨页），慢到和读一个连续块差好几个数量级。所以最优策略是：**每次 I/O 多读一点（一个"页"/page），把"树的层数"压到最少**——层数越少，磁盘读的次数越少。 二叉树每个节点只有 2 个孩子，树太高，10 亿条数据要读约 30 层——也就是 30 次磁盘 I/O，不可接受。于是有了 **B 树（B-tree）**：每个节点可以有很多个孩子（m 叉），把一棵又高又瘦的树压成又矮又胖。 但数据库最终普遍选择了 **B+ 树（B-plus tree）**，而不是 B 树。Hussein 在视频里反复强调的关键差异是： > **B 树：数据和键可以出现在任何节点（包括非叶子节点）。** > **B+ 树：数据只出现在叶子节点；非叶子（内部）节点里只有键和子节点指针，一个数据都不存。** 这一句差异，决定了数据库的命运。 ### 三、内部节点是"纯路牌"：fanout 如何决定树高 这是整期视频最反直觉、也最值钱的洞察，我把它单独拎出来讲透。 大多数人脑中的"树"，每个节点都挂着真实的数据（值、记录）。但 B+ 树偏偏不让内部节点带货——**内部节点里那些键，不是为了"被查到"，而是为了"指路"。** 它们是一块块"路牌"：告诉你"你要找的值，往左走还是往右走"。真正的货物（行数据），全部压在最底层的叶子里。 为什么这个设计如此精妙？因为**节点的容量是固定的（一个磁盘页，比如 InnoDB 默认 16KB）**。一个内部节点如果不带货，只放"键 + 子页指针"，每条记录就非常小——InnoDB 里子页指针 6 字节，加一个 Bigint 主键 8 字节，一条才 14 字节。于是： > **一个 16KB 的页，能塞下约 16384 ÷ 14 ≈ 1170 个路牌。** 也就是说，一个内部节点能分出 **1170 个叉**。这个数字叫 **fanout（扇出）**。Hussein 强调的核心就在这里：**fanout 越大，树越矮。** 因为每一层都把数据"摊平"成了 1170 份，三下五除二就能定位到任意一条记录。 如果是 B 树，内部节点还要塞数据，每个键后面跟着一大坨行记录，一个页只能放几十个键，fanout 骤降，树立刻变高——磁盘 I/O 翻倍。这就是 B 树"败给"B+ 树的根本原因：**为了榨干每一个页的指路能力，必须让内部节点彻底卸货。** ### 四、三四层装下百亿：那道小学算术题 把上面的数字乘起来，就得到数据库圈那道著名的算术题，Hussein 在视频里算过，我用 InnoDB 的真实参数替你重算一遍： - 假设每行数据约 1KB，那么一个 16KB 的**叶子页**大约放 **16 行**。 - 一个**内部页**放 **1170 个路牌**（子页指针）。 - **第 1 层（根）**：1 个页，1170 个路牌 → 指向 1170 个下层页。 - **第 2 层**：1170 个内部页，共 1170 × 1170 ≈ **136 万**个路牌 → 指向 136 万个叶子页。 - **第 3 层（叶子）**：136 万个叶子页 × 16 行 ≈ **2189 万行**。 - **第 4 层**：1170 × 1170 × 1170 × 16 ≈ **256 亿行**。 结论震撼又朴素：**一棵只有 3～4 层的 B+ 树，就能装下 2000 万到 256 亿行数据。** 而每一次按主键查找，只需要从根走到叶——**最多 3～4 次磁盘 I/O**。对 256 亿行数据，你只需读 4 个页。 这就是为什么所有数据库都死守 B+ 树：它把"层数 = I/O 次数"这个最贵的指标，压缩到了一个近乎常数（3～4），与数据总量几乎无关。无论你的表是 10 万行还是 100 亿行，单条主键查询的成本都稳如老狗。红黑树要 30+ 次比较，B 树要 5～6 次 I/O，而 B+ 树永远只要 3～4 次。 ### 五、叶子节点"手拉手"：范围查询为什么快 如果 B+ 树只是"矮"，那还不足以统治数据库世界。Hussein 在视频里点出的第二个杀手特性是：**B+ 树的所有叶子节点，用链表串了起来（在 InnoDB 里是双向链表）。** 为什么这个设计至关重要？想想这两类查询： - **点查询**（point query）：`WHERE id = 837`。从根走 3～4 层到叶子，一步到位。 - **范围查询**（range query）：`WHERE id BETWEEN 100 AND 500`，或 `ORDER BY created_at LIMIT 20`。 对范围查询，B 树会很尴尬：你要找 100～500 之间所有值，可能散落在树的各个角落，得反复从根往下走，I/O 次数爆炸。而 B+ 树优雅得多：先定位到 id=100 的那个叶子页，然后**沿着叶子之间的链表，一路向右顺藤摸瓜**，把 100→500 之间的所有叶子页顺序读出来。 更妙的是：**叶子页在物理上往往被尽量分配在相邻的磁盘块**（顺序 I/O 比随机 I/O 快 10～100 倍）。于是范围查询、`ORDER BY`、`LIMIT` 分页——这些互联网应用里 90% 的真实查询——都被这种"叶子手拉手 + 顺序读"吃得死死的。B 树做不到，因为它的数据散在每一层，没有这种"叶子连成一片"的结构。 ### 六、聚集索引 vs 二级索引：一次查询可能要爬两棵树 这是 Hussein 视频里点到、但很多中文资料没讲透的进阶点，我帮你补全（这部分是我的延伸，视频未详述）。 在 InnoDB 里，**表本身就是一棵 B+ 树**，叫**聚集索引（clustered index）**，按主键排序，叶子页里存的是**完整的一行数据**。也就是说，InnoDB 的表 = 主键索引，数据物理上就"长在"主键这棵树的叶子上（这种表叫 index-organized table）。 但你在其他列（比如 `email`、`user_id`）上加的索引，叫**二级索引（secondary index / non-clustered index）**。关键细节来了：**二级索引的叶子页里，存的不是完整行数据，而是"被索引列的值 + 主键值"。** 于是当你执行 `SELECT * FROM users WHERE email = 'x@y.com'`，且 email 上有二级索引时，发生的是**两棵树的攀爬**： 1. 先在 email 的二级索引 B+ 树里，走 3～4 层，找到叶子，拿到主键值（比如 `id = 837`）。 2. 再拿着 `id = 837`，回到聚集索引这棵树，再走 3～4 层，把完整行捞出来。 这个"回主键树取数据"的动作，中文圈叫**回表（bookmark lookup）**。它意味着一次查询可能要 **2 倍的 I/O**。这就是为什么有"覆盖索引"（covering index）这种优化：如果你的查询只需要 email 和 id 两列，而二级索引叶子页里正好就有这两列，数据库就**不用回表**，直接返回——性能直接砍半。这是面试高频、生产高频的实战知识。 ### 七、读得快是因为写得慢：索引的隐性账单 回到第一节埋下的伏笔。Hussein 在视频后半段会提醒：B+ 树给你的"3～4 次 I/O 查询"，是有代价的——代价就是**写放大（write amplification）**。 每一次 `INSERT`/`UPDATE`/`DELETE`，数据库不仅要改聚集索引，还要维护**每一棵相关的二级索引 B+ 树**。因为索引必须时刻保持有序，一个新值插入，可能触发： - 叶子页满了要**分裂（split）**成两个页； - 内部节点路牌要相应更新； - 甚至连锁引起上层节点分裂，一路冒泡到根。 这就是为什么**一个表上的索引越多，写入越慢**。我见过一个表加了 8 个索引，写入吞吐直接掉到原来的 1/5。更隐蔽的是 `UPDATE`：哪怕你只改一个非索引列，如果这个列参与了某个索引，那棵索引树也要更新；而 `UPDATE` 一个被索引的列，等于"删旧值 + 插新值"，在 B+ 树里是两次定位 + 可能的分裂。 所以 Hussein 真正想传递的元洞察是：**索引是建立在你对这张表"读写比"判断之上的一笔投资。** 读多写少的表（如配置表、字典表、日志查询表），多加索引划算；写多读少的表（如埋点、计数器、消息流水），每加一个索引都是给写入性能放血。盲目 `CREATE INDEX`，和盲目吃药一样危险。 ### 八、Hussein 的真正洞察：没有银弹，只有读写比 把整期视频串起来，Hussein 想说的其实不是"B+ 树好"，而是**所有数据结构都是取舍，B+ 树是"读优化"路线的极致**。与之相对的，是另一条"写优化"路线——**LSM 树（Log-Structured Merge Tree）**，被 Cassandra、HBase、RocksDB、LevelDB 采用。LSM 树把写入先丢进内存的 memtable，再批量、顺序地刷成磁盘上的 SSTable，写入飞快，但读取时要查多层 SSTable，读放大严重。 这是一对镜像： - **B+ 树**：读快（3～4 次 I/O），写慢（要原地更新 + 维持有序 + 可能分裂）。适合**读多写少、对点查和范围查都敏感**的场景（绝大多数 OLTP 业务库）。 - **LSM 树**：写快（追加写），读慢（要合并多层）。适合**写多读少、海量数据**的场景（时序、日志、宽列存储）。 Hussein 没有下"B+ 树更好"的结论——一个合格的后端工程师，不该问"哪个更好"，而该问"我的读写比是什么、我的查询模式是什么、我能容忍多大的写放大"。这才是这期视频的真正价值：它不是教你一个数据结构，而是教你**用"读写比 + 放大代价"这把尺子，去丈量所有存储引擎的设计选择**。 ## 知识结构图 ```mermaid flowchart TD R["🟦 根节点 Root（内部页）
只存【键 + 子页指针】
★纯路牌·不带货★"] R -->|1170 叉 fanout| I1["内部节点
键 + 指针
无数据"] R -->|1170 叉 fanout| I2["内部节点
键 + 指针
无数据"] I1 --> L1["🍃 叶子页
键 + 行数据"] I1 --> L2["🍃 叶子页
键 + 行数据"] I2 --> L3["🍃 叶子页
键 + 行数据"] I2 --> L4["🍃 叶子页
键 + 行数据"] L1 <-. 双向链表 .-> L2 L2 <-. 双向链表 .-> L3 L3 <-. 双向链表 .-> L4 R -.- M1["每页 16KB ÷ 14B ≈ 1170 路牌
→ 树极矮"] L1 -.- M2["叶子手拉手
→ 范围查询顺序读"] L1 -.- M3["3~4 层 = 3~4 次磁盘 I/O
装下 2000 万~256 亿行"] classDef internal fill:#e8f0fe,stroke:#4285f4,stroke-width:2px; classDef leaf fill:#e6f4ea,stroke:#34a853,stroke-width:2px; classDef note fill:#fff8e1,stroke:#f9a825,stroke-dasharray:5 5; class R,I1,I2 internal; class L1,L2,L3,L4 leaf; class M1,M2,M3 note; ``` ## 实战启示 **1. 加索引前，先算三笔账。** 别再无脑 `CREATE INDEX`。先问：这列的**读写比**是多少？查询是**等值查询**还是**范围查询**？这一列是否经常和其他列**一起被查询**（能不能组成联合索引 / 覆盖索引）？三笔账算清，再决定加不加、加几个。 **2. 善用 `EXPLAIN`，别靠玄学。** 执行计划里看两件事：`type` 字段是不是 `ref/range/eq_ref`（走了索引）还是 `ALL`（全表扫描）；`Extra` 里有没有 `Using index`（覆盖索引，免回表）或 `Using filesort`（索引没帮上排序，要警惕）。一个 `ALL` 就意味着你加的索引没被用上——可能是查询里对列用了函数（`WHERE YEAR(create_time)=...`）、用了左模糊（`LIKE '%abc'`）、或隐式类型转换，这些都会让 B+ 树"失效"，必须重写查询。 **3. 写多场景，慎用索引；考虑 LSM 引擎。** 如果你的业务是写密集（IoT 埋点、订单流水、监控指标），与其堆索引，不如考虑换存储：时序数据库（InfluxDB、TDengine）或基于 LSM 的引擎（RocksDB、ScyllaDB）。理解了 B+ 树 vs LSM 的读写镜像，你才知道"为什么 TimescaleDB 和 InfluxDB 用不同的底层"。 **4. 联合索引的"最左前缀"是 B+ 树的直接推论。** 联合索引 `(a, b, c)` 在 B+ 树里是按 a→b→c 排序的，所以 `WHERE a=? AND b=?` 能用，`WHERE b=? AND c=?` 用不上（因为没有 a，无法在第一层路牌定位）。这不是死记硬背的规则，而是"树是按这个顺序排列的"的必然结果——理解了结构，规则自然成立。 **5. 认清"回表"代价，优先设计覆盖索引。** 高频查询语句，尽量让二级索引的叶子页就包含所需列，避免回表（省一半 I/O）。这对高并发接口是立竿见影的优化。 ## 延伸学习路径 1. **《Designing Data-Intensive Applications》（DDIA，Martin Kleppmann）第 3 章"存储与检索"**——公认最清晰的 B+ 树与 LSM 树对比，作者在 YouTube 上也有完整大学授课录像。 2. **Hussein Nasser《Fundamentals of Database Engineering》**（Udemy 课程 + 频道免费视频）——本视频所属体系，深入 ACID、MVCC、索引、复制，是后端工程师的数据库通识必修。 3. **CMU 15-445《Database Systems》（Andy Pavlo，YouTube 全程免费）**——学术界最权威的数据库系统公开课，B+ 树的并发控制、页面分裂讲得极其透彻。 4. **MySQL 官方手册 §17.6.2.2 "The Physical Structure of an InnoDB Index"**——一手权威资料，直接确认 16KB 页、叶子页存索引记录等实现细节。 5. **Wikipedia: B+ tree / Write amplification**——快速核对 fanout、放大系数等数学定义，链接到原始论文（Bayer & McCreight 1972）。 ## 一句话总结 B+ 树之所以能让数据库"3～4 次磁盘 I/O 搞定任意一条记录"，靠的不是树，而是把内部节点全部榨成不带货的"纯路牌"、把 fanout 撑到上千——理解了"读写比 + 写放大"这把尺子，你才算真正懂了索引。 ## 参考来源 1. [B-tree vs B+ tree in Database Systems — Hussein Nasser (YouTube)](https://www.youtube.com/watch?v=UzHl2VzyZS4) — 本文分析的核心视频 2. [How Many Rows Can an InnoDB B+ Tree Store? A Deep Dive — BestHub](https://www.besthub.dev/articles/how-many-rows-can-an-innodb-b-tree-store-a-deep-dive-aac9a8b86510) — 提供 1170×1170×16≈2189 万行的算术推导 3. [MySQL 8.4 Reference Manual §17.6.2.2 The Physical Structure of an InnoDB Index](https://dev.mysql.com/doc/refman/8.4/en/innodb-physical-structure.html) — 确认 16KB 默认页、索引记录存于叶子页 4. [Understanding the B+ Tree in InnoDB: The Backbone of MySQL Performance — duthaho](https://duthaho.substack.com/p/understanding-the-b-tree-in-innodb) — InnoDB B+ 树实现与查询路径详解 5. [B+ Trees vs B-Trees: How Database Indexing Really Works — Ahmed N. Abdeltwab](https://ahmed-n-abdeltwab.github.io/blog/2025/04/19/b-plus-trees-database-indexing.html) — 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 等场景全覆盖。