最左前缀底层原理
问题
面试不仅会问”什么是最左前缀匹配”，更会问”底层是怎么实现的”。理解 B+树中联合索引的存储结构是关键。
B+树联合索引的存储
排序规则
联合索引 (a, b) 在 B+树中的排序规则：
-- 排序规则：
-- 1. 先比较 a 的值
-- 2. a 相同时比较 b 的值
-- 3. a 不同时 b 的顺序无意义
graph TD
subgraph B+树叶子节点[叶子节点存储顺序]
A[('赵', 18) → id=10]
B[('赵', 20) → id=15]
C[('赵', 25) → id=20]
D[('钱', 19) → id=8]
E[('钱', 22) → id=12]
F[('孙', 17) → id=5]
G[('孙', 30) → id=25]
H[('李', 18) → id=30]
end
A <--> B <--> C <--> D <--> E <--> F <--> G <--> H
完整的 B+树结构
graph TD
subgraph 根页
Root[索引节点<br/>(赵,18) (孙,17) ...]
end
subgraph 非叶子节点
N1[节点1<br/>(赵,18) → 页A]
N1[节点1<br/>(钱,19) → 页B]
N2[节点2<br/>(孙,17) → 页C]
N2[节点2<br/>(李,18) → 页D]
end
subgraph 叶子节点[叶子节点]
L1[页A<br/>(赵,18) (赵,20) (赵,25)]
L2[页B<br/>(钱,19) (钱,22)]
L3[页C<br/>(孙,17) (孙,30)]
L4[页D<br/>(李,18)]
end
Root --> N1
Root --> N2
N1 --> L1
N1 --> L2
N2 --> L3
N2 --> L4
为什么 WHERE b=xxx 走不了索引
graph TD
subgraph B+树叶子节点[叶子节点]
L1[('赵', 18)] --> L2[('赵', 20)] --> L3[('赵', 25)]
L3 --> L4[('钱', 19)] --> L5[('钱', 22)]
L5 --> L6[('孙', 17)]
end
Query[查询 WHERE b=18] --> Search{B+树怎么搜?}
Search --> Compare{比较公式: (a, b)}
Compare -->|传入 (?, 18)| Problem["? 无法比较
因为没有第一列的值"]
Problem --> Result[只能从第一页遍历到最后一页<br/>→ 全索引扫描而不是索引查找]
关键点：B+树的内部节点是通过比较 (a, b) 复合键来定位的。如果缺少 a，根本无法与非叶子节点的索引项进行比较。
// 伪代码：B+树节点查找逻辑
int compare(CompositeKey k1, CompositeKey k2) {
if (k1.a != k2.a) {
return compare(k1.a, k2.a); // 先比 a
} else {
return compare(k1.b, k2.b); // a 相同才比 b
}
}
// 如果 WHERE b=18：
// 传入节点比较的是 (?, 18)
// 无法与节点中的 (赵, 18) 比较
// 因为不知道 ? 和 '赵' 谁大谁小
为什么 WHERE a=1 AND c=3 只能用到 a
-- 索引 idx_a_b_c(a, b, c)
-- 查询：WHERE a = 1 AND c = 3
graph LR
subgraph B+树中
A[(1, 2, x)] --> B[(1, 3, y)]
B --> C[(1, 3, z)]
C --> D[(1, 4, w)]
D --> E[(2, 1, v)]
end
Query1[WHERE a=1] --> B
Query1 --> C
Query1 --> D
Note["找到所有 a=1 的范围
但无法跳到 c=3
因为 b 字段不确定"]
Filter[在回表后<br/>用 WHERE c=3 过滤]
过程：
1. B+树定位到 a=1 的范围（用到索引）
2. 在 a=1 范围内，B+树无法确定 c=3 的位置（因为 b 是中间的维度，索引只保证 b 有序）
3. 只能扫描所有 a=1 的行，回表后过滤 c=3
范围查询后列失效的原因
-- 索引 idx_a_b_c(a, b, c)
-- 查询：WHERE a = 1 AND b > 10 AND c = 3
graph LR
A[索引条目<br/>a=1, b=5, c=1] --> B[a=1, b=8, c=2]
B --> C[a=1, b=10, c=1]
C --> D[a=1, b=12, c=3]
D --> E[a=1, b=15, c=1]
E --> F[a=1, b=18, c=2]
Start[从 b>10 开始] --> D
Start --> E
Start --> F
Note["索引保证了 (a,b) 有序
但在 b>10 范围内
c 是无序的!
c=3: 3, 1, 2
无法利用索引查找c"]
b > 10是一个范围条件- 在
b > 10的范围内，c列的值是无序的 - 因此
c = 3不能在索引中直接定位，只能回表后过滤
面试要点
- 排序本质：联合索引按列顺序逐层排序，后面的列的有序性依赖前面的列
- B+树比较：节点比较是按复合键整体比较的，缺少前面的列无法比较
- 跳列失效：跳过的列破坏了有序性依赖，后面的列索引失效
- 范围失效：范围查询后，后面的列不再有序，无法利用索引
一句话总结：最左前缀的底层原理是 B+树复合键的比较规则——先比较第一列，相同才比较第二列，跳过了前面的列就失去了比较基准。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
暂无评论内容