一文搞定MySQL索引原理(让你拷打面试官，索引失效再也难不倒你)-开发者社区

B+ 树的存储规则主要围绕平衡性、阶数（m）、节点分裂与合并来组织数据，确保查询、插入和删除的高效性。核心规则如下：

1. 节点类型与存储内容

叶子节点：存储所有数据记录（或指向数据的指针），并通过双向链表相连。叶子节点内键值按升序排列。
内部节点（非叶子）：只存储键和指向子节点的指针，不存储数据。键用于路由，指引搜索路径。

2. 阶数 m 决定容量约束

一棵 m 阶 B+ 树（m ≥ 3）需满足：

每个节点最多有 m 个孩子→ 最多存 m-1 个键。
除根节点外，每个节点至少 ⌈m/2⌉ 个孩子→ 至少存 ⌈m/2⌉ - 1 个键。
根节点至少 2 个孩子（除非树为空或只有一个节点）。

例如 m=5（五阶树）：

非根节点至少有 3 个孩子（含 2 个键），最多 5 个孩子（含 4 个键）。
根节点至少有 2 个孩子，最多 5 个孩子。

3. 键的分布与重复规则

内部节点的键：是其子树中最小键的副本（或最大键的副本，取决于实现），用于分叉决策。这些键同样会出现在叶子节点中（作为实际数据的一部分）。
叶子节点的键：包含所有键值，不重复（每个键唯一对应一条数据，除非允许重复键）。

4. 插入时的分裂规则

当节点键数超过 m-1 时，触发分裂：

将节点从中间位置（第 ⌈m/2⌉ 个键）切开。
中间键被提升至父节点（在内部节点中是副本，不影响子树）。
分裂后左右节点各含约一半的键，且都满足至少 ⌈m/2⌉-1 的约束。
若父节点也溢出，递归向上分裂；最终可能产生新根节点，树高度增加。

5. 删除时的合并与借位规则

当节点键数少于 ⌈m/2⌉ - 1 时，触发调整：

先尝试借位：从左或右兄弟节点借一个键过来（通过父节点中转调整）。
否则合并：将当前节点与一个兄弟节点合并，并把父节点中对应的下界键下移。合并后父节点可能欠载，递归处理。
若根节点变为空，树高度减一。

6. 叶子节点链表规则

所有叶子节点按键值顺序形成双向链表，支持高效范围查询（例如BETWEEN或> x）。
链表指针存储在叶子节点中，不占用阶数 m 的计数（它是额外元数据）。

对比 B 树的关键差异（帮助你记忆）

特性	B+ 树	B 树
数据存储位置	仅叶子节点	所有节点
内部节点键	仅是副本（用于路由）	是真实键（携带数据指针）
叶子节点链表	有，支持范围扫描	无
查询稳定性	所有查找必须到叶子（高度固定）	可能在非叶子命中

一个实际例子（m=4，即 2-3-4 树的变体）：

非根节点至少 2 个孩子（1-2 个键），最多 4 个孩子（3 个键）。
插入 10, 20, 30, 40：
前三个在一个叶子（10,20,30），插入 40 导致分裂：中间键 20 上提到父节点，左边叶子存 10，右边叶子存 30,40。
查询 35 时：从根比较键 20 → 进入右子树 → 叶子节点内顺序查找。

这些规则共同保证了树始终保持平衡（所有叶子在同一层），因此 B+ 树的高度约为 log⁡⌈m/2⌉Nlog⌈m/2⌉N，在百万级数据下通常只需 3-4 次磁盘 I/O。

第一部分：索引生效的核心原理（B+树结构）

大多数关系型数据库（MySQL、PostgreSQL 等）默认使用B+树存储索引。索引生效的数学本质是：查询条件能够利用 B+树叶子节点的有序链表进行快速定位和范围扫描。

1.1 单列索引的有序性

结构：假设对age建索引，B+树叶子节点按age值从小到大排序，并通过双向链表连接。
生效逻辑：
- 等值查询WHERE age = 20：在树中二分查找定位到第一个20。
- 范围查询WHERE age > 20 AND age < 30：定位到20后，顺着链表向右读取，直到遇到30。

1.2 联合索引的排序规则（关键）

假设联合索引(A, B, C)。

