)
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 包含无索引列 | 优化器认为拆分成两次索引查询再合并去重，代价可能高于一次全表扫描。 |
通过这套推导逻辑，我们就能理解：索引不是“用了”就快，而是“能用得上排序”才快。任何破坏数据在 B+树中有序性的操作，都会让索引失效。
