当前位置：首页 > news >正文

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

news 来源：原创 2025/9/10 8:26:56

MySQL 为什么使用 B+ 树来做索引，它的优势是什么？
- 特性和定义
- B+ 树和 B 树的对比
- - 拓展：既然 B+ 树相较于 B 树优势如此之大，为什么 nosql 的 MongoDB 底层仍采用 B 树而不是 B+ 树？
- 使用 B+ 树做索引的优势
- - 补充：为什么说 B+ 树的插入和删除效率高？B+ 树的冗余结点是如何形成的？它们的作用是什么？冗余结点是如何帮助提高插入和删除效率的？冗余结点指的是叶子节点冗余还是用做索引的非叶子节点冗余？
  - - 为什么说 B+ 树的插入和删除效率高？结构特性带来的效率优势
    - 冗余节点的形成与作用
    - 冗余结点提升效率的原理
    - 冗余结点指的是叶子节点冗余还是用做索引的非叶子节点冗余？冗余结点的本质
- 与其它数据结构的对比
索引有哪些种？
- 单值索引
- 唯一索引
- 主键索引
- 复合索引
- 前缀索引
什么是最左匹配原则？
- 拓展：最左匹配原则是数据库索引设计的核心概念之一，主要针对联合查询
索引区分度？
联合索引如何进行排序？

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

特性和定义

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

B+ 树和 B 树的对比

数据存储分布：
B 树：所有结点均存储数据（键值对）；
B+ 树：仅叶子节点存储完整数据，内部节点仅做索引（键 + 指针）；
叶子节点结构：
B 树：独立叶子节点；
B+ 树：叶子节点通过双向链表串联，形成有序链表结构；
查询性能对比：
B 树和 B+ 树的单点查询平均时间复杂度相当，均为 $O(\log_d{N})$ ；
在进行范围查询时，B+ 树通过链表直接进行顺序查询，而 B 树则需要中序遍历，效率差 10 倍。
空间利用率：
B+ 树内部可以存储更多的键值，树高普遍比 B 树低 2 层。
插入删除操作：
B+ 树数据变更仅影响叶子节点，而 B 树可能引发连锁节点的分裂与合并；
典型应用场景：
B 树：MongoDB（文档型数据库）、文件系统；
B+ 树：MySQL（InnoDB）、Oracle、PostgreSQL 等关系型数据库；
工程实践差异：
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仍保持升序排列）

目录