MySQL索引算法原理以及常见索引的使用

企业微信服务商
腾讯云授权服务中心

MySQL索引算法原理以及常见索引的使用

发布日：2022-01-06 13:56 阅读数：

MySQL 索引原理

1、数据结构

B Tree指的是Balance Tree，也就是平衡树。平衡树是一颗查找树，并且所有叶子节点位于同一层，如下：

B+ Tree是基于B Tree和叶子节点的顺序访问指针进行实现，它具有B Tree的平衡性，并且通过顺序指针来提供查询的性能，如下图：

2、数据操作

DDL：从根节点开始进行二分查找，找到一个key的所在的指针，然后递归地在指针所指的节点进行查找。直到查找到叶子节点，然后在叶子节点上进行二分查找，找出 key 所对应的 data。

DML：增删会破坏tree的平衡性，插入删除之后，需要对tree进行一个分裂、合并、旋转等操作来维护平衡性。

MySQL 索引类型

MySQL 的索引按照存储方式分为两类：

聚集索引：也称 Clustered Index。是指关系表记录的物理顺序与索引的逻辑顺序相同。由于一张表只能按照一种物理顺序存放，一张表最多也只能存在一个聚集索引。与非聚集索引相比，聚集索引有着更快的检索速度。

MySQL 里只有 INNODB 表支持聚集索引，INNODB 表数据本身就是聚集索引，也就是常说 IOT，索引组织表。非叶子节点按照主键顺序存放，叶子节点存放主键以及对应的行记录。所以对 INNODB 表进行全表顺序扫描会非常快。

非聚集索引：也叫 Secondary Index。指的是非叶子节点按照索引的键值顺序存放，叶子节点存放索引键值以及对应的主键键值。MySQL 里除了 INNODB 表主键外，其他的都是二级索引。MYISAM，memory 等引擎的表索引都是非聚集索引。简单点说，就是索引与行数据分开存储。一张表可以有多个二级索引。

假设表中有如下数据：

select * from t1;
+-------+----------+--------+------+--------------+
| id    | username | gender | age  | phone_number |
+-------+----------+--------+------+--------------+
| 10001 | 小花     | 女     |   18 | 18501877098  |
| 10005 | 小李     | 女     |   21 | 15827654555  |
| 10006 | 小白     | 男     |   38 | 19929933000  |
| 10009 | 小何     | 男     |   35 | 19012378676  |
| 10002 | 小王     | 男     |   20 | 17760500293  |
| 10003 | 小赵     | 女     |   29 | 13581386000  |
| 10004 | 小青     | 女     |   25 | 13456712000  |
| 10007 | 小米     | 男     |   23 | 19800092354  |
| 10008 | 小徐     | 女     |   22 | 18953209331  |
+-------+----------+--------+------+--------------+

MYISAM 存储引擎介绍

主键字段索引树：

非聚集索引树：

INNODB存储引擎

主键字段索引树：

非聚集索引树：

1、B+ Tree索引

大多数MySQL存储引擎默认都是B+ Tree，因为不需要进行全表扫描，只需要对树进行搜索即可，所以查询的速度会快很多。InnoDB 的 B+Tree 索引分为主索引和辅助索引。主索引的叶子节点 data 域记录着完整的数据记录，这种索引方式被称为聚簇索引。因为无法把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。辅助索引的叶子节点的 data 域记录着主键的值，因此在使用辅助索引进行查找时，需要先查找到主键值，然后再到主索引中进行查找。

2、哈希索引

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

无法用于排序与分组；

只支持精确查找，无法用于部分查找和范围查找。

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