MySQL索引结构

MySQL 索引结构详解

MySQL 索引的核心设计目标是减少磁盘 IO 次数—— 因为磁盘 IO 是查询性能的主要瓶颈。通过合理的索引结构（如树结构），可将磁盘 IO 次数控制在 O (logN) 级别，显著提升查询效率。以下从索引设计逻辑、结构类型、核心特性及主键设计原则展开说明。

不同存储引擎的索引实现差异

MySQL 的索引实现与存储引擎强相关，不同引擎对索引技术的支持不同：

存储引擎	主要索引类型	说明
InnoDB	B+Tree 索引	5.6 后支持 FullText 全文索引，5.7 后通过 ngram 插件支持中文全文索引
MyISAM	FullText 全文索引、B+Tree 索引	支持 R-Tree 空间索引（但 MySQL 对 GIS 支持有限）
Memory	Hash 索引	数据存于内存，索引基于 Hash 表实现

索引结构核心解析

为什么不使用二叉树或红黑树？

索引设计需避免高深度（减少磁盘 IO），而二叉树和红黑树存在明显缺陷：

• 二叉树：可能退化为链表（如有序插入时），导致磁盘 IO 次数变为 O (N)，完全失去索引价值。
• 红黑树：虽能保证 O (logN) 的查询复杂度，但仅支持 2 个子节点，数据量大时树深度过高（如 100 万条数据需约 20 层），磁盘 IO 次数过多。

B 树（多路搜索树）

为减少树深度，B 树采用 “多路分支” 设计（允许一个节点有多个子节点），其结构定义如下：

• 非叶子节点最多有 M 个儿子（M>2），根节点儿子数为 [2,M]，其他非叶子节点儿子数为 [M/2,M]。
• 每个节点存储 [M/2-1, M-1] 个关键字，关键字有序（k [i]<k [i+1]）。
• 非叶子节点的指针数 = 关键字数 + 1，指针指向对应范围的子树（如 p [1] 指向小于 k [1] 的子树）。
• 所有叶子节点在同一层。

缺陷：非叶子节点既存索引也存数据，导致单个节点存储的索引数量少，树深度仍较高；且叶子节点无链接，不支持范围查询。

B+Tree（InnoDB 默认索引结构）

B+Tree 是 B 树的优化版本，是 InnoDB 索引的核心结构，其设计完美适配减少磁盘 IO 和支持范围查询的需求。

结构特点：

• 非叶子节点仅存索引：不存储数据，仅作为索引指引，因此单个节点可存储更多索引，降低树深度（减少磁盘 IO）。
• 叶子节点存全量数据：所有叶子节点包含完整数据记录，且按关键字有序连接（形成双向链表）。
• 查询必达叶子节点：无论查询单值还是范围，最终都需访问叶子节点，保证查询逻辑一致。

聚簇索引与非聚簇索引：

InnoDB 中 B+Tree 索引分为两种，核心差异在于叶子节点存储内容：

• 聚簇索引（主键索引）：
  • 按主键构造 B+Tree，叶子节点直接存储完整数据行（索引与数据同存）。
  • 每张表仅 1 个聚簇索引（由主键决定）。
  • 优势：主键排序查询和范围查询速度极快（直接访问叶子节点数据）。
• 非聚簇索引（二级索引）：
  • 叶子节点存储索引字段值 + 主键值（不存完整数据）。
  • 一张表可有多非聚簇索引（不影响聚簇索引的组织）。
  • 查询逻辑：先通过非聚簇索引找到主键，再通过聚簇索引查完整数据（此过程称为回表）；若查询字段仅为索引字段和主键，则无需回表（称为索引覆盖）。

不同点是叶节点是否存放着一整行数据

加载时是以页为基本单位的，每次加载一页或多页，InnoDB的pageSize可以通过命令show variables like 'innodb_page_size'得到，默认值是16k

B+Tree 的核心优势：

• 非叶子节点仅存索引，单页（InnoDB 默认 16KB）可存更多索引，减少磁盘 IO 次数。
• 叶子节点有序链表，高效支持范围查询（如 “id>100 and id<200”）。
• 树高稳定（通常 3-4 层），查询时间复杂度稳定为 O (logN)。

Hash 索引

基于哈希表实现，仅支持精确匹配，适用于等值查询场景。

特点：

• 查询效率：单次哈希计算即可定位，等值查询速度快于 B+Tree。
• 局限性：
  • 不支持范围查询、排序（哈希值无序）。
  • 不支持部分索引列匹配（需用全部索引列计算哈希值）。
  • 哈希冲突时需遍历链表（性能下降）。
• 适用场景：仅 Memory 引擎默认支持，InnoDB 有 “自适应哈希索引”（高频索引值在内存中自动构建哈希索引）。

R-Tree（空间索引）

用于存储地理空间数据（如经纬度），支持基于几何类型的索引。

• 仅 MyISAM 引擎支持，限制较多（如仅支持 NOT NULL 列）。
• MySQL 对 GIS 支持不完善，实际应用极少。

全文索引

用于大文本字段（char、varchar、text）的关键词搜索，类似搜索引擎逻辑。

• 不直接比较索引值，而是查找文本中的关键词。
• 适用于MATCH AGAINST查询，替代低效的LIKE '%关键词%'。
• MyISAM 和 InnoDB（5.6+）均支持，InnoDB 5.7 + 通过 ngram 插件支持中文。

主键设计原则

主键作为聚簇索引的核心，设计直接影响 B+Tree 性能：

1. 不宜过大：
   主键值会存储在所有非聚簇索引的叶子节点中，若主键过大（如 UUID），会占用大量非叶子节点空间，导致树深度增加，磁盘 IO 增多。
2. 建议自增：
   自增主键插入时始终在 B+Tree 末尾添加，避免页分裂（调整树结构）；若用 UUID 等无序值，插入时需频繁调整树结构，导致页分裂，严重影响性能