每个程序员都听过"加个索引就好了"这句万灵药式的建议。但很少有人真正停下来想：为什么是 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 索引实践 |
视频开场很直接——它先让你感受"没有索引"的痛。当你在一张上亿行的表里执行 SELECT * FROM users WHERE email = '[email protected]'，数据库唯一能做的事就是顺序扫描（Sequential Scan）：从第一行读到最后一行，逐个比较。这是 O(n) 的操作，n 是行数。
这里的关键不是"O(n) 慢"，而是慢在哪。我延伸一下：CPU 比较一个字符串只需要纳秒级，但如果你那上亿行存在机械硬盘上，真正的时间被花在等待磁头寻道上——一次随机读取大约 10 毫秒，比 CPU 周期慢了六个数量级。视频的核心铺垫正在于此：索引的全部意义，是把"必须读 n 次"压缩成"只读几次"。 从 O(n) 到 O(log n)，看起来只是数学符号的变化，在磁盘世界里却意味着"扫一整张表"和"翻几页书"的天壤之别。
这是全视频最该停下来思考的一段。视频指出，很多人下意识觉得：既然索引要支持快速查找和范围扫描，那用一棵平衡二叉搜索树（BST）或红黑树不就行了？查找 O(log₂ n)，完美。
但这是把"内存思维"套到了"磁盘现实"上。 我的延伸分析：在内存里，红黑树确实优秀，因为每个节点访问都是同一个数量级的延迟。可一旦树落到磁盘，问题就暴露了——二叉树每个节点只有两个子节点，意味着它"又高又瘦"。一亿行数据，一棵平衡二叉树的高度约为 log₂(10⁸) ≈ 27 层。最坏情况下你要做 27 次磁盘读取，每次 10 毫秒，光寻道就要 270 毫秒。二叉树的"平衡"在 CPU 眼里是优势，在磁盘眼里是灾难。视频正是用这种落差，把读者推向 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 最重要的一层。
视频以 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。这是任何想真正读懂执行计划的人都该知道的一层。
视频花了相当篇幅讲 PostgreSQL 特有的索引架构，这也是它比泛泛教程更值钱的地方。我梳理其逻辑：PostgreSQL 的表是一个堆表（heap），行数据物理上按写入顺序乱堆着，索引本身不存数据，只存"键 → 行物理位置（CTID）"的映射。这意味着通过二级索引查到行之后，往往还要回表（bookmark lookup）一次去取真实数据。
这里有个常考的对比：MySQL InnoDB 的主键索引是聚簇索引（Clustered Index）——整行数据就物理上按主键排序存在 B+ tree 的叶子里，主键查询不需要回表；而非主键索引的叶子存的是主键值，查完还要再查一次主键树。聚簇索引"表即索引"，二级索引"指回主键"。 PostgreSQL 选择了不同的哲学：表和索引分离，索引永远是二级的。两种设计各有取舍——聚簇索引主键查询快，但二级索引要绕一圈；堆表模型写更新更灵活，配合 MVCC（多版本并发控制）天然友好。视频把这些工程权衡摆出来，是它最有营养的部分。
视频后半段开始泼冷水，这也是我最欣赏它的地方——它不像营销号那样鼓吹"到处加索引"。索引是有代价的。
代价一：写放大（write amplification）。每插入、更新、删除一行，数据库不仅要改表，还要同步维护所有相关索引。一张表上有 5 个索引，一次写入可能触发 6 次页修改。这就是为什么 OLTP（高并发事务）系统要克制索引数量。
代价二：选择性（selectivity）。我的延伸：索引不是万能加速器。如果你给"性别"这种只有两三个值的列建索引，查询时索引可能扫出一半行，再逐个回表，比直接全表扫描还慢。数据库优化器会判断"索引是否划算"，不划算就弃用索引走顺序扫描——这就是为什么你建了索引却"没生效"。视频反复强调一个经验法则：索引适合高选择性列，即不同值多、重复少的列，比如 email、用户 ID。
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》里把这层讲得最透。
flowchart TD
A["查询慢的根本原因<br/>磁盘 I/O 是瓶颈，而非 CPU"] --> B["索引的目标<br/>把 O(n) 压缩到 O(log n) 次磁盘读取"]
B --> C["为什么不用二叉树/红黑树?"]
C --> C1["又高又瘦: 1亿行 ≈ 27 层<br/>≈ 27 次磁盘 I/O = 灾难"]
B --> D["B-tree 的两个工程决策"]
D --> D1["高扇出: 每节点存几百个键<br/>树变得矮胖, 仅 3-4 层"]
D --> D2["页对齐: 一个节点 = 一个磁盘页<br/>读一个节点 = 一次 I/O, 零浪费"]
D --> E["数据库实际用 B+ tree"]
E --> E1["数据只在叶子节点<br/>内部节点纯当路标"]
E --> E2["叶子用双向链表串联<br/>范围查询沿链表线性扫描"]
E --> F["两种表存储架构"]
F --> F1["聚簇索引 MySQL InnoDB<br/>表即主键索引树, 主键查询免回表"]
F --> F2["堆表 + 二级索引 PostgreSQL<br/>索引存 键→CTID, 二级查询需回表"]
D --> G["索引的代价"]
G --> G1["写放大: 写一次要维护所有索引"]
G --> G2["选择性: 低基数列建索引反而更慢"]
E --> H["B-tree 之外"]
H --> H1["PostgreSQL: Hash / GIN / GiST / BRIN"]
H --> H2["写密集: LSM tree<br/>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 是瓶颈"这个原点。
B-tree 不是又一个数据结构，而是一份"把树的高度与磁盘的页精确对齐"的工程契约——它让一亿行数据只需三四次 I/O，这是整个数据库世界能跑得快的底层原因。
本文由「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 等场景全覆盖。