MySQL索引详解【B+Tree索引、哈希索引、全文索引、覆盖索引】

比眉伴天荒 2022-09-12 03:50 308阅读 0赞

前段时间面试每次提到索引，我就巴拉巴拉说一堆，然后到了说说你理解的 **B+tree索引**我就懵逼了。

直接说`B+tree`可能并不是很好理解，下面我们从最简单的二叉查找树开始慢慢循序渐进。

## 一、B+Tree索引 ##

### 1、二叉查找树 ###

在最开始学习树的时候，我们一定学习过这样一种结构的二叉树**根结点大于它的左节点，小于它的右节点**。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP6YGT5LuZOTc_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

如果我们要在上述的二叉树里面去查询 `6` ,只需要三步即可

1.  找到根节点 `10` ，判断6比10小，寻左结点
2.  找到结点 `5` ， 判断6比5大，寻右结点
3.  找到结点 `6`，判断6符合查找需要

### 2、平衡二叉树（AVL树） ###

熟悉二叉树的都知道，在特殊情况下，上面的二叉树可能形成如下结构

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP6YGT5LuZOTc_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]

如果在此种二叉树上面查询结点，那就是一个个进行对比了，效率相当低下，这个时候我们就引入**平衡二叉树**的概念。

平衡二叉树有如下要求：

*  每个根结点的左节点小于它，右节点大于它
 *  每个结点的左右子树高度差不能超过 `1`

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP6YGT5LuZOTc_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]

**每次添加元素的时候，代码都会判断当前结构是否还属于平衡的，如果不是就进行调整。调整的代价也是挺大的，所以平衡二叉树一般用于多查询的功能里面。**

### 3、B-Tree ###

我们所有的数据最终都是存在磁盘上面的。平衡二叉树有一个问题，那就是数据量如果过大的话，那么这个树就会很长很长，这样会导致频繁的进行磁盘IO，这样效率就降低了很多。

**在数据库里面数据不是一个个存储，而是按照页来存储，一页是16kb大小。**

B-Tree可以解决频繁的IO问题，它把数据按照页进行存储。

假如我们有这样一张表，里面有两个字段 id、name，id是主键

那么它的存储结构如下：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP6YGT5LuZOTc_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 3]

**页之间也是双向指向的**

从上面的结构我们可以看出，每一**页**里面存储索引和对应的数据，并且是多条数据，而不是单一的。

一般我们的根页（页1）是存储在内存中的，然后我们进行判断一个个读取页到内存，使用这种结构可以在查询更少的页，就可以查询到我们想要的数据了。

### 4、B+Tree ###

上面的结构也存在一种问题，因为每一页的大小是固定的（16KB），如果既要存储索引，又要存储数据，那么我们16KB也存储不了多少索引数据（尤其是在大表中），这样还是会进行频繁的IO处理。

**如果我们只在结点中存储索引，在叶子结点里面存储数据，这样我们每一页都可以存储更多的索引。**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP6YGT5LuZOTc_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 4]

#### 4-1、精确查找 ####

如果我们要查询 `1`，先找到页1，再找到页2，最后从叶子结点找到对应的数据。

#### 4-2、范围查询 ####

如果我们要找到 `WHERE id > 2 AND id < 5`

和上面一样会先精确查询到`2`，叶子结点上下和左右都是有双向指针的，一个个向下去找，当找打5的时候发现 `id < 5` 已经不满足要求了，就结束查找。

### 5、总结 ###

*  B+Tree 把所有的数据都存储在叶子结点上面，非叶子结点只存储索引，这样可以保证最少次数的IO提高索引查询的性能。
 *  存储的时候不是一个结点一个结点的存储，而是以页的方式进行存储，每一页的大小是16KB。

## 二、Hash索引 ##

Hash索引就是根据给定的字段，进行创建Hash值。Hash索引可以很快的进行单个匹配度查询，但是无法做到范围查询。

如果你创建组合索引（A、B），它是根据AB俩个字段进行Hash的，所以当你单独使用A进行条件筛选的时候，是无法使用索引的。

## 三、全文索引 ##

全文索引是一个比较特殊的索引，一般用的也很少。它查找的是文本中的关键词，而不是比较索引中的值。全文索引更类似于搜索引擎做的事。

## 四、聚簇索引和非聚簇索引 ##

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。在InnoDB的聚簇索引实际上在同一个结构中保存了B+Tree索引和数据行。当表有聚簇索引时，它的数据行实际上存放在索引的叶子页中。

因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。（不过，覆盖索引可以模拟多个聚簇索引的情况，下面说明）

在InnoDB中会选择主键来作为聚簇索引，如果没有定义主键，InnoDB会选择一个唯一的非空索引代替。如果没有这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引。

**聚簇索引：** 它的非叶子结点存储的是，主键索引（大多数是的），叶子结点是存储的行数据。

**非聚簇索引：** 它的非叶子结点存储的是，索引值，叶子结点存储的是这个索引对应的主键索引。

所以我们使用非聚簇索引进行查询数据的时候，会查询两次先查询到聚簇索引，再去通过聚簇索引找到相关的数据，这个过程称之为**回表**。

## 五、其它 ##

### 5-1、为什么主键索引比其它索引快 ###

因为非主键索引对应的是非聚簇索引，所以在查询的时候需要进行回表操作，先在查询找到对应的主键索引，再通过主键索引去查询真实的数据。

但也不是全部的主键索引都比其它索引快，比如我们下面要说的覆盖索引。

### 5-2、覆盖索引 ###

假设我们有这样一张表

CREATE TABLE `t_user` (
      `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '主键id',
      `name` varchar(50) DEFAULT NULL COMMENT '姓名',
      `age` int(3) DEFAULT NULL COMMENT '年龄',
      `sex` tinyint(1) DEFAULT NULL COMMENT '性别',
      PRIMARY KEY (`id`),
      KEY `name_age` (`name`,`age`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

我们需要查询 name和age，sql如下

SELECT name, age FROM t_user

因为我们建立了 name，age 的索引，并且我们查询的数据也就是这两个，所以我们不需要再去进行回表了。

**覆盖索引：** 如果一个索引包含（或者说覆盖）所有需要查询的字段的值，我们就称之为“覆盖索引”。

注：覆盖索引必须要存储索引列的值，而哈希索引、空间索引和全文索引等都不存储索引列的值，所以MySQL只能使用B+Tree索引做覆盖索引。另外，不同的存储引擎实现覆盖索引的方式也不同，而且不是所有的引擎都支持覆盖索引。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP6YGT5LuZOTc_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/b9fb7347b2bc484ca87b1c1f570e66b3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP6YGT5LuZOTc_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: /images/20220828/766bfe34fafe4117b708beecc12dbb44.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP6YGT5LuZOTc_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]: /images/20220828/d48a5282ecac41f3a79138647a235c83.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP6YGT5LuZOTc_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 3]: /images/20220828/fab334ea8ff3483e84ee74fbd63ebeeb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP6YGT5LuZOTc_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 4]: /images/20220828/7f17dd97e773411d9f876e9fec91fb87.png