在数据库系统中，索引是提升查询性能的核心机制之一。而索引的高效性，离不开其底层所依赖的数据结构。本文将从基础的二叉树出发，逐步剖析B树、B+树的结构特性，并深入探讨为什么现代关系型数据库（如MySQL）普遍采用B+树作为其索引的底层实现。
一、二叉树：理想与现实的差距
二叉搜索树（Binary Search Tree, BST） 是最直观的有序数据结构之一：对于任意节点，其左子树的所有节点值小于该节点，右子树的所有节点值大于该节点。这种结构支持 O(log n) 的平均查找、插入和删除效率。
然而，在实际应用中，普通二叉搜索树存在致命缺陷：
- 退化问题：若插入数据有序（如1,2,3,4,5），树会退化为链表，时间复杂度退化为 O(n)。
- 频繁磁盘I/O：数据库中的数据通常存储在磁盘上，而二叉树的高度较高（即使平衡），每次查找可能需要多次磁盘读取，效率低下。
为解决退化问题，出现了AVL树、红黑树等自平衡二叉树。它们能保证树的高度始终为 O(log n)，但依然不适合作为数据库索引结构——原因在于磁盘I/O模型不匹配。
磁盘以“页”为单位读写（通常4KB或16KB），而二叉树每个节点只存储一个键值，一次I/O仅获取一个关键字，I/O效率极低。
二、B树：为磁盘而生的多路平衡搜索树
B树（B-Tree） 是由Rudolf Bayer和Ed McCreight于1972年提出的一种多路平衡搜索树，专为减少磁盘I/O而设计。
B树的关键特性：
- 每个节点可包含多个关键字（key）和多个子指针（child pointer）。
- 所有叶子节点位于同一层，保证平衡。
- 节点大小通常设计为一个磁盘页（如16KB），最大化单次I/O的信息量。
- 关键字数量介于 ⌈m/2⌉−1 到 m−1 之间（m为阶数），保证树的紧凑性和平衡性。
例如，一个阶数为100的B树，每个节点最多存储99个关键字和100个子指针。三层B树即可容纳约 100^3 = 1,000,000 条记录，而高度仅为3，意味着最多3次磁盘I/O即可完成查找。
但B树仍存在不足：
- 内部节点同时存储关键字和数据（记录指针或完整记录），导致每个节点能容纳的关键字数量受限。
- 范围查询效率不高：需中序遍历整棵树，无法高效连续访问。
三、B+树：数据库索引的黄金标准
B+树（B+ Tree） 是B树的改进版本，也是现代数据库（如MySQL InnoDB引擎）索引的首选结构。
B+树的核心特点：
- 数据仅存于叶子节点
所有内部节点仅存储索引关键字和子节点指针，不存储实际数据。这使得每个内部节点能容纳更多关键字，进一步降低树高。 - 叶子节点通过双向链表连接
所有叶子节点按关键字顺序链接成链表，极大优化了范围查询（如WHERE id BETWEEN 10 AND 100）和全表扫描的性能。 - 更高的扇出（Fan-out）
由于内部节点不存数据，同样大小的节点可存储更多关键字，树的高度更低，I/O次数更少。
举例说明：
假设每页16KB，主键为BIGINT（8字节），指针为6字节。
- B+树内部节点：每个条目 = 8（key）+ 6（ptr）= 14字节 → 每页可存约 16×1024 / 14 ≈ 1170 个条目。
- 两层B+树可索引 1170 × 1170 ≈ 136万条记录；三层可达 16亿条以上，而高度仅为3！
四、MySQL中的索引实现：InnoDB与B+树
在MySQL中，InnoDB存储引擎使用B+树实现两种主要索引：
1. 聚簇索引（Clustered Index）
- 主键索引即为聚簇索引。
- 叶子节点直接存储整行数据。
- 表数据按主键物理排序存储。
2. 二级索引（Secondary Index）
- 非主键字段的索引。
- 叶子节点存储索引列值 + 主键值。
- 查询时需“回表”：先查二级索引得主键，再用主键查聚簇索引获取完整数据。
正因如此，合理设计主键（如使用自增整数）对性能至关重要——避免频繁页分裂和随机I/O。
五、为何不用哈希或跳表？
- 哈希索引：仅支持等值查询（=），不支持范围查询（<, >, BETWEEN）和排序，适用于Memory引擎，但不适用于通用场景。
- 跳表（Skip List）：Redis等内存数据库常用，但在磁盘环境下不如B+树高效，因缺乏局部性（Locality of Reference）。
结语
从二叉树到B+树，数据结构的演进始终围绕两个核心目标：降低树高以减少I/O次数 和 提升范围查询效率。B+树凭借其高扇出、数据集中于叶子、链表连接等特性，成为磁盘存储系统中最优的索引结构之一。
理解这些底层原理，不仅能帮助我们写出更高效的SQL，还能在数据库设计、索引优化和性能调优中做出更明智的决策。
索引不是魔法，而是精心设计的数据结构艺术。
