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

B 树的存储规则主要围绕平衡性、阶数m、节点分裂与合并来组织数据确保查询、插入和删除的高效性。核心规则如下1. 节点类型与存储内容叶子节点存储所有数据记录或指向数据的指针并通过双向链表相连。叶子节点内键值按升序排列。内部节点非叶子只存储键和指向子节点的指针不存储数据。键用于路由指引搜索路径。2. 阶数 m 决定容量约束一棵 m 阶 B 树m ≥ 3需满足每个节点最多有 m 个孩子→ 最多存 m-1 个键。除根节点外每个节点至少 ⌈m/2⌉ 个孩子→ 至少存 ⌈m/2⌉ - 1 个键。根节点至少 2 个孩子除非树为空或只有一个节点。例如 m5五阶树非根节点至少有 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 树数据存储位置仅叶子节点所有节点内部节点键仅是副本用于路由是真实键携带数据指针叶子节点链表有支持范围扫描无查询稳定性所有查找必须到叶子高度固定可能在非叶子命中一个实际例子m4即 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) ... ^ ^ ^ ^ ^ ^ A1区域内部B有序 A2区域内部B有序但全局B无序第二部分从原理推导失效原因索引失效的根本原因只有两类排序规则被破坏或索引代价过高被优化器放弃。2.1 破坏排序规则最左前缀场景跳过最左列SQLWHERE B 2索引为(A, B)原理推演在 B树中第一层排序键是AB只在A的内部有序。如果没给A数据库无法确定该从叶子链表的哪个位置开始找只能扫描全表。场景范围查询阻断后续列SQLWHERE A 1 AND B 2索引为(A, B)原理推演数据库通过A 1定位到一个起始点比如 A2 的位置。但在A2, A3, A4...这组数据中B是局部有序但全局不连续的例如 A2 里有 B1A3 里也有 B1。因此无法直接跳到“B2”的全局位置索引对B列失效只能用于 ICP 过滤。2.2 破坏值的可比性函数与类型转换场景对索引列使用函数SQLWHERE YEAR(create_time) 2024原理推演B树叶子节点存储的是原始值2024-01-01 00:00:00。查询条件是计算后的值2024。这相当于要比较f(x)和y而不是x和y。数据库无法直接利用排序好的原始值链表必须先计算出每一行的YEAR值再比较——这就是全表扫描。场景隐式类型转换SQLWHERE phone 13800138000phone是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 包含无索引列优化器认为拆分成两次索引查询再合并去重代价可能高于一次全表扫描。通过这套推导逻辑我们就能理解索引不是“用了”就快而是“能用得上排序”才快。任何破坏数据在 B树中有序性的操作都会让索引失效。