一、MySQL 索引概述

首先明确一点是索引是在存储引擎层实现的，而不是在服务器层实现的，所以不同存储引擎具有不同的索引类型和实现。

对于常用的InnoDB 存储引擎，支持一下几种常见的索引：

  • B + 树索引
  • 全文索引
  • 哈希索引

而在整个 MySQL 中，还有另一种主要索引：R-Tree 索引。

特性 说明 InnoDB MyISAM MEMORY
B 树索引（B-Tree indexes） 自增ID物理连续性更高，二叉树、红黑树高度不可控 yes yes yes
R 树索引 （R-Tree indexes） 空间索引 yes
哈希索引（Hash indexes） 无法做范围查询 yes yes
全文索引（Full-text indexes） yes yes

B+ 索引就是传统意义上的索引，是目前关系型数据库系统中查找最为常用和最为有效的索引。因为不再需要进行全表扫描，只需要对树进行搜索即可，因此查找速度快很多。除了用于查找，还可以用于排序和分组。

在 MySQL 中，MyISAM 引擎和 InnoDB 引擎都是使用 B+Tree 作为索引结构，但是，两者的实现方式不太一样。非聚簇索引与聚簇索引之分。

InnoDB 存储引擎支持的哈希索引是自适应的，InnoDB 存储引擎会根据表的使用情况来为表生成哈希索引，不能人为设置。

二、B-Tree 结构

本部分来自程序员小灰的公众号

2.1 B- 树

B 树是一种多路平衡查找树，它的每个节点最多包含k个孩子，k 被称为 B 树的阶。 k的大小取决于磁盘页的大小。B 树的设计是为了使得一个查找树尽可能“矮胖”， 从而解决磁盘IO 的要求，在这种特定的查找场景下，尽可能提高查找效率。

一个m 阶的B树（Ballance Tree）具有如下几个特征：

  1. 根结点至少有两个子女。

  2. 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m

  3. 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

  4. 所有的叶子结点都位于同一层。

  5. 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

文字描述很难理解，以一个3阶的B- 树为例就会很清晰。

image-20211215101441502

分析：

  • 这棵树中，咱们重点来看(2, 6) 这个节点。该节点有两个元素2和6，又有3个孩子，数量都小于阶数。满足第2, 3条特征。
  • 从整棵树来看，根节点包含2个孩子；所有叶子节点都在同一层；每个节点中的元素从小到大排列。

查找：

假如我们要查询的数值为5.

image-20211215102321541

image-20211215102339986

第二次磁盘IO ， 在内存中与（2， 6）比较。

第三次磁盘IO，在内存中与（3，5）比较。

插入与删除：直接看小灰的

2.2 B+ 树

B+ 树是基于B- 树的一种变体，有着比B- 树更高的查询性能。

一个m 阶的B+树具有如下几个特征：

  1. 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

  2. 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

  3. 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

image-20211215102942251

分析：

  • 可以知道结构与B-树类似，都是多路平衡。但在细节上有不同。
  • 以（2，5，8）节点为例，该节点有3个元素，并且有3个孩子，这一点与B-树不同；每个元素还会出现在孩子节点中，而且是孩子节点的最大元素。
  • 叶子节点同样是排好序的，多了一个指向下一个叶子节点的指针，形成了一个有序链表。

B+ 树还具有一个特点，这个特点实在索引之外，确是至关重要的特点。那就是[卫星数据]的位置。所谓卫星数据，指的是索引元素所指向的数据记录。比如数据库中的某一行。在B- 树种，无论中间节点还是叶子节点都带有卫星数据。

image-20211215103549859

image-20211215103618308

需要指出的是：B+ 树索引并不能找到一个给定键值的具体行。B+ 树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读入到内存，再在内存中进行查找，最后得到要查找的数据。这一点与上述描述是一致的，比如找到索引包含5的节点（3，5），该节点表示的就是一个页，数据data就存在这个页中。

B+树的优势：

  1. 单一节点存储更多的元素，使得查询的IO次数更少。

  2. 所有查询都要查找到叶子节点，查询性能稳定。

  3. 所有叶子节点形成有序链表，便于范围查询。

