B+ 树非唯一索引如何处理重复 key？为什么常把主键拼进索引项？
简化版
非唯一索引允许多个记录拥有相同 key。为了在 B+ 树中让每个索引项可区分、可排序，存储引擎常把主键或行定位信息拼到二级索引项里，形成类似 (secondary_key, primary_key) 的复合顺序。
详细版
如果只按 status 建非唯一索引，可能有大量记录都是 status=1。B+ 树叶子中不能只存一个 1，而要存多条索引项。常见方式是：
(status=1, pk=100)
(status=1, pk=108)
(status=1, pk=233)这样好处是：
- 重复 key 内部仍有稳定顺序；
- 每条索引项能定位到具体行；
- 删除或更新某一行时能精确找到对应索引项；
- 二级索引查到主键后可回表。
因此 InnoDB 二级索引叶子中保存主键，不只是为了回表，也让非唯一索引项具备唯一定位能力。
完整版教学
一、为什么重复 key 会给 B+ 树带来问题
B+ 树依赖有序 key 做查找。如果索引是唯一的，每个 key 对应一条记录，定位很简单。但非唯一索引中，一个 key 可能对应成千上万条记录。树必须能保存这些重复项，并且在插入、删除、扫描时区分它们。
例如用户表按 status 建索引，活跃用户可能有 100 万个 status=1。如果叶子页只保存一个 1，就无法定位每一行，也无法高效删除其中某一条记录。
记忆钩子：非唯一索引不是一个 key 指一坨数据，而是很多条带行身份的索引项排在一起。
二、为什么常拼上主键
在 InnoDB 这类聚簇索引存储中，二级索引叶子项通常保存二级索引 key 和主键值。对于非唯一二级索引，这相当于用 (secondary_key, primary_key) 形成可唯一排序的索引项。相同二级 key 下，再按主键区分顺序。
idx_status 叶子项:
(0, pk=5)
(1, pk=2)
(1, pk=8)
(1, pk=20)
(2, pk=7)这样查 status=1 时能定位到连续范围，范围内每个索引项都有主键，可用于回表或精确删除。
三、重复 key 范围如何扫描
查询 where status=1 时，B+ 树会定位到第一个 status=1 的索引项，然后沿叶子页向后扫描，直到 key 不再等于 1。若索引项按 (status, pk) 排序，那么扫描范围是从 (1, -∞) 到 (1, +∞)。
lower bound: (1, MIN_PK)
upper bound: (1, MAX_PK)这说明重复 key 并不会破坏 B+ 树范围扫描，只是可能导致命中的范围很大，选择性差。
四、删除某条重复 key 记录为什么需要行身份
如果要删除 status=1, pk=8 的记录，索引必须能找到具体那一个索引项，而不是随便删掉某个 status=1。拼上主键后，删除目标就是 (1,8)，定位明确。
如果索引项没有主键或行指针，就需要在一堆重复 key 下额外扫描和比较完整行，成本高且实现复杂。行身份是非唯一索引可维护的基础。
五、非唯一索引对选择性的影响
重复 key 很多意味着索引选择性低。status 只有 0、1、2 三种值时，单独建 status 索引可能对某些查询帮助有限，因为每个值对应大量行。优化器可能认为扫描索引再大量回表不如全表扫描。
| 索引列 | 不同值数量 | 选择性 | 常见效果 |
|---|---|---|---|
id | 100万 | 高 | 点查很好 |
status | 3 | 低 | 单独使用可能一般 |
(status, created_at) | 更多组合 | 中等或更好 | 适合状态+时间范围 |
所以非唯一索引可用，不代表一定高效；要结合过滤比例和回表成本。
六、唯一索引和非唯一索引的查找差异
唯一索引找到目标 key 后可以确认最多一条记录，查找可立即结束。非唯一索引找到第一个匹配后，还要继续扫描相同 key 的范围。若查询需要全部匹配行，这是必须成本；若只需要一条，数据库也要根据执行语义决定能否提前停止。
唯一约束还会在插入时检查重复；非唯一索引则允许相同 key，只维护有序项。两者底层都可以是 B+ 树，但语义和扫描行为不同。
七、常见误区与追问
- 误区：B+ 树索引 key 必须唯一。 B+ 树可以存非唯一索引项，只要每条项可排序、可定位。
- 追问：为什么二级索引叶子要存主键？ 用于回表，也用于区分和定位重复二级 key 下的具体行。
- 误区：非唯一索引一定没用。 它选择性可能低，但配合其他列、排序或覆盖仍然有价值。
- 追问：查重复 key 时怎么确定范围？ 定位到该 key 的下界，再扫到 key 变化为止。
- 误区：唯一索引和非唯一索引查找完全一样。 唯一索引命中后可停止，非唯一索引可能要扫描一段重复范围。
八、加强记忆
非唯一索引的核心是「重复 key 也要变成可区分的索引项」。常见做法是把主键拼到二级索引叶子中，形成 (二级key, 主键) 的顺序。这样重复值能连续扫描，每条记录也能精确定位和回表。它解决的是存储和维护问题；查询是否高效，还要看选择性、返回行数和是否覆盖。