结构：叶子节点内的数据首先按 A 排序，A 相同时按 B 排序，B 相同时按 C 排序。
生效前提（最左前缀法则）：查询条件必须包含A（最左列）的等值或范围条件。只有 A 定下来了，B 才是有序的；如果跳过 A 直接查 B，那么在整个索引树中，B 是全局乱序的，无法利用链表扫描。

text

索引 (A, B, C) 的叶子节点示意： (1, 1, 1) -> (1, 1, 2) -> (1, 2, 1) -> (1, 2, 3) -> (2, 1, 1) -> (2, 3, 1) ... ^ ^ ^ ^ ^ ^ A=1区域，内部B有序 A=2区域，内部B有序，但全局B无序

第二部分：从原理推导失效原因

索引失效的根本原因只有两类：排序规则被破坏或索引代价过高被优化器放弃。

2.1 破坏排序规则（最左前缀）

场景：跳过最左列

SQL：WHERE B = 2（索引为(A, B)）
原理推演：在 B+树中，第一层排序键是A，B只在A的内部有序。如果没给A，数据库无法确定该从叶子链表的哪个位置开始找，只能扫描全表。

场景：范围查询阻断后续列

SQL：WHERE A > 1 AND B = 2（索引为(A, B)）
原理推演：数据库通过A > 1定位到一个起始点（比如 A=2 的位置）。但在A=2, A=3, A=4...这组数据中，B是局部有序但全局不连续的（例如 A=2 里有 B=1，A=3 里也有 B=1）。因此无法直接跳到“B=2”的全局位置，索引对B列失效（只能用于 ICP 过滤）。

2.2 破坏值的可比性（函数与类型转换）

场景：对索引列使用函数

SQL：WHERE YEAR(create_time) = 2024
原理推演：B+树叶子节点存储的是原始值'2024-01-01 00:00:00'。查询条件是计算后的值2024。这相当于要比较f(x)和y，而不是x和y。数据库无法直接利用排序好的原始值链表，必须先计算出每一行的YEAR值再比较——这就是全表扫描。

场景：隐式类型转换

SQL：WHERE phone = 13800138000（phone是VARCHAR类型）
原理推演：字符串和数字的比较规则在 MySQL 中会触发将字符串列转换为数值（CAST(phone AS UNSIGNED)）。这等于在列上套了一层函数，原理同上，排序规则瞬间无效。

2.3 破坏前缀匹配（模糊查询）

场景：LIKE '%abc'

原理推演：B+树是按字符串从左到右的字典序排列的。例如索引存储顺序："a", "ab", "abc", "b", "bc"。
如果是LIKE 'abc%'，数据库可以快速定位到以"abc"开头的第一个词，然后向右扫描。
如果是LIKE '%abc'，后缀"abc"可能在链表任何位置（"1abc"在数字区，"zabc"在字母区尾部），无法定位起点，只能全扫描。

2.4 优化器的代价估算（选择性低）

场景：表中 80% 的行gender = 'Male'，查询SELECT * FROM users WHERE gender = 'Male'

原理推演：即使有索引，优化器计算发现：走二级索引 -> 回表查 80% 的数据行（随机 IO 极多）代价 >直接全表扫描（顺序 IO）。因此优化器主动放弃索引。这是逻辑失效，而非物理结构失效。

场景：IS NOT NULL且大部分行非空

原理推演：B+树索引不存储全为 NULL 的值（稀疏索引特性）。查非空意味着要查绝大部分数据，优化器算账后觉得直接扫表更划算。

第三部分：总结对照表（原理 -> 现象）

失效现象	根本原理
违反最左前缀	联合索引树按列顺序排序，跳过头列导致后续列全局无序。
范围查询后索引失效	范围条件导致后续列仅在局部组内有序，无法跨组索引定位。
列上做运算/函数	B+树存的是原始值，无法与计算后的结果直接进行有序比对。
类型转换	触发隐式函数作用于列，等同于在列上做运算。
`LIKE '%x'`	字符串后缀匹配破坏了从左到右的字典序连续性。
`!=`或`NOT IN`	查的是“除了某个点以外的全部”，本质是范围过大，优化器放弃。
OR 包含无索引列	优化器认为拆分成两次索引查询再合并去重，代价可能高于一次全表扫描。