# 一亿行只需四次IO：B树为何统治数据库 ## 导语 每个程序员都听过"加个索引就好了"这句万灵药式的建议。但很少有人真正停下来想：**为什么是 B-tree？** 为什么不是教科书第一章就教你的二叉搜索树、红黑树、跳表，甚至是查一次 O(1) 的哈希表？Hussein Nasser 在《Database Indexing Explained (with PostgreSQL)》里做了一件大多数教程懒得做的事——他不满足于告诉你"索引让查询变快"，而是把镜头怼到磁盘这一层，让你亲眼看见：**数据库的性能瓶颈从来不是 CPU 比较，而是磁盘 I/O。** 一旦你接受了这个反直觉的前提，整个 B-tree 的设计就不再是"一个数据结构"，而是一份写给机械硬盘和 SSD 的情书。这篇文章我会把视频的核心论点拆开揉碎，再补上视频没展开的 B+ tree、聚簇索引、LSM tree 和写放大，让你看完之后，面对 `EXPLAIN ANALYZE` 的输出不再两眼一抹黑。 ## 视频背景卡片 | 项目 | 内容 | |------|------| | 视频标题 | Database Indexing Explained (with PostgreSQL) | | 频道 | Hussein Nasser | | 时长 | 约 18 分 19 秒 | | 播放量 | 约 39 万次（截至 2026 年） | | 核心主题 | 从磁盘 I/O 出发，解释数据库为何选择 B-tree，及 PostgreSQL 索引实践 | ## 核心内容拆解 ### 1. 没有索引的世界：顺序扫描有多贵 视频开场很直接——它先让你感受"没有索引"的痛。当你在一张上亿行的表里执行 `SELECT * FROM users WHERE email = 'x@y.com'`，数据库唯一能做的事就是**顺序扫描（Sequential Scan）**：从第一行读到最后一行，逐个比较。这是 O(n) 的操作，n 是行数。 这里的关键不是"O(n) 慢"，而是慢在哪。我延伸一下：CPU 比较一个字符串只需要纳秒级，但如果你那上亿行存在机械硬盘上，真正的时间被花在**等待磁头寻道**上——一次随机读取大约 10 毫秒，比 CPU 周期慢了六个数量级。视频的核心铺垫正在于此：**索引的全部意义，是把"必须读 n 次"压缩成"只读几次"。** 从 O(n) 到 O(log n)，看起来只是数学符号的变化，在磁盘世界里却意味着"扫一整张表"和"翻几页书"的天壤之别。 ### 2. 最大的反直觉：为什么不用二叉搜索树 这是全视频最该停下来思考的一段。视频指出，很多人下意识觉得：既然索引要支持快速查找和范围扫描，那用一棵平衡二叉搜索树（BST）或红黑树不就行了？查找 O(log₂ n)，完美。 **但这是把"内存思维"套到了"磁盘现实"上。** 我的延伸分析：在内存里，红黑树确实优秀，因为每个节点访问都是同一个数量级的延迟。可一旦树落到磁盘，问题就暴露了——二叉树每个节点只有两个子节点，意味着它"又高又瘦"。一亿行数据，一棵平衡二叉树的高度约为 log₂(10⁸) ≈ **27 层**。最坏情况下你要做 27 次磁盘读取，每次 10 毫秒，光寻道就要 270 毫秒。二叉树的"平衡"在 CPU 眼里是优势，在磁盘眼里是灾难。视频正是用这种落差，把读者推向 B-tree：**我们需要一棵"矮胖"的树。** ### 3. B-tree 的魔法：高扇出、页对齐、矮胖 B-tree（Rudolf Bayer 与 Ed McCreight 在 1970 年提出）的设计目标只有一个——**最小化磁盘访问次数**。它怎么做到的？靠两个关键决策。 第一是**高扇出（high fan-out）**。B-tree 的每个节点不是存一个键，而是存一整排键（几十到几百个），对应几百个子指针。这让树变得极度扁平：假设每个节点扇出 200，那么 log₂₀₀(10⁸) ≈ **3.5 层**，实际只需 3 到 4 层就能覆盖一亿行。从 27 次 I/O 降到 4 次，这就是 B-tree 的全部魔法。 第二是**页对齐（page-aligned）**。我的补充：操作系统和数据库都以"页（page）"为单位读写磁盘，PostgreSQL 默认页大小是 8KB。B-tree 巧妙地把一个节点设计成正好一个页的大小——读一个节点 = 读一页 = 一次 I/O，没有浪费。节点内的二分查找发生在内存里，几乎免费。**B-tree 本质上是把"树的高度"和"磁盘的页"做了一个精确的工程匹配。** 这是视频没有点透、但理解 B-tree 最重要的一层。 ### 4. 数据库真正用的是 B+ tree：叶子链表与范围查询 视频以 PostgreSQL 为例讲解，但我必须补充一个常被混淆的事实：**现代关系型数据库几乎都不用原始 B-tree，而是 B+ tree。** 差别在哪？原始 B-tree 的数据既存在内部节点也存在叶子节点；而 B+ tree 把所有实际数据**只放在叶子节点**，内部节点只存"键 + 指针"，纯粹当路标用。这带来两个巨大好处：其一，内部节点能塞下更多键，扇出更高，树更矮；其二，**所有叶子节点用双向链表串起来**。当你执行 `WHERE age BETWEEN 20 AND 30`，数据库先用树结构定位到 age=20 的叶子，然后**沿着链表线性扫描**到 age=30 即可，不需要再回到上层。范围查询因此和单点查找一样高效。MySQL 的 InnoDB、PostgreSQL 的默认索引、SQL Server，底层清一色是 B+ tree。这是任何想真正读懂执行计划的人都该知道的一层。 ### 5. 聚簇 vs 非聚簇：PostgreSQL 的堆表哲学 视频花了相当篇幅讲 PostgreSQL 特有的索引架构，这也是它比泛泛教程更值钱的地方。我梳理其逻辑：PostgreSQL 的表是一个**堆表（heap）**，行数据物理上按写入顺序乱堆着，索引本身**不存数据**，只存"键 → 行物理位置（CTID）"的映射。这意味着通过二级索引查到行之后，往往还要**回表（bookmark lookup）**一次去取真实数据。 这里有个常考的对比：MySQL InnoDB 的主键索引是**聚簇索引（Clustered Index）**——整行数据就物理上按主键排序存在 B+ tree 的叶子里，主键查询不需要回表；而非主键索引的叶子存的是主键值，查完还要再查一次主键树。**聚簇索引"表即索引"，二级索引"指回主键"。** PostgreSQL 选择了不同的哲学：表和索引分离，索引永远是二级的。两种设计各有取舍——聚簇索引主键查询快，但二级索引要绕一圈；堆表模型写更新更灵活，配合 MVCC（多版本并发控制）天然友好。视频把这些工程权衡摆出来，是它最有营养的部分。 ### 6. 索引不是免费的：写放大与选择性 视频后半段开始泼冷水，这也是我最欣赏它的地方——它不像营销号那样鼓吹"到处加索引"。**索引是有代价的。** 代价一：**写放大（write amplification）**。每插入、更新、删除一行，数据库不仅要改表，还要同步维护所有相关索引。一张表上有 5 个索引，一次写入可能触发 6 次页修改。这就是为什么 OLTP（高并发事务）系统要克制索引数量。 代价二：**选择性（selectivity）**。我的延伸：索引不是万能加速器。如果你给"性别"这种只有两三个值的列建索引，查询时索引可能扫出一半行，再逐个回表，比直接全表扫描还慢。数据库优化器会判断"索引是否划算"，不划算就弃用索引走顺序扫描——这就是为什么你建了索引却"没生效"。视频反复强调一个经验法则：**索引适合高选择性列**，即不同值多、重复少的列，比如 email、用户 ID。 ### 7. 超越 B-tree：PostgreSQL 的索引家族与 LSM tree B-tree 是默认答案，但不是唯一答案。视频在结尾带过了 PostgreSQL 的索引多样性，我把这部分展开。 PostgreSQL 一个表上可以挂多种索引：**Hash** 索引只支持等值查询、不支持范围，但更紧凑；**GIN**（Generalized Inverted Index）倒排索引，专为全文搜索和 JSONB 数组设计；**GiST** 适合地理空间（PostGIS）和范围类型；**BRIN**（Block Range Index）对海量、物理有序的时间序列数据极省空间。选对索引类型，本身就是一门手艺。 更大的格局：在写密集场景（日志、时序、Cassandra、RocksDB、LevelDB），业界用 **LSM tree（Log-Structured Merge-tree）** 替代 B-tree——它把随机写转成顺序写，牺牲一点读性能换极致的写吞吐。B-tree 擅长读、LSM 擅长写，这是数据库存储引擎最核心的两大流派分野。Martin Kleppmann 在《Designing Data-Intensive Applications》里把这层讲得最透。 ## 知识结构图 ```mermaid flowchart TD A["查询慢的根本原因
磁盘 I/O 是瓶颈，而非 CPU"] --> B["索引的目标
把 O(n) 压缩到 O(log n) 次磁盘读取"] B --> C["为什么不用二叉树/红黑树?"] C --> C1["又高又瘦: 1亿行 ≈ 27 层
≈ 27 次磁盘 I/O = 灾难"] B --> D["B-tree 的两个工程决策"] D --> D1["高扇出: 每节点存几百个键
树变得矮胖, 仅 3-4 层"] D --> D2["页对齐: 一个节点 = 一个磁盘页
读一个节点 = 一次 I/O, 零浪费"] D --> E["数据库实际用 B+ tree"] E --> E1["数据只在叶子节点
内部节点纯当路标"] E --> E2["叶子用双向链表串联
范围查询沿链表线性扫描"] E --> F["两种表存储架构"] F --> F1["聚簇索引 MySQL InnoDB
表即主键索引树, 主键查询免回表"] F --> F2["堆表 + 二级索引 PostgreSQL
索引存 键→CTID, 二级查询需回表"] D --> G["索引的代价"] G --> G1["写放大: 写一次要维护所有索引"] G --> G2["选择性: 低基数列建索引反而更慢"] E --> H["B-tree 之外"] H --> H1["PostgreSQL: Hash / GIN / GiST / BRIN"] H --> H2["写密集: LSM tree
RocksDB / Cassandra"] ``` ## 实战启示 理解了 B-tree，你才能真正用好它。给四条能立刻上手的行动指南。 **第一，让 `EXPLAIN ANALYZE` 成为肌肉记忆。** 别再凭感觉加索引。在 PostgreSQL 里，`EXPLAIN ANALYZE SELECT ...` 会告诉你执行计划用了 Index Scan、Bitmap Index Scan 还是 Seq Scan。如果发现走了 Seq Scan 而你以为有索引，问题通常出在选择性、函数包裹列或类型不匹配上。 **第二，警惕"索引失效"的经典陷阱。** `WHERE LOWER(email) = 'x'` 不会用上 `email` 上的普通索引，因为索引存的是原始值；要么建表达式索引，要么改成 `WHERE email = LOWER('x')`。`WHERE date_col::text = '2026-06-17'` 同样会因为类型转换放弃索引。 **第三，复合索引牢记最左前缀。** 索引 `(last_name, first_name)` 能服务 `WHERE last_name=?` 和 `WHERE last_name=? AND first_name=?`，但**不能**服务 `WHERE first_name=?`。把过滤性最强的列放最左。 **第四，拥抱覆盖索引（Covering Index）消灭回表。** 如果一个高频查询只用到几列，可以把这些列一起放进索引（PostgreSQL 用 `INCLUDE` 子句），查询直接从索引拿到全部数据，省掉昂贵的回表 I/O。这是把"4 次 I/O"进一步压到"2 次 I/O"的杀手锏。 最后一条心法：**索引是用写入成本换读取性能的契约。** 读多写少的列放手加，高并发写入的表要克制。一切权衡，回到"磁盘 I/O 是瓶颈"这个原点。 ## 延伸学习路径 1. **《Designing Data-Intensive Applications》** — Martin Kleppmann。第 3 章"存储与检索"把 B-tree 与 LSM tree 的对比讲得最透彻，是这领域的圣经。 2. **CMU 15-445 Database Systems** — Andy Pavlo 教授的公开课，B+ tree 实现与并发控制讲得极其硬核，B 站有字幕版。 3. **PostgreSQL 官方文档 · Indexes 章节** — 最权威的一手资料，涵盖 B-tree、Hash、GIN、GiST、BRIN 的选择指南。 4. **Spanning Tree《Understanding B-Trees: The Data Structure Behind Modern Databases》** — 同主题的高播放可视化视频（108 万次），动画补足本文的直觉。 5. **Hussein Nasser 频道** — 数据库/后端系统深度内容持续更新，本文分析的这条之外，其 MVCC、数据库事务系列同样值得追。 ## 一句话总结 B-tree 不是又一个数据结构，而是一份"把树的高度与磁盘的页精确对齐"的工程契约——它让一亿行数据只需三四次 I/O，这是整个数据库世界能跑得快的底层原因。 ## 参考来源 1. [Database Indexing Explained (with PostgreSQL) — Hussein Nasser](https://youtu.be/-qNSXK7s7_w) — 本文分析的核心视频 2. [PostgreSQL 官方文档 · Chapter 11. Indexes](https://www.postgresql.org/docs/current/indexes.html) — 索引类型与用法权威说明 3. [Understanding B-Trees: The Data Structure Behind Modern Databases — Spanning Tree](https://youtu.be/K1a2Bk8NrYQ) — 同主题可视化补充 4. Martin Kleppmann, *Designing Data-Intensive Applications*, Chapter 3 "Storage and Retrieval" — B-tree 与 LSM tree 深度对比 5. [CMU 15-445 Database Systems (Andy Pavlo)](https://15445.courses.cs.cmu.edu/) — 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 等场景全覆盖。