三、B+ 索引

3.1 MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：

img

这里设表一共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：

img

同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

MYISAM 引擎的表的.MYI 文件包含了表的索引， 该表的索引(B+树)的每个叶子非叶子节点存储索引， 叶子节点存储索引和索引对应数据的指针，指向.MYD 文件的数据。

这是MySQL 的表的文件截图：

img

3.2 InnoDB 索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

img

上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：

img

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

3.2 聚集索引与非聚集索引

  1. 聚集索引

    聚集索引即索引结构和数据一起存放的索引。主键索引属于聚集索引。

    优点：

    聚集索引的查询速度非常的快，因为整个 B+树本身就是一颗多叉平衡树，叶子节点也都是有序的，定位到索引的节点，就相当于定位到了数据。

    缺点：

    • 依赖于有序的数据 ：因为 B+树是多路平衡树，如果索引的数据不是有序的，那么就需要在插入时排序，如果数据是整型还好，否则类似于字符串或 UUID 这种又长又难比较的数据，插入或查找的速度肯定比较慢。
    • 更新代价大 ： 如果对索引列的数据被修改时，那么对应的索引也将会被修改， 而且况聚集索引的叶子节点还存放着数据，修改代价肯定是较大的， 所以对于主键索引来说，主键一般都是不可被修改的。

  2. 非聚集索引

    非聚集索引即索引结构和数据分开存放的索引。 二级索引（辅助索引）属于非聚集索引。

    优点：

    更新代价比聚集索引要小 。非聚集索引的更新代价就没有聚集索引那么大了，非聚集索引的叶子节点是不存放数据的

    缺点：

    • 跟聚集索引一样，非聚集索引也依赖于有序的数据；

    • 可能会二次查询(回表) :这应该是非聚集索引最大的缺点了。 当查到索引对应的指针或主键后，可能还需要根据指针或主键再到数据文件或表中查询。

      尽量使用覆盖索引，避免回表查询。

四、哈希索引

InnoDB 引擎有一个特殊的功能叫 “自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。

自适应哈希索引会占用InnoDN Buffer Pool。对于某些工作负载，如使用1like 和% 的范围查询以及高并发的 joins，不适合使用自适应哈希索引，维护哈希索引结构的额外开销会带来严重性能损耗。这种情况更适合于禁用自适应哈希索引。

哈希索引能以 O(1) 时间进行查找，但是失去了有序性，它具有以下限制：

  • 无法用于排序与分组；
  • 只支持精确查找，无法用于部分查找和范围查找；

五、全文索引

MyISAM 存储引擎支持全文索引，用于查找文本中的关键词，而不是直接比较是否相等。查找条件使用 MATCH AGAINST，而不是普通的 WHERE。InnoDB 存储引擎在 MySQL 5.6.4 版本中也开始支持全文索引。

全文索引通常使用倒排索引（inverted index）来实现。倒排索引是通过记录关键词到其所在文档的映射实现的。

img

以 ES 为例：

Elasticsearch 使用一种称为 倒排索引 的结构，它适用于快速的全文搜索。一个倒排索引由文档中所有不重复词的列表构成，对于其中每个词，有一个包含它的文档列表。

例如，假设我们有两个文档，每个文档的 content 域包含如下内容：

  1. The quick brown fox jumped over the lazy dog
  2. Quick brown foxes leap over lazy dogs in summer

为了创建倒排索引，我们首先将每个文档的 content 域拆分成单独的 词（我们称它为 词条 或 tokens ），创建一个包含所有不重复词条的排序列表，然后列出每个词条出现在哪个文档。结果如下所示：

image-20211215134016083

现在，如果我们想搜索 quick brown ，我们只需要查找包含每个词条的文档：

image-20211215134037692

两个文档都匹配，但是第一个文档比第二个匹配度更高。如果我们使用仅计算匹配词条数量的简单 相似性算法 ，那么，我们可以说，对于我们查询的相关性来讲，第一个文档比第二个文档更佳。