自存笔记，学习MySQL实战45讲

第四讲：索引常用数据结构、B+树、索引维护

索引常用数据结构

哈希表

以键值对形式存储数据
等值查询复杂度是O(1)，范围查询性能很差，因为存储位置之间无序
底层实现通常是，数组+链表/红黑树，当多个键映射到同一索引，这些键值会以链表/红黑树形式存储在该索引位置

有序数组

就是数组中元素按照某种固定顺序排序的数组
等值查询和范围查询性能都很优秀，有序可以用二分
但是更新数据很麻烦，比如中间插入一个记录就要改动后面的所有记录，只适合静态存储引擎

N叉树

分叉多，树高很低，访问磁盘次数很低

B+树

InnoDB使用了B+树索引模型
每一个索引再InnoDB里面对应一颗B+树
非叶子节点只存索引键和指向子节点的指针，叶子节点存索引键和完整记录（主键索引）/主键值（非主键索引）

聚簇索引VS二级索引

特性	主键索引（聚簇索引）	非主键索引（二级索引）
非叶子节点内容	主键值 + 子节点指针	非主键字段值 + 子节点指针
叶子节点内容	主键值 + 完整记录	非主键字段值 + 主键值（需回表）
数据存储方式	数据与索引聚簇存储（物理有序）	索引与数据分离（逻辑有序）
是否需要回表	否（直接获取记录）	是（通过主键二次查询）

索引维护

页分裂

插入新数据时，目标数据页已填满，则需要页分裂
将满页的数据按中间位置分成两部分，原页保留前半部分，后半部分申请新的数据页
原页中最大键（或中间键）提升到父节点，作为指向新页的索引键

页合并

删除数据后，目标数据页的数据量低于阈值，且相邻页页低
当前页与相邻页的数据合并到其中一个页，释放另一个空页
删除父节点中指向被合并页的索引键，确保索引结构正确

自增主键

通过数据库自增机制自动生成的无业务含义的数值型主键
自增ID是严格递增的，插入时数据按主键顺序追加，不会触发页分裂
长度短，非主键索引的叶子节点需要存主键值，节省存储空间
短主键可以减少回表时的开销

业务字段主键

选择具有实际业务意义的字段作为主键
若业务key无序（如uuid），可能频繁触发页分裂，增加I/O开销
长字符串主键可能会占用更多磁盘空间
适用于kv场景
- kv场景要求仅通过键精准查询，每行数据由“唯一键”和“对应值”组成，类似字典的结构
- 仅有一个索引，且是唯一索引

第五讲：回表、覆盖索引、最左前缀、索引下推

回表

正常二级索引仅存储了索引字段值和主键值
通过二级索引查询非主键列/二级索引无法覆盖查询所需的所有列，需要额外访问主键索引获取完整数据行
当使用二级索引查询数据时，需先通过二级索引找到对应的主键值，再通过主键索引（聚簇索引）查询完整数据行，这个二次查询的过程就称为 “回表”

覆盖索引

避免回表，提升性能
一种特殊的二级索引，通过让索引本身覆盖查询所需的所有字段，从而避免回表
MySQL中通过联合索引实现

1	CREATE INDEX idx ON user (name, age, address);

*创建联合索引idx，包含user表中的name，age，address字段

最左前缀

基于数据库索引的有序性设计的核心规则
查询条件必须匹配联合索引中从左到右的连续字段，才能有效利用索引加速检索
所以可以根据查询频率来设计索引

索引设计的核心原则

复用优先：若存在高频联合查询（如a AND b），优先创建联合索引（a，b）
为单字段高频查询单独建立索引：若单字段拆线呢频率高&无法被现有联合索引覆盖，则创建单独索引

索引设计决策流程

是否有高频联合查询？
   ├─ 是 → 创建联合索引（字段顺序按高频查询条件排序，最左放等值查询字段，范围查询字段放右侧）
   │    └─ 同时存在单字段高频查询（如仅查第二个字段）？
   │         ├─ 是 → 额外创建单字段索引（权衡字段大小和查询频率）
   │         └─ 否 → 无需额外索引
   └─ 否 → 是否有高频单字段查询？
        ├─ 是 → 创建单字段索引（多个字段则多个索引，字段小优先）
        └─ 否 → 仅在必要时为低频需求创建单字段索引（避免全表扫描）

索引下推

MySQL5.6引入的查询优化技术
通过将部分查询条件从服务层下推至引擎层，在扫描索引阶段直接过滤数据，减少回表
在传统查询流程中，存储引擎只负责根据索引定位行 ID，然后将这些 ID 返回给服务层，由服务层回表读取完整数据后再应用查询条件（如age=10）
而索引下推（ICP）将原本由服务层执行的索引字段过滤条件（如 age=10），下沉到存储引擎层执行

对比示例

假设有查询 SELECT * FROM tuser WHERE name LIKE ‘张%’ AND age=10;，且存在联合索引 (name, age)

无索引下推（ICP）时：
- 存储引擎扫描索引：通过 (name, age) 索引定位所有满足 name LIKE ‘张%’ 的索引项，获取对应的行 ID（假设找到 1000 条）
- 回表获取完整数据：将这 1000 个行 ID 全部回表，读取完整的行数据
- 服务层过滤剩余条件：服务层遍历这 1000 行数据，逐一检查 age=10，最终仅 100 条符合条件，丢弃其余 900 条
有索引下推（ICP）时：
- 存储引擎扫描索引并同时检查所有条件：
  存储引擎扫描 (name, age) 索引，同时应用 name LIKE ‘张%’ 和age=10 两个条件：
  - 先定位 name LIKE ‘张%’ 的索引项；
  - 对每个匹配的索引项，直接检查其 age 值是否为 10；
  - 仅保留同时满足两个条件的索引项（假设最终筛选出 100 条）。
- 仅回表符合条件的行 ID：将这 100 个行 ID 回表，读取完整数据。
- 服务层直接返回结果：
  由于存储引擎已提前过滤 age=10，服务层无需再次检查，直接返回这 100 行数据。