【每日八股】MySQL篇（三）：索引（上）

MySQL 为什么使用 B+ 树来做索引，它的优势是什么？

特性和定义

B+ Tree 是一种多叉树，叶子节点才存放具体的数据而非叶子节点仅存放索引，每个结点当中的数据是按主键顺序存放的。在叶子节点中，包括了所有的索引值信息，并且每一个叶子节点都指向下一个叶子节点，形成一个链表（因此 B+ 树支持范围查询）。B+ Tree 存储千万级别的数据只需要 3 ~ 4 层高度就可以满足（加入一个非叶子结点存储 1000 个索引，那么三层树高的情况下可以存储$1000^3=1000000000$十亿条数据），千万级的表查询最多只需要 3 ~ 4 次磁盘 I/O。

B+ 树和 B 树的对比

1. 数据存储分布：
   B 树：所有结点均存储数据（键值对）；
   B+ 树：仅叶子节点存储完整数据，内部节点仅做索引（键 + 指针）；

2. 叶子节点结构：
   B 树：独立叶子节点；
   B+ 树：叶子节点通过双向链表串联，形成有序链表结构；

3. 查询性能对比：
   B 树和 B+ 树的单点查询平均时间复杂度相当，均为$O({\log }_{d}N)$；
   在进行范围查询时，B+ 树通过链表直接进行顺序查询，而 B 树则需要中序遍历，效率差 10 倍。

4. 空间利用率：
   B+ 树内部可以存储更多的键值，树高普遍比 B 树低 2 层。

5. 插入删除操作：
   B+ 树数据变更仅影响叶子节点，而 B 树可能引发连锁节点的分裂与合并；

6. 典型应用场景：
   B 树：MongoDB（文档型数据库）、文件系统；
   B+ 树：MySQL（InnoDB）、Oracle、PostgreSQL 等关系型数据库；

7. 工程实践差异：
   B+ 树叶子节点存储密度可达 70%，而 B 树通常为 50% ~ 60%；
   在处理百万级数据时，B+ 树比 B 树减少 30% ~ 50% 的磁盘 I/O 次数（得益于 B+ 树的高扇出与低树高特性）；
   在进行范围查询时，B+ 树比 B 树的性能高 5 ~ 10 倍（得益于 B+ 树叶子节点之间的顺序连接特性）。

拓展：既然 B+ 树相较于 B 树优势如此之大，为什么 nosql 的 MongoDB 底层仍采用 B 树而不是 B+ 树？

B+ 树在关系型数据库（如 MySQL）中表现卓越，因其擅长范围查询和排序；而 MongoDB 作为文档数据库，优先优化点查询和文档快速获取，B 树的结构特性更契合其设计目标。

使用 B+ 树做索引的优势

• 单点查询：B 树进行单个索引查询时，最快可以在$O(1)$的时间代价内完成（因为 B 树当中的结点，包括非叶子节点，既存储索引又存储数据）。从平均时间代价上来看，它比 B+ 树更快。但是 B 树的查询波动比较大，原因同样是每个节点既存储索引又存储数据，所以有时候访问到非叶子节点即可找到索引，有时候需要访问到叶子节点才能找到索引。B+ 树的非叶子节点不存放实际的记录数据，而只存放索引，在数据量相同的情况下，B+ 树的非叶子节点可以存放更多的索引，查询底层结点的 I/O 更少，因此 B+ 树在做单点查询时更加稳定。
• 插入和删除效率：B+ 树含有大量的冗余结点，删除一个节点时，可以直接从叶子结点删除，甚至可以不动非叶子节点，删除非常快。B+ 树的插入也是一样，有冗余结点，插入可能存在结点的分裂（如果节点饱和），但是最多只涉及树的一条路径。B 树没有冗余结点，删除节点非常复杂，可能涉及复杂的树的变形。
• 范围查询：B+ 树的所有叶子节点直接通过双向链表连接，而 B 树没有将叶子节点通过链表串联，因此 B 树只能通过树的遍历来完成范围查询，其范围查询的效率不如 B+ 树。B+ 树的插入删除效率非常高，当面对存在大量的范围检索的场景时，适合使用 B+ 树，比如数据库；而对于存在大量单个索引查询的场景，可以考虑 B 树，比如 nosql 的 MongoDB。

补充：为什么说 B+ 树的插入和删除效率高？B+ 树的冗余结点是如何形成的？它们的作用是什么？冗余结点是如何帮助提高插入和删除效率的？冗余结点指的是叶子节点冗余还是用做索引的非叶子节点冗余？

为什么说 B+ 树的插入和删除效率高？结构特性带来的效率优势

• 多路平衡特性：每个结点可存储大量键值（高扇出），树高通常维持在 3 ~ 4 层，磁盘 I/O 次数更少；
• 顺序访问优化：叶子节点之间形成有序链表（InnoDB 在实现上使用双向链表），范围查询效率极高；
• 写操作局部性：插入/删除只需要修改局部节点（具体来说，指的就是叶子节点），多数情况下不会引发连锁结构调整。

冗余节点的形成与作用

• 冗余节点类型：主要存在于非叶子节点（即索引节点）；
• 形成机制：插入时结点分裂会产生临时性父节点键值冗余，删除节点时合并会暂时保留未及时清理的索引键，批量操作时会延迟维护产生的中间状态；
• 作用：缓冲结构调整压力，避免频繁的节点分裂/合并，允许临时超出结点容量限制，为并发操作提供版本控制的可能性。

冗余结点提升效率的原理

