【MySQL】索引简述-一一网

索引是用来快速查找记录的数据结构，相当于书籍的目录。在 MySQL 中，索引是在存储引擎层实现的，因此没有统一的索引标准，每个存储引擎都可以选择适合自己的索引，甚至像 CSV 和老版 Archive 引擎会选择不支持索引。

本文是笔记类型文章，只有结论没有证明，可用于复习巩固知识，不能用于新知识的学习。如有错误，恳请指正，不胜感谢。

转载请于文首标明出处：【MySQL】索引简述 – 掘金 (juejin.cn)

索引的类型

要谈论 MySQL 中索引的类型，必须从不同的角度进行讨论。

从数据结构的角度来说，MySQL 索引分为 B 树索引、B+ 树索引、T 树索引、哈希索引、全文索引和 R 树空间索引。
从数据存储的角度来说，MySQL 索引分为聚集索引和辅助索引。
从逻辑意义的角度来说，MySQL 索引分为主键索引与非主键索引、单列索引与多列索、唯一索引与非唯一索引、前缀索引与后缀索引。
从查询方式的角度来说，MySQL 索引分为覆盖索引和非覆盖索引。

聚集索引就是存储的数据与索引数据结构合并在一起的索引，整个索引数据结构就存储了所有的数据，后文有更具体的解释。

索引的逻辑分类

索引的逻辑分类比较容易理解，先从索引的逻辑分来开始说明。

主键索引与非主键索引

主键是数据的唯一标识，以主键为 Key 的索引称为主键索引。非主键索引就是除了主键之外的一切索引。

单列索引与多列索引

索引可以由多个字段组成，由单独一列作为 Key 的索引称为单列索引，由多列组成作为 Key 的索引称为多列索引，也叫联合索引。

唯一索引与非唯一索引

唯一索引实际上更多的是一种约束。建立唯一索引的列中不得出现相同的 key，即构成索引的字段不得出现重复。主键就是最典型的唯一索引。而非唯一索引就是没有这种约束的索引。

前缀索引与后缀索引

前缀索引指利用某字段数据的前缀建立的索引，对于长字符串类型的字段我们不可能把整个字符串作为索引存储起来，因此可以截取其最前面 N 个字符进行索引，这就是前缀索引。前缀索引通常用于超长 Varchar、Blob 或者 Text 类型字段。它所选择的前缀长度取决于其索引选择性。

索引选择性指不重复的索引值和表中总记录数的比值，比如唯一索引不存在重复索引值，因此索引选择性为 1。如果一个索引存在的重复很多，那么不重复的索引值就很少，索引选择性就越低。因此索引选择性越高越好。

MySQL 不支持后缀索引，但是我们可以自己实现后缀索引，例如将字符串翻转过来再建立前缀索引，此时就是后缀索引了。

索引的匹配与失效

由于索引类型非常多，因此会有许多匹配方式：

全值匹配：指的是索引在匹配时使用索引中的所有列进行匹配，如 WHERE name = 'Allen' AND addr = 'Guangzhou'。
匹配最左前缀：指的是在多列索引的匹配中，只需要使用到最左几列即可完成匹配，如 WHERE name = 'Allen'。
匹配列前缀：指的是匹配某一列值的开头部分，如 WHERE name LIKE 'All%'。
匹配范围值：指的是通过范围进行匹配，如 WHERE id > 1024 AND id < 2048。
精确匹配再范围匹配：如 WHERE name = 'Allen' AND first_name LIKE 'Thrump'。
覆盖索引匹配：指的是只访问多列索引所覆盖到的列的数据，如 WHERE teacher_id = 1024 AND student_id > 202000000 AND student_id < 202000103。

只有合法地使用索引，才能够让索引生效，否则索引只会徒占空间，对于多列索引而言，存在着许多查询生效的规则，这些规则存在的原因，都是因为多列索引在建立时，先由前面的列决定顺序，再由后面的列决定顺序。如先排第一列，再排第二列，再排第三列等等。因此，后面列的顺序是基于前面列的，一旦查询条件中没有用到前面列的顺序，后面列的索引就没法生效了：

如果不按照索引的最左列开始向右进行多列查询，整个索引就会失效。
如果跳过索引的中间列，后面的索引就会失效，只能用到前面按序的列。
如果查询中某个列有范围查询，则后面的索引就会失效。
如果查询中有 like 条件，只有匹配最左前缀才能够使索引生效，同时后面的列就不生效了。

B 树与 B+ 树索引

B 树索引就是以 B 树为数据结构存储的索引，B+ 树同理。

B 树

B 树全称多路搜索树，B 的含义为 Balance 而非 Binary，是为磁盘等外存储设备设计的一种平衡查找树，MyISAM 就是使用 B 树作为实现索引的数据结构。

以三阶 B 树为例。每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的 key 和三个指向子节点的指针，两个 key 将数据划分成的三个范围域。由于范围域和 key 都是升序排序，所以对于一块载入的磁盘空间可以使用二分查找查找元素。如果命中关键字则直接返回数据，如果不命中则进入相应范围的子节点查询。

