索引（Index）是帮助 MySQL 进行高效查询的数据结构（有序）。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构是以某种方式引用（指向）数据，这样就可以在这些数据结构之上实现高级查找算法，这种数据结构就是索引。
索引结构
MySQL 的索引结构是在存储引擎层实现的，不同的存储引擎有不同的结构，主要包含以下几种:
| 索引结构 | 描述 |
|---|---|
| B+ Tree 索引 | 最常见的索引类型，大部分引擎都支持 B+ 索引 |
| Hash 索引 | 底层数据结构是用哈希表实现的，只有精确匹配索引列的查询才能有效，不支持范围查询 |
| R-Tree （空间索引） | 空间索引是通过 MyISAM 引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少 |
| Full-Text（全文索引） | 是一种通过建立倒立索引，快速匹配文档的方式，类似于 Lucene、Solr、ES |
| 索引 | InnoDB | MyISAM | Memory |
|---|---|---|---|
| B+ Tree 索引 | 支持 | 支持 | 支持 |
| Hash 索引 | 不支持 | 不支持 | 支持 |
| R-Tree （空间索引） | 不支持 | 支持 | 不支持 |
| Full-Text（全文索引） | 5.6版本后支持 | 支持 | 不支持 |
B 树与 B+ 树
B 树
- 基本结构：B 树是一种自平衡的多路查找树，能够保持数据有序。每个节点包含多个键和子节点指针，所有叶子节点具有相同的深度。
- 特点：
- 每个节点最多有
m个子节点，其中m是树的阶。 - 根节点至少有两个子节点，除根节点外的所有节点至少有
⌈m/2⌉个子节点。 - 每个节点的键按升序排列，节点的子树按键值范围划分。
- 可以直接在非叶子节点上存储数据。
- 每个节点最多有
B+ 树
- 基本结构：B+ 树是 B 树的一种变体，所有数据都存储在叶子节点上，内部节点只存储键和指向子节点的指针。
- 特点：
- 叶子节点通过链表相连，形成一个有序的数据链表。
- 每个叶子节点存储实际的数据记录（数据指针），所有非叶子节点仅存储键值用于索引。
- B+ 树的分支因子通常更高，树的高度更小。
- 更高效的范围查询：通过叶子节点链表可以快速访问连续的数据。
区别与联系
- 数据存储位置：
- B 树：数据可以存储在所有节点上。
- B+ 树：数据只存储在叶子节点上。
- 查询性能：
- B 树：查找时可能访问所有层节点。
- B+ 树：由于所有数据在叶子节点，查找路径更稳定，每次都需要遍历到叶子节点。
- 顺序访问性能：
- B 树：顺序访问效率较低。
- B+ 树：叶子节点有顺序链表，顺序和范围查询性能极高。
为什么 MySQL 选择 B+ 树，不是 B 树 或者 Hash
相较于 B 树
- 更少的磁盘 I/O
- B+ 树由于每个节点可以存储更多的指针（更高的分支因子），从而大幅降低树的高度。这意味着从根节点到叶子节点的路径更短，因此访问数据时需要的磁盘 I/O 次数更少。
- 更高效的范围查询
- B+ 树的叶子节点通过链表相连，形成一个有序的数据链表。这种结构使得 B+ 树在进行范围查询时非常高效，只需在链表中顺序遍历即可，不需要返回上层节点。
- 数据和索引分离
- B+ 树将数据存储在叶子节点，内部节点只存储索引，这样的分离有助于缓存更多的索引节点，提高查询速度。相对于 B 树，B+ 树更容易利用 CPU 缓存和内存页结构。
相较于 Hash
- 支持范围查询
- B+ 树的叶子节点通过链表连接，形成一个有序的数据链表。可以通过顺序扫描叶子节点高效地执行范围查询。而 Hash 仅支持等值查询
- 顺序查询效率更高
- B+ 树的叶子节点是有序的，对于连续的记录查询非常高效，而 Hash 是无序存储数据的。
- 支持多列索引
- B+ 树支持多列索引查询，并且在多列查询时，可以有效地使用索引的前缀来优化查询性能。而哈希值是基于整体计算的，无法利用部分列进行查询
- 处理大量重复值
- 在处理重复值时，不会有性能问题，因为叶子节点是有序的，可以按顺序检索到所有重复值。而对于 Hash ，如果有大量重复值，可能会导致哈希碰撞增多，从而降低查找效率。
- 空间利用率更高
- B+ 树通过节点的分裂和合并，可以保持树的平衡和空间的有效利用。而哈希表在扩展时需要重新哈希，且空间利用率在负载因子较高时会下降。
索引类型
按索引性质
- 主键索引（Primary Key Index）：
- 唯一性：主键索引是唯一的，不能有重复值，并且不允许为 NULL。
- 默认自动创建：当为表定义主键时，数据库会自动创建主键索引。
- 用途：快速定位唯一的行。
- 唯一索引（Unique Index）：
- 唯一性：唯一索引的值必须唯一，但可以有一个 NULL 值。
- 用途：确保某列或多列的值唯一，防止重复数据。
- 普通索引（Normal Index）：
- 非唯一：普通索引允许重复值。
- 用途：加速对指定列的查询，但不强制唯一性。
- 全文索引（Full-Text Index）：
- 用途：用于文本字段的全文搜索，适合于大文本数据的高效查询。
- 支持：在 InnoDB 和 MyISAM 引擎中都有支持，但存在不同的实现方式。
- 空间索引（Spatial Index）：
- 用途：专用于地理空间数据类型的索引，支持对空间数据的高效查询。
按常见的基于 InnoDB B+ 树索引角度（存储性质）
- 聚集索引（Clustered Index）
- 定义：InnoDB 的聚簇索引将主键索引和数据行存储在一起，叶子节点存储的是完整的数据行记录。
- 特点：
- 一个表只能有一个聚簇索引（通常是主键）。
- 由于数据行和主键索引在一起，主键查询的性能非常高。
- 聚簇索引中的数据是物理上连续存储的，减少了磁盘访问的次数。
- 选取策略：
- 如果存在主键，主键索引就是聚集索引。
- 如果不存在主键，将使用第一个唯一（UNIQUE）索引作为聚集索引。
- 如果表没有主键且没有合适的唯一索引，则 InnoDB 会自动生成一个 rowid 作为隐藏的聚集索引。
- 辅助索引（Secondary Index）
- 定义：除了聚簇索引之外的所有索引都是辅助索引，叶子节点存储的是主键的值，而不是直接的数据行。
- 特点：
- 辅助索引用于快速定位主键，再通过主键查找实际数据（回表操作）。
- 辅助索引不强制数据的物理顺序，因此对插入和删除的性能影响较小。
按索引结构
即上面提到的四种索引结构。
- B+ 树索引
- Hash 索引
- 全文索引
- R-Tree 索引