• 延迟维护：非叶子节点的冗余键允许暂时不立即处理结构变更；
• 批量处理：多个操作累积后，一次性处理冗余，摊平维护成本；
• 概率优化：利用节点填充因子（如 70% 阈值）预留空间缓冲突发操作。

冗余结点指的是叶子节点冗余还是用做索引的非叶子节点冗余？冗余结点的本质

冗余结点是 B+ 树用空间换时间的典型设计，通过允许非叶子节点存在临时性的冗余键值，换取更平缓的结构维护代价。叶子节点由于需要保证数据的有序性，冗余主要表现为预留空间而非键值重复。

与其它数据结构的对比

• B+ 树对比 B 树：B+ 树只在叶子节点存储数据，而 B 树的非叶子节点也存储数据。因此 B+ 树的单个结点数据量更小（在数据量相同的前提下，B+ 树可以存储更多的索引），在相同的磁盘 I/O 次数下，B+ 树可以查询更多的结点。B+ 树的叶子节点采用双向链表连接（具体来说，MySQL 的 InnoDB 在实现细节上是采用双向链表的。早期 MySQL 的 MyISAM 引擎使用单向链表，InnoDB 自 MySQL 5.5 称为默认引擎后，叶子节点之间的双向链表连接称为标准实现），适合 MySQL 中常见的基于范围的查询，而 B 树做不到这一点，因此它更适用于单点查询。
• B+ 树对比二叉树：对于有 N 个叶子节点的 B+ 树，其搜索复杂度为 $O({\log }_{d}N)$，其中 d 表示结点允许的最大子节点个数。实际应用中，d 值大于 100，即使数据达到千万级，B+ Tree 的高度依然维持在 3 ~ 4 层，一次查询只需要 3 ~ 4 次磁盘 I/O 就能查到。二叉树每个父节点的儿子结点个数为 2 个，意味着其搜索复杂度为$P(\log N)$，二叉树搜索到目标数据需要的磁盘 I/O 数更多。
• B+ 树对比哈希：哈希在做等值查询时效率较高，搜索复杂度为$O(1)$，但是 Hash 不适合做范围查询。

索引有哪些种？

单值索引

单值索引即一个索引只包含单个列，一个表可以有多个单列索引。

• 建表时：加上 key(列名) 指定；
• 单独创建：create index 索引吗 on 表名(列名)；
• 单独创建：alter table 表名 add index 索引名(列名)；

唯一索引

唯一索引中，索引列的值必须唯一，但允许有 null 且 null 可以多次出现。

• 建表时：加上 unique(列名) 指定；
• 单独创建：create unique index idx 表名(列名) on 表名(列名)；
• 单独创建：alter table 表名 add unique 索引名(列名)；

主键索引

设定为主键后，数据库会自动建立索引，InnoDB 为聚簇索引，值必须唯一且不能为 null。

• 建表时：加上 primary key(列名) 指定；

复合索引

复合索引即一个索引包含多个列。

• 建表时：加上 key(列名列表) 指定；
• 单独创建：create index 索引名 on 表名(列名列表)；
• 单独创建，alter table 表名 add index 索引名(列名列表)；

前缀索引

对字符类型字段的前几个字符建立的索引，而不是在整个字段上建立的索引，前缀索引可以建立在字段类型为 char、 varchar、binary、varbinary 的列上。使用前缀索引的目的是为了减少索引占用的存储空间，提升查询效率。

• 单独创建：alter table 表名 add 索引名(column_name(索引长度))。

什么是最左匹配原则？

使用联合索引时，存在最左匹配原则，也就是按照最左优先的方式进行索引的匹配。使用联合索引进行查询的时候，如果不遵循最左匹配原则，联合索引会失效。

拓展：最左匹配原则是数据库索引设计的核心概念之一，主要针对联合查询

最左匹配原则规定了在使用联合索引时，查询条件必须从索引定义的最左侧列开始，不能跳过中间的列，这样才能有效地利用索引进行快速检索。

联合索引按照定义时的列顺序构建 B+ 树结构，例如索引(a, b, c)，数据先按a排，a相同再按b排，b相同按c排。

联合索引的生效条件是，查询必须包含最左列，条件列需要连续无跳跃。若某列使用范围查询，则其右侧的列无法继续使用索引，比如WHERE a=1 AND b>10 AND c=2，仅a和b有效，c需回表过滤。

案例：
WHERE a=1 AND b>2 AND c=3 -- ✅ 使用a、b（c因b范围查询失效）
WHERE b=2 -- ❌ 缺少最左列a
WHERE a=1 AND c=3 -- ❌ 跳过b，仅用a（c无法走索引）
WHERE a>1 AND b=2 -- ❌ a范围查询后，b无法走索引（失效原因：当a使用范围查询时，b的等值条件无法有效利用索引，数据库只能使用a>1的索引范围扫描，此时b=2的记录在索引中是离散分布的）

索引区分度？

查询优化器在发现某个值出现在表的数据行中的百分比（惯用的百分比界限为 30%）很高时，会忽略索引，进行全表扫描。

联合索引如何进行排序？

以(a, b, c)为例，第一优先级：按 a 列值升序排序；第二优先级：a 相同则按 b 列值升序排序；第三优先级：a 和 b 都相同按 c 值升序排序。

排序特性：

• 局部有序性：每个 a 值的范围内，b 是有序的；每个 a, b 组合内，c 是有序的。
• 跨级断点：a 改变时，b 和 c 的排序重新开始。

对查询的影响：

• 范围查询会破坏后续列的排序优势（如a>1时，b的排列不再全局有序）；
• 等值查询能保持后续列的排序（如a=1时，b仍保持升序排列）