MySQL 学习 04 - 索引

博主： zhaojun
发布时间：2022 年 05 月 02 日
1986 次浏览
暂无评论
4634字数
分类：默认分类

# 索引

数据库的索引是一个要点, 无论是面试还是在工作中, 这个知识点都很常会用到, 你可能只是用过索引, 知道加了索引可以提高查询的性能, 但不知道为什么这样, 今天我们一起来详细了解下吧.

## 索引模型

索引有很多种存储结构, 称之为索引模型, 不同类型的模型分别对应不同的适用场景.

### 哈希表

哈希表是一种以键值对存储数据的结构 `KEY - VALUE`. 查找时输入 `key` 来查找对应点 `value`.

哈希表的思路很简单, 将值放置到数组中. 如定义一个长度为 16 的数组, 输入 `key`: `user1`, 对 `user1` 做哈希运算 (利用哈希函数), 返回一个整数, 如 `2156648`, 用这个数对 16 取余, 返回值为 8. 那么就将他放到数组的第 8 个位置.

你可能会有下面的疑惑:

* 哈希函数又是什么: 哈希函数的意图就是把任何长度输入值, 变化成固定长度的输出, 一般为整数.
* 哈希值会冲突么, 冲突了怎么办: 会冲突, 冲突了有许多中解决方式, 今天我讲一种比较常用的, 即在数组中不直接存放数据值, 而是存放一个链表, 当冲突时, 就把多个值通过链表串联起来. 类似于 Java 中 `HashMap` 的存储方式.

> 总结: **适合用于等值查询**, 不适用于范围查询. 出现大量哈希冲突的情况后, 查询效率会很低.

### 有序数组

这个就更简单了, 将所有值从小到大排序, 这样查找时, 可以采用二分法, 时间复杂度只有 `O(logN)`. 而且对范围查询的支持也非常好, 先根据二分法, 找到范围查询的左值, 然后依次遍历数组到范围查询的右值即可.

但这仅仅是查询效率很好, 但向数组中心插入值就麻烦了, 如现有数据 `[1, 5, 8, 10, 11, 13]`, 现在要插入数据值 `3`, 那么就要将 `5, 8, 10, 11, 13` 这些值都向后移动一位, 插入操作的效率为 `O(N)`, 这并不是一个理想的效率.

> 适用于范围查询. 等值查询的效率也较高, 但插入操作效率较低.

### 搜索树

#### 二叉搜索树

二叉搜索树的特点是: 每个节点的左儿子小于父节点, 父节点又小于右儿子. 如:

```

```
5
  / \
3    6
```

/ \    
2   4    8
/        / \
1        7   9

```
这是如果你找值 7, 先从根节点 5 开始找, 比 5 大, 那肯定在右边, 所以找到第二层的 6, 比 6 还大, 找到第三次的 8, 比 8 小, 最后找到第四层的 7, 这样最坏的情况也就数据在树的最后一层, 即**平均时间复杂度**为 `O(logN)`.

#### 平衡二叉树 (红黑树)

但是二叉搜索树还可能会出现一个问题是树不平衡, 如:
```

1
2
3
4
5
6
7
8
9

```
上面我们提高二叉搜索树的查询性能取决于树的高度, 现在这个数查询的性能变成了 O(N), 性能大打折扣. 为了解决这个问题, 提出了 `红黑树` 的概念. 他是一种自平衡的二叉搜索树, 即在插入节点时, 判断整个树是否是平衡的, 如果不平衡, 通过一系列旋转操作来达到平衡的目的, 在更新时维持树的平衡需要的时间复杂度也是 `O(logN)`.

> 红黑树的篇幅有点长, 不太适合放到这里, 需要详细了解的朋友, 可自行查阅相关知识.

#### N 叉树 (B 树, B+ 树)

同样的, 平衡二叉树也有一个问题, 如当数据有 100 条时, 此时树的高度为 20, 那么一次查询可能需要访问 20 个数据块, 也就是访问 20 次磁盘, 这是不能被接受的, 尤其是在机械硬盘下, 为了让一个查询更少的读取磁盘, 我们就不应该使用二叉树, 而是 N 叉树, 这个 N 取决于数据块的大小.

以 InnoDB 的一个整数字段索引为例, 这个 N 差不多是 1200, 当树高为 4 时, 可以存储 1200 的三次方个值, 大约为 17 亿, 那么这样访问磁盘的次数就大大减少了.

> InnoDB 中的 B+ 树, 就是 N 叉树的一种实现.

## InnoDB 存储模型

在 InnoDB 中, 表是根据主键顺序以索引的形式存放的, InnoDB 存储模型采用了 B+ 树索引模型, **在 InnoDB 中每一个索引都对应着一颗 B+ 树**, 每棵非主键索引树的叶子节点存储的是主键的值, 每棵主键树的叶子节点存储的是整行数据值.

假如, 我们有一个主键列为 ID 的表, 表中有字段 K, 并且在 K 上有索引, 建表语句如下:

