# mysql 索引
## 一、BTree索引
> 官方定义：索引是一种帮助mysql提高查询效率的排好序的**数据结构**。
mysql采用BTree的变种B+Tree作为索引的数据结构，下面就从BTree数据结构开始一步步的探究Mysql的索引究竟是什么东西？
### 1. BTree
Mysql采用BTree作为索引的数据结构，BTree也是一种树结构，与二叉树相比，其能有多个子节点。
> 那么Mysql为什么采用BTree作为索引的数据结构呢？而不是采用常见的红黑树或者平衡二叉树？
答案就是：在数据库表中有大量的记录的情况下，我们无法一次性的将数据库中一整表中的数据都读入内存中，只能分开多次读取磁盘，读取的次数与数据的存储结构的设计有关。BTree这种结构所具有的特性能够很好的适应这种情况，也就是BTree的高度要远远低于平衡二叉树或者红黑树，磁盘的读写IO次数更少（这在后面进行说明）；可以这么说，BTree这种数据结构是针对磁盘读写而设计的。
#### 1.1 磁盘的结构
先来看看磁盘的结构
典型的物理磁盘一般有多个盘片组成，每个盘片一般都有上下两个盘面，盘面表面覆盖有一层可磁化的物质可以用来记录数据。磁盘驱动器可以驱动磁臂来进行寻道，同时盘片可以高速旋转到磁头所在的位置，进而定位到一个要读写数据的位置。这个过程是机械化的过程，与电气过程相比非常缓慢。一次磁盘的读取时间一般可以分为：**寻道时间 + 旋转延迟 + 传输时间**。传输时间属于电气过程，与另外两个所花费的时间相比可以忽略不计。一般而言磁盘的平均读写时间为8-11ms，而主存的存取时间在50ns左右（参考《算法导论》）。因此一次磁盘的读取周期，主存都能进行十几万次的存取了，速度相比是非常大的。
基于磁盘和主存之间的速度的差异性，为了不让磁盘的读取时间严重影响到整体的性能，一个重要的改进就是减少磁盘的读取次数。BTree树就是为此而诞生的。一棵BTree的类似结构如下：
假定每个节点可以存放1000个索引，一个索引占4个字节，假设指向孩子节点的指针占6个字节（InnoDB引擎就是这么6个字节），则一个节点总共占1000 \* 4 + 1001 \* 6 ≈ 9.7kB；InnoDB的默认页大小为**16KB**，所以一次IO磁盘读写将一个节点写入（或写出）主存是完全没有问题的。对于这样一棵高度为3的BTree，能够存放的索引数量为 1000 \* 1 + 1000 \* 1001 + 1000 \* 1001 \* 1001 = 1,003,003,000，大约包含10亿个索引数量（不考虑卫星数据）。而这只用进行2次磁盘读写（根节点一般常驻内存）就能够找到一个索引的位置。如果是平衡二叉树或者红黑树10亿个节点的树的高度可能就远远不止这么大了，要进行磁盘读写的次数也会随之增加。
> 备注：
>
> 1. Mysql中的节点的指针就是为6个字节大小，猜测这应该和现在64位操作系统的48位的虚存寻址一样，没有找到对应的说明。
>
> 2. 现在操作系统的虚存页的大小一般在2K~16K大小（Linux系统的为4KB），mysql的InnoDB存储引擎给每个节点分配的索引页分配的大小为：16KB，可以通过语句
>
> show global status like 'Innodb\_page\_size';查看具体的大小。
>
说了这么多下面先来看一下BTree的定义及相关操作的时间复杂度(不会涉及到具体的实现)
#### 1.2 BTree定义
假设：
1. 节点的卫星数据与节点存放在一起，这里的卫星数据可以是真正的数据，或者是存放数据对应的地址（通过这种方式区分出了聚簇索引和非聚簇索引）。
2. BTree的节点的最大度为M。
则一棵BTree需要满足如下的性质：
* 根节点如果不是叶子节点，则至少有两个子节点。
* 每个节点最多只有M个子节点。
* 每个除根外的非叶子结点至少有⌈ M / 2⌉个子节点。
* 具有K个子节点的非叶子节点有K - 1个关键字，同时关键字按照**非递减次序排序。**
* 节点的每个关键字都分割子节点的关键字的范围，关键字左边的子树的所有关键字小于等于该关键字，右边子树的所有关键字大于该关键字。
* **所有的叶子都在同一层，是平衡的。**
**注意：对于一棵BTree进行先序遍历将会得到非递减的次序。**
#### 1.3 查找操作
跟二叉树的查找类似，BTree的查找是多路的，其时间复杂度和BTree的高度有关，对于一棵有n个节点的BTree，其高度不超过
对于一棵“满”的BTree的高度为logM(n)。因此其查找的时间复杂度为O（logM(n)），当节点的最大度M比较大的时候，树的高度是非常小的（例如上面说的h=3的树可以存放10亿个关键字）。
#### 1.4 插入操作
BTree的插入操作只会在叶子结点中进行，如果插入之后节点的关键字数量不满足BTree的要求，则会对节点进行分裂，即将该节点的关键字分为左右两部分，将中间大小的关键字提升到父节点中，分类成两个子节点；对于父节点也是做同样的操作，不满足的节点就进行回溯，直到分裂根节点。
这个过程也是和树的高度相关，其时间复杂度为O(lgn)。
#### 1.5 删除操作
如果要删除的节点是叶子节点，则直接进行删除，同时判断父节点是否满足BTree的要求，如果不满足，则做跟插入操作做类似的分裂回溯操作使其满足BTree的要求。
这个过程的时间复杂度也是为O(lgn)。
> 备注：关于BTree的插入和删除操作是怎么维护BTree的性质的可以查看《算法导论》第18章。
>
> 参考博文：[https://www.cnblogs.com/lianzhilei/p/11250589.html](https://www.cnblogs.com/lianzhilei/p/11250589.html)
### 2\. B+Tree
在Mysql中并不是直接使用上面BTree的结构，而是使用其变种B+Tree。B+Tree与BTree的主要差别在于非叶子结点不存储卫星数据，使得非叶子节点能够存储的索引数量尽可能的大，以此来压缩树的高度；**与此同时需要在叶子节点中备份存放非叶子节点的关键字及其卫星数据**，同时叶子节点之间使用双向链表进行连接，这样能够**方便进行范围查询**。两种结构的区别可如下图：
BTree结构：
:-: 
B+Tree结构：
（上面图片使用网站：[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html](https://www.cs.usfca.edu/~galles/visualization/Algorithms.html)绘制）。
注意：与上图B+Tree结构不同的是，Mysql中的叶子节点是使用**双向链表**进行连接。
mysql中不同的存储引擎的索引的具体结构还有些区别，具体区别在于卫星数据是否和索引放在一起，由此可以引出如下两个概念：
* 聚簇索引：索引和对应的行数据存储在一起。（InnoDB存储引擎使用）
* 非聚餐索引：索引和对应的行数据分开存储。（MyIsam存储引擎使用）
> 备注：下面的实验在mysql8中进行。
### 3\. 聚簇索引
也称聚集索引。Mysql8之后默认使用的就是InnoDB存储引擎，一般情况下使用的是聚簇索引，索引和行数据一起存储，也称为主键索引，InnoDB会为每张表创建一个主键索引（显示或者是隐藏的）。例如在创建Student表时使用Innodb存储引擎：
~~~
create table student(
sid int primary key auto_increment,
name varchar(64),
age int,
grade varchar(32),
sex char(2)
);
~~~
创建成功之后可以看到在本地文件夹中生成了.idb的文件
这个文件中存放了表的索引及其行记录的数据，同时也保存了表元数据，没有在另外生成一个.sdi文件。
其索引结构的直观感受如下：
【图像来源网上】
对于其他的创建的索引，即辅助索引（非聚簇索引），会在叶子节点的卫星数据中存放该行记录对应的主键值。如果SQL语句走的是辅助索引，则会先在辅助索引中找到对应行的主键，接着才去聚簇索引中寻找对应的数据（这个过程就称为回表）。例如辅助索引的高度为3，聚簇索引的高度也为3，找到一行记录需要6次的IO读写操作。因此一般而言查询优化器会偏向于使用聚簇索引进行查找（我们书写SQL语句时应该也一样）。
【图像来源网上】
💡 可以认为在InnoDB中，除了聚簇索引（也就是主键索引），其他的索引全是辅助索引，这对理解InnoDB中索引树的结构十分重要。即主键索引会和数据一起存放在叶子节点中，辅助索引的叶子节点存放辅助索引和其对应的主键。
### 4\. 非聚簇索引
也称辅助索引，非聚集索引，是MyIsam存储引擎使用的索引结构（当然InnoDB引擎非主键索引也是称为非聚簇索引），区分聚簇索引与非聚簇的关键是，非聚簇索引和对应的行数据分开存储，例如创建user表时指定MyIsam引擎：
~~~
create table user(
uid int primary key auto_increment,
name varchar(64),
age int,
sex char(2)
)engine=MYISAM;
~~~
创建成功之后可以到mysql的安装目录的**data**文件夹中找到user表所在的数据库名称对应的文件夹，可以发现生成了两个如下文件：
生成了一个以.MYD结尾和一个以.MYI结尾的文件夹，从文件名也可以看出.myd文件就是存储使用MyIsam引擎表的数据（MyIsam Data），而.myi就是存储使用MyIsam引擎表的索引（MyIsam Index）。同时可以发现在我们刚创建的时候索引文件就是有数据的了（初始化B+Tree的结构），而数据文件因为还没有插入任何数据，因此里面还没有数据，为0KB。
~~~
备注：mysql8之后再也没有生产frm文件，对于由非innodb引擎建立的表会生成一个.sdi文件来存储表结构的元数据。
~~~
MyIsam索引结构的直观感受：
【图像来源网上】
#### 4.1联合索引
多个列作为索引，例如（name,age,position)作为联合索引，在比较的时候按照定义索引时的属性顺序一个一个进行比较。联合索引遵循`最左匹配原则`。一个查询有没有走索引可以用explain工具来查看。
只有第一条会走索引，下面两条都不走索引。对于没有用name的查询条件（最左的查询条件），会进行全表的扫描，因为最左边的不同，不一定是有序的。
可以看到如果只是查询age=30的话并不能按照索引的方式来顺序查找，还是的全表扫描。
使用联合索引的好处在于可以对多个索引列按照逻辑顺序排好序，例如对于有一张表buy\_log，用来记录用户的购买日期，如下：
~~~
create table buy_log(
user_id int unsigned not null,
buy_date DATE
)ENGINE=InnoDB;
insert into buy_log values(1, '2022-01-01');
insert into buy_log values(2, '2022-01-01');
insert into buy_log values(3, '2022-01-01');
insert into buy_log values(1, '2022-02-01');
insert into buy_log values(2, '2022-02-01');
insert into buy_log values(3, '2022-02-01');
insert into buy_log values(1, '2022-03-01');
insert into buy_log values(1, '2022-04-01');
# 创建两个索引
alter table buy_log add key(user_id);
alter table buy_log add key(user_id, buy_date);
~~~
分别执行如下两条语句可以得到下面的执行的执行计划：
~~~
mysql> explain select * from buy_log where user_id = 2\G;
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: buy_log
partitions: NULL
type: ref
possible_keys: user_id,user_id_2
key: user_id_2
key_len: 4
ref: const
rows: 2
filtered: 100.00
Extra: Using index
1 row in set, 1 warning (0.00 sec)
mysql> explain select * from buy_log where user_id = 1 ORDER BY buy_date\G;
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: buy_log
partitions: NULL
type: ref
possible_keys: user_id,user_id_2
key: user_id_2
key_len: 4
ref: const
rows: 4
filtered: 100.00
Extra: Using index
1 row in set, 1 warning (0.00 sec)
~~~
PS：与《MYSQL技术内幕 InnoDB存储引擎》不同的是，这两条走的都是联合索引。
#### 4.2 覆盖索引
Covering index，或称索引覆盖。如果一个索引包含（覆盖）所需要查询的字段的值，我们就称之为“覆盖索引”。即从辅助索引中就可以得到要查询的值，而不需要去聚簇索引中在查询一遍。
对于一些执行统计的操作，执行优化器会偏向于执行覆盖索引的操作。
例如：
~~~
mysql> explain select count(*) from buy_log\G;
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: buy_log
partitions: NULL
type: index
possible_keys: NULL
key: user_id
key_len: 4
ref: NULL
rows: 8
filtered: 100.00
Extra: Using index
1 row in set, 1 warning (0.00 sec)
mysql> explain select count(*) from buy_log where buy_date >= '2022-01-01' and buy_date <= '2022-03-03'\G;
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: buy_log
partitions: NULL
type: index
possible_keys: user_id_2
key: user_id_2
key_len: 8
ref: NULL
rows: 8
filtered: 12.50
Extra: Using where; Using index
1 row in set, 1 warning (0.00 sec)
~~~
对于单单buy\_date的查询，一般都不会去走索引，但是在统计操作中，执行优化器会去走索引。
> 备注：使用explain执行器查看到的Extra字段的值为Using index就是走覆盖索引。
#### 4.3 前缀索引
对于一些内容很长的列可以使用前缀索引，即选取该列的前面几个字节作为索引，这种方式需要去判断所选择的字段的选择性怎么样。
## 二、哈希索引
### 1\. 哈希算法
InnoDB使用的哈希函数为除法散列的方式，同时使用链地址法来解决冲突。哈希表槽位m的选择一般都会选择一个比缓冲池页中的数量大的2的倍数的一个质数。例如当缓冲池为128M时，共有8192个页。对于哈希表来说就会分配接近8192 x 2=16384的一个质数。
### 2\. 哈希索引
哈希索引是基于哈希表实现的，只能用于等值查询中，不能用于范围查询中。存储引擎会通过哈希函数为表中的每行数据计算出一个哈希码，在哈希表中保存这个哈希码，同时保存指向该行数据的一个指针。
InnoDB存储引擎不支持显示的创建哈希索引，只有Memory引擎(基于内存的一个存储引擎)显示的支持哈希索引。InnoDB存储引擎在注意到某些索引值使用非常频繁的时候，就会在基于BTree索引之上创建一个哈希索引，以实现快速哈希查找。可以通过如下命令原则是否打开自适应哈希索引：
~~~
set global innodb_adaptive_hash_index = off/on;
~~~
查看自适应哈希索引是否打开：
~~~
show variables like '%ap%hash_index';
~~~
参考博文：[https://www.cnblogs.com/geaozhang/p/7252389.html](https://www.cnblogs.com/geaozhang/p/7252389.html)
### 3\. 自定义哈希索引
可以自定义一个伪哈希索引来达到哈希索引的目的，当原始要索引的列的值很长的时候就可以对该值使用CRC32()函数生成一个32位的整数值索引。这样索引占用的空间就大大减少了，每页可以放下更多的节点。
下面的例子使用触发器来自动维护哈希索引的创建：
~~~
# 创建表，id、url、url_crc，其中url_crc表示经过CRC32()函数加工后的索引值。
create table pseudohash(
id int unsigned not null auto_increment,
url varchar(255) not null,
url_crc int unsigned not null default 0,
primary key(id),key(url_crc)
);
~~~
创建插入和更新触发器；
~~~
delimiter //
create trigger pseudohash_crc_insert before insert on pseudohash for each row
begin
set new.url_crc=crc32(new.url);
end;
//
create trigger pseudohash_crc_update before update on pseudohash for each row
begin
set new.url_crc=crc32(new.url);
end;
//
delimiter ;
~~~
插入新的url
~~~
insert into pseudohash (url) values('http://www.mysql.com');
~~~
:-: 
更新url
~~~
update pseudohash set url = 'https://www.mysqlzh.com/' where id=1;
~~~
:-: 
当然查询的时候需要添加对url添加上crc32函数进行查询：
~~~
select * from pseudohash where url_crc = crc32('https://www.mysqlzh.com/');
~~~
:-: 
为了避免哈希冲突，一般都会加上对应的被哈希的列的值
~~~
select * from pseudohash where url_crc = crc32('https://www.mysqlzh.com/')
AND url='https://www.mysqlzh.com/';
~~~
## 三、全文索引
可以用于在数据库中查找文本中的关键词，常用于文章的检索、商品详情的检索等。
## 四、mysql索引的管理
1. 创建主键索引，随表建立的时候一起建立。
~~~
create table employee(
employee_ID int primary key
);
~~~
2. 创建普通索引
在创建表的时候一起创建
~~~
create table employee(
employee_ID int primary key,
empoyee_name varchar(32),
key (employee_name)
);
~~~
这种方式建立的列名和索引名字一致；
创建表之后指定索引
~~~
create index index_name on table_name(column);
~~~
3. 创建唯一索引
在建表的时候一起创建
~~~
create table employee(
employee_ID int primary key,
name varchar(32),
company_name varchar(32),
key(name),
unique(company_name)
);
~~~
创建表之后建立
~~~
create unique index index_name on table_name(column);
~~~
4. 创建联合索引
在建表的时候一起创建
~~~
create table employee(
employee_ID int primary key,
name varchar(32),
company_name varchar(32),
key(name, company_name)
);
~~~
5. 对列的一部分数据进行索引，例如一个表test中有某个列的定义如下：name varchar(1000);则对这个列的前100个字段添加索引可如下：
~~~
alter table test add key idx_name (name(100))
~~~
5. 删除索引
~~~
drop index index_name on table_name;
~~~
6. 查看表的索引
~~~
show index from table;
~~~
:-: 
## 五、Explain使用
Explain工具可以帮助查看查询执行计划的信息，一般而言Mysql最终就会根据执行计划的信息执行查询语句。可以通过Explain执行计划来判断一条查询的SQL语句究竟有没有走索引，以此来写出更好SQL语句来。
使用方式为在select之前加上explain关键字，例如
~~~sql
explain select * from user where id = 1;
~~~
explain的输出为每一个select语句输出一行。
### Explain列
1. id：select的编号，如果没有子查询或者其他连结操作，id=1。
2. select_type：对应行是简单的select还是复杂的select。可能的值为：primary，如果有复杂的子查询，则最外层标识为primary。union，标识联合的查询。
3. table：访问的表名或者表的别名。
4. type：select访问表的类型，指示mysql如何查找表中的行。最差到最优的可能的值为：
**ALL**，全表扫描。
**index**，与ALL类似，但是扫描的是索引数据，通常Extra列中会显示“Using index”。**range**，范围上的索引扫描，通常出现在带有between或者大于号的查询语句中。**ref**，使用非唯一索引时发生，主要用在等值的条件判断中，同时返回值可能有多行数据。
**equ_ref**，最多返回一条符合条件的记录。
**const**，对查询的某部分进行优化并将其转化成一个常量时会使用。
**NULL**，Mysql提前优化，执行阶段甚至不用再访问表或者索引。
5. possible_keys：可能使用哪些索引，不一定会用。
6. Key：执行时真正使用的索引。
7. key_len：索引的字节长度。
8. ref：使用的索引的列。
9. rows：估计要找到行所需要读取的行数，并不一定精确。
10. Extra：额外信息。可能的值有：
**Using index**，使用覆盖索引。
**Using where**，检索出行后再进行行过滤。
**Using filesort**，不管是内存中完成排序还是再磁盘中完成排序都会显示这个值。
## 六、索引优化
1. Cardinality值
在使用语句`show index from table\G;`中可以查看到有一列Cardinality的值
Cardinality值可以用来表示索引中不重复记录数量的估计值。该值可以用于判断一个列是否具有高选择性，即其是否应该创建索引。该列的值除于表中的行数应该尽可能的接近1。如果该值过低要考虑是否去掉该列上的索引。
使用`analyze table\G;`可以更新表中所以的Cardinality的值，但是这个过程对于大表需要时间比较就，需要在系统停止服务的时候使用。
【参考】
1. 《Mysql高性能》
2. 《Mysql技术内幕 InnoDB存储引擎》
- 第一章 Java基础
- ThreadLocal
- Java异常体系
- Java集合框架
- List接口及其实现类
- Queue接口及其实现类
- Set接口及其实现类
- Map接口及其实现类
- JDK1.8新特性
- Lambda表达式
- 常用函数式接口
- stream流
- 面试
- 第二章 Java虚拟机
- 第一节、运行时数据区
- 第二节、垃圾回收
- 第三节、类加载机制
- 第四节、类文件与字节码指令
- 第五节、语法糖
- 第六节、运行期优化
- 面试常见问题
- 第三章 并发编程
- 第一节、Java中的线程
- 第二节、Java中的锁
- 第三节、线程池
- 第四节、并发工具类
- AQS
- 第四章 网络编程
- WebSocket协议
- Netty
- Netty入门
- Netty-自定义协议
- 面试题
- IO
- 网络IO模型
- 第五章 操作系统
- IO
- 文件系统的相关概念
- Java几种文件读写方式性能对比
- Socket
- 内存管理
- 进程、线程、协程
- IO模型的演化过程
- 第六章 计算机网络
- 第七章 消息队列
- RabbitMQ
- 第八章 开发框架
- Spring
- Spring事务
- Spring MVC
- Spring Boot
- Mybatis
- Mybatis-Plus
- Shiro
- 第九章 数据库
- Mysql
- Mysql中的索引
- Mysql中的锁
- 面试常见问题
- Mysql中的日志
- InnoDB存储引擎
- 事务
- Redis
- redis的数据类型
- redis数据结构
- Redis主从复制
- 哨兵模式
- 面试题
- Spring Boot整合Lettuce+Redisson实现布隆过滤器
- 集群
- Redis网络IO模型
- 第十章 设计模式
- 设计模式-七大原则
- 设计模式-单例模式
- 设计模式-备忘录模式
- 设计模式-原型模式
- 设计模式-责任链模式
- 设计模式-过滤模式
- 设计模式-观察者模式
- 设计模式-工厂方法模式
- 设计模式-抽象工厂模式
- 设计模式-代理模式
- 第十一章 后端开发常用工具、库
- Docker
- Docker安装Mysql
- 第十二章 中间件
- ZooKeeper