树的阶数指一个节点的子节点数量。

优点：由于 B 树每个节点内部都是有序的，因此节点内数据查询可以使用二分查找的方式查询，时间复杂度为 $O(\log_2N)$ ，而且也非常适合范围查询。同时，一棵 M 阶树的节点会存储 M 个指针和 M-1 个 Key，因此整体查询的渐进复杂度为 $O(\log _MN)$ 。这样的查询速度还是很快的，而且由于是多叉树，树的深度减少，更适合磁盘检索。
缺点：B 树存在的问题在于，非叶子节点也会存储数据，由于每个节点大小是固定的，如果节点存储的数据越大，节点能够保存的指针数量就会越少，随着阶数的减少，就必定要树的深度，这样就会使 IO 次数增加。对于普通索引还好，只是将主键 ID 作为 data 存储，但对于主键索引，data 就是整条记录，在这种情况下，整个 B 树的阶数会变得非常小。

B+ 树

B+ 树是 B 树的一种优化，InnoDB 就是使用 B+ 树作为实现索引的数据结构。

B+ 树

由于 B 树的问题是父节点也存储数据，导致父节点的指针数量减少，因此 B+ 树的优化就在于，将所有数据都存放在叶子节点，父节点只存放 key 和指针，不存放数据，这样就可以大大提高父节点的指针数了。

InnoDB 中默认页大小为 16K，假设指针长度为 64 位，主键的类型为长整型，二者都为 8 字节。那么一个 B+ 树父节点可以存储的指针数是：16 * 1024 / (8 + 8) = 1024。因此一个父节点可以拥有 1024 个子节点。深度为三的 B+ 树总共拥有 $1024^2 = 1,048,576$ ，也就是约一百万个叶子节点。如果一行数据是 512 字节，那么三层的 B+ 数可以存储三千多万行记录了。

哈希索引

哈希索引基于哈希表实现，这就使得它的查询速度非常快，基于哈希索引的存储引擎有 Memory 和 NDB 引擎。Memory 的哈希索引有以下几个特点：

Memory 采用拉链法的方式解决哈希冲突，因此哈希冲突多的时候，查询和修改都会比较慢。
Memory 的哈希索引只存储索引值和行指针，因此无法实现覆盖索引。
Memory 的哈希索引是无序的，只有精确匹配才能进行有效的查询。因此无法使用范围查询，只支持等值比较查询，如 =、in 和 <=>。
哈希索引是绝对不支持部分匹配的，因为计算哈希值必须索引的所有字段都参与计算。

<=> 用于和 NULL 进行比较：

(a = NULL) 结果为 NULL
(NULL = NULL) 结果为 NULL
(a <=> NULL) 结果为 0
(NULL <=> NULL)  结果为 1
复制代码

全文索引

全文索引是一种特殊的索引，如它的名字所描述，它是针对大文本类型所设计的索引。对于一个超长的字符串类型字段，我们不可能将它所有的内容都作为索引，全文索引通过抽取文本关键词的方式生成索引。在使用时通过关键字的匹配进行查询过滤。

全文索引最初只对英文有效，因为可以利用空格进行分词，MySQL5.7.6 开始，引入了一个新的全文分析器来解决这个问题，并且对 MyISAM 和 InnoDB 引擎都有效。

聚集索引与辅助索引

聚集索引有的叫聚簇索引，也有的叫索引组织表，指的是一种数据存储方式，指数据与索引的数据结构存储在一起。如 InnoDB 的主键索引中所有叶子节点都存储了对应行的数据。因为数据肯定只是存储在一个地方，所以一个表只能有一个聚集索引。如果 InnoDB 表没有定义主键，那么它会选择一个唯一非空索引代替，如果没有唯一非空索引，则会隐式地创建一个整型主键作为聚集索引的 Key。

而辅助索引就是除了聚集索引之外的其他索引，不具有数据存储的功能，索引 B+ 树叶子节点存储的 data 也只是主键的值而已。因此通过辅助索引查询数据，实际上是先用它来找主键，然后再去聚集索引找行数据。

辅助索引由于只保存主键值，如果主键和索引都是长整型，叶子节点才 16 字节，这种情况下三层的 B+ 树可以达到十亿条数据。

使用主键查询之所以快的原因就是，主键和数据放在一起，不需要想辅助索引一样进行二次查询。

覆盖索引和非覆盖索引

覆盖索引是一个从查询方式来讲的概念，如果一个辅助索引的索引 Key 包含了查询需要的所有字段，那我们就称之为覆盖索引。比如我们的索引是基于 name, age, gender 建立的，如果查询条件能命中索引并且只查询 SELECT name, age, gender、SELECT name, age 或者 SELECT name，那么在查询时，就不需要根据主键去聚集索引那里查找行记录了，因为索引的 Key 已经包含了我们要的所有数据。

覆盖索引有这些好处：