```sql
create table T
(
    id int primary key, 
    k int not null, 
    name varchar(16),
    index (k)
) engine = InnoDB;
```

然后插入数据:

```sql
insert into T(id, k, name) values(100, 1, "A");
insert into T(id, k, name) values(200, 2, "B");
insert into T(id, k, name) values(300, 3, "C");
insert into T(id, k, name) values(400, 4, "D");
insert into T(id, k, name) values(500, 5, "E");
insert into T(id, k, name) values(600, 6, "F");
```

两个树的示意图如下:

![](https://cdn.jun6.net/2019/07/17/5d2f325737b14.png)

那么对于 **主键索引和普通索引的查询有什么区别呢?**

如查询语句 `select * from T where ID = 500`, 即根据主键进行查询, 则只需要搜索 ID 索引树.

如查询语句 `select * from T where K = 5`, 即根据普通索引进行查询, 则需要先搜索 K 索引树, 得到 ID 值 500, 再到 ID 索引树搜索. 这个过程称之为**回表**.

由于普通索引的叶子节点存储的是主键, 那么很显然, 主键长度越小越好, 所以自增主键是一个很好的选择.

当然, 如果你自己有业务字段是唯一的, 且不需要其他索引, 那么使用业务字段来做主键会适合.

## 覆盖索引

还是上面那个查询语句: `select * from T where K = 5`, 上面我们他会进行 **回表** 操作.

那么有没有可能经过索引优化, 不回表呢?

如果执行的语句是: `select ID from T where K = 5`, 这时只需要查找 ID 值, 而 ID 值已经在 k 索引树的叶子节点中了, 这样已经得到了需要的数据, 就不用进行 **回表** 操作了.

在这个查询中, 索引 k 覆盖了我们需要查询的字段,  我们称之为 **覆盖索引**.

> 由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

## 最左前缀索引

当然, 我们不能为所有需要查询的字段都建立上 **索引**, 那索引就太多了, 并且索引的维护成本也很大, 其实 **B+ 树** 这种索引结构, 支持最左前缀匹配, 来定位记录.

如现在我们有 `(name, age)` 这个联合索引 :

![](https://cdn.jun6.net/201905191038_931.png)

可以看到, 索引已经按照定义中的顺序排序好了, name 在前, age 在后, 如果 name 一致, 按照 age 排序.

此时我们需要查找所有姓名等于 "张三" 的人, 可以快速定位到 ID4, 然后向后遍历直到姓名不等于张三.

那么如果你要查找的是所有姓名的第一个字等于 "张" 的人, 也可以快速定位到 ID3, 然后向后遍历直到不符合条件.

同理, 如现在有联合索引 `(name, age, score)`, 那么我们查询 `where name = '%张' and age = 10` 也是用到了索引的, 但查询 `where name = '%张' and score = 60`, 就没有完全用到这个索引.

由此可知, 我们只要满足索引的最左前缀, 就可以用索引来加速检索, 这个最左前缀可以是联合索引的最左 `N` 个字段, 也可以是字符串索引的前 `M` 个字符.

## 索引下推

上一段我们提到了最左前缀可以用来在索引中定位记录, 但如果不符合最左前缀的部分, 应该怎么办呢?

还是以 `(name, age)` 联合索引为例. 现在需要查询 "名字第一个字是张, 年龄为 10 的男孩", sql 示意如下:

```sql
select * from tuser where name like '张%' and age = 10 and ismale = 1;
```

再次附上索引结构图:

![](https://cdn.jun6.net/201905191038_931.png)

这个索引只能用到 name 的前缀索引, 找到第一个满足条件的记录 ID3, 然后, 如何判断后面两个条件是否满足呢?

在 MySQL 5.6 之前, 只能从 ID3 开始一个一个的回表, 到主键索引上找出数据行, 再比对字段值.

而在 MySQL 5.6 引入了索引下推优化, 即在索引遍历过程中, 对索引中**包含的字段**先做判断, 先过滤到不符合条件的记录, 避免回表:

无索引下推执行流程:
![](https://cdn.jun6.net/201905191107_285.png)

有索引下推执行流程:

![](https://cdn.jun6.net/201905191107_395.png)

每个虚线表示回表一次, 在无索引下推图中, 我特意去掉了 age 值, 因为他不会看 age 的值, 只是按顺序把 name 第一个字是 "张" 的所有数据一个一个回表, 因此回表了 4 次.

而在有索引下推时, InnoDB 在 `(name, age)` 索引内部就判断了 age 是否等于 10, 对于不等于的, 直接跳过, 所以这里只回表了 2 次.

最后修改：2022 年 05 月 02 日

如果觉得我的文章对你有用，请我喝杯咖啡吧。

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

MySQL 学习 04 - 索引

zhaojun • 2022 年 05 月 02 日

# 索引

## 索引模型

索引有很多种存储结构, 称之为索引模型, 不同类型的模型分别对应不同的适用场景.

### 哈希表

哈希表是一种以键值对存储数据的结构 `KEY - VALUE`. 查找时输入 `key` 来查找对应点 `value`.

你可能会有下面的疑惑:

> 总结: **适合用于等值查询**, 不适用于范围查询. 出现大量哈希冲突的情况后, 查询效率会很低.

### 有序数组

> 适用于范围查询. 等值查询的效率也较高, 但插入操作效率较低.

### 搜索树

#### 二叉搜索树

二叉搜索树的特点是: 每个节点的左儿子小于父节点, 父节点又小于右儿子. 如:

```

```
5
  / \
3    6
```

/ \    
2   4    8
/        / \
1        7   9

#### 平衡二叉树 (红黑树)

但是二叉搜索树还可能会出现一个问题是树不平衡, 如:
```

1
2
3
4
5
6
7
8
9

> 红黑树的篇幅有点长, 不太适合放到这里, 需要详细了解的朋友, 可自行查阅相关知识.

#### N 叉树 (B 树, B+ 树)

> InnoDB 中的 B+ 树, 就是 N 叉树的一种实现.

## InnoDB 存储模型

假如, 我们有一个主键列为 ID 的表, 表中有字段 K, 并且在 K 上有索引, 建表语句如下:

```sql
create table T
(
    id int primary key, 
    k int not null, 
    name varchar(16),
    index (k)
) engine = InnoDB;
```

然后插入数据:

两个树的示意图如下:

![](https://cdn.jun6.net/2019/07/17/5d2f325737b14.png)

那么对于 **主键索引和普通索引的查询有什么区别呢?**

如查询语句 `select * from T where ID = 500`, 即根据主键进行查询, 则只需要搜索 ID 索引树.

如查询语句 `select * from T where K = 5`, 即根据普通索引进行查询, 则需要先搜索 K 索引树, 得到 ID 值 500, 再到 ID 索引树搜索. 这个过程称之为**回表**.

由于普通索引的叶子节点存储的是主键, 那么很显然, 主键长度越小越好, 所以自增主键是一个很好的选择.

当然, 如果你自己有业务字段是唯一的, 且不需要其他索引, 那么使用业务字段来做主键会适合.

## 覆盖索引

还是上面那个查询语句: `select * from T where K = 5`, 上面我们他会进行 **回表** 操作.

那么有没有可能经过索引优化, 不回表呢?

在这个查询中, 索引 k 覆盖了我们需要查询的字段,  我们称之为 **覆盖索引**.

> 由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

## 最左前缀索引

如现在我们有 `(name, age)` 这个联合索引 :

![](https://cdn.jun6.net/201905191038_931.png)

可以看到, 索引已经按照定义中的顺序排序好了, name 在前, age 在后, 如果 name 一致, 按照 age 排序.

此时我们需要查找所有姓名等于 "张三" 的人, 可以快速定位到 ID4, 然后向后遍历直到姓名不等于张三.

那么如果你要查找的是所有姓名的第一个字等于 "张" 的人, 也可以快速定位到 ID3, 然后向后遍历直到不符合条件.

## 索引下推

上一段我们提到了最左前缀可以用来在索引中定位记录, 但如果不符合最左前缀的部分, 应该怎么办呢?

还是以 `(name, age)` 联合索引为例. 现在需要查询 "名字第一个字是张, 年龄为 10 的男孩", sql 示意如下:

```sql
select * from tuser where name like '张%' and age = 10 and ismale = 1;
```

再次附上索引结构图:

![](https://cdn.jun6.net/201905191038_931.png)

这个索引只能用到 name 的前缀索引, 找到第一个满足条件的记录 ID3, 然后, 如何判断后面两个条件是否满足呢?

在 MySQL 5.6 之前, 只能从 ID3 开始一个一个的回表, 到主键索引上找出数据行, 再比对字段值.

而在 MySQL 5.6 引入了索引下推优化, 即在索引遍历过程中, 对索引中**包含的字段**先做判断, 先过滤到不符合条件的记录, 避免回表:

无索引下推执行流程:
![](https://cdn.jun6.net/201905191107_285.png)

有索引下推执行流程:

![](https://cdn.jun6.net/201905191107_395.png)

而在有索引下推时, InnoDB 在 `(name, age)` 索引内部就判断了 age 是否等于 10, 对于不等于的, 直接跳过, 所以这里只回表了 2 次.

MySQL 学习 04 - 索引

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

谈裸辞和开源的体会

剑指 Offer 04. 二维数组中的查找

宝塔 nginx 增加编译模块

通过 Github Actions 自动构建 ZFile 镜像并推送到 Docker Hub

优化 Java 项目 Docker 镜像内存占用从 500 M 到 100M

一款基于 Shiro 的权限管理系统，支持 restful 风格 URL.

页面动态添加 JS，并监听加载完毕事件

debian 11 vps 安装 pve7

设计模式 - 代理模式

修复 docker buildx 编译后，manifest 包含 unknown 的问题

MySQL 学习 04 - 索引

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

MySQL 学习 04 - 索引

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款