B+树

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

InnoDB数据页和索引结构

数据页

索引结构

索引数据结构

索引是帮助MySQL高效获取数据的排好序的数据结构

索引数据结构是B+树，下面这些数据结构有一定的缺点

二叉树

层数太高，若递增或递减添加，会形成类链表的数据结构，效率较低
红黑树
Hash表

不利于范围查找
B-Tree

不利于范围查找
B+Tree
- 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点用指针连接，提高区间访问的性能

MyISAM存储引擎

索引文件和数据文件是分离的(非聚集)

*.frm：描述表结构的文件

*.MYI：索引信息文件(索引树)

*.MYD：数据信息文件

InnoDB存储引擎

表数据文件本身就是按B+Tree组织的一个索引结构文件
聚集索引----叶节点包含了完整的数据记录

*.frm：描述表结构的文件

*.ibd：索引树，同时叶节点包含数据全部信息

为什么InnoDB表必须有主键？

表数据文件本身就是按B+Tree组织的一个索引结构文件。若没有显式声明主键，则其内部会生成一个row_id主键索引。

为什么推荐使用整型的自增主键？

整型方便比较大小，节省空间。

自增插入，对原有的树结构影响不大。

为什么非主键索引结构叶子节点存储的是主键值？

1. 保持一致性
当数据库表进行DML操作时，同一行记录的页地址会发生改变，因非主键索引保存的是主键的值，无需进行更改。

2. 节省存储空间

索引增删语句

创建索引

# 建表时创建
CREATE TABLE user (
	user_id INT AUTO_INCREMENT COMMENT '用户id',
	name VARCHAR(30) COMMENT '用户名',
	email VARCHAR(50) COMMENT '邮箱',
	birthday DATETIME COMMENT '生日',
	
    PRIMARY KEY (user_id),  # 主键索引
	UNIQUE INDEX index_name (name), # 唯一索引
	INDEX index_3 (name, email, birthday)  # 普通索引、组合索引
) ENGINE = INNODB DEFAULT CHARSET = utf8;

# 建表后创建
ALTER TABLE user ADD UNIQUE INDEX index1(name); # 唯一索引
ALTER TABLE user ADD INDEX (name, email, birthday)  # 普通索引、组合索引

查看索引

show index from 表名;

删除索引

# 删除index1索引
ALTER TABLE user drop INDEX index1;

索引分类

逻辑区分

根据索引的具体用途，MySQL 中的索引在逻辑上分为以下 5 类：

1) 普通索引

普通索引是 MySQL 中最基本的索引类型，它没有任何限制，唯一任务就是加快系统对数据的访问速度。

普通索引允许在定义索引的列中插入重复值和空值。

ALTER TABLE user ADD INDEX index1(id);

2) 唯一索引

唯一索引与普通索引类似，不同的是创建唯一性索引的目的不是为了提高访问速度，而是为了避免数据出现重复。

唯一索引列的值必须唯一，允许有空值。如果是组合索引，则列值的组合必须唯一。

ALTER TABLE user ADD UNIQUE INDEX index1(id);

3) 主键索引

主键索引就是专门为主键字段创建的索引，也属于索引的一种。

主键索引是一种特殊的唯一索引，不允许值重复或者值为空。

创建主键索引通常使用 PRIMARY KEY 关键字。

4) 空间索引(了解)

空间索引是对空间数据类型的字段建立的索引，使用 SPATIAL 关键字进行扩展。

创建空间索引的列必须将其声明为 NOT NULL，空间索引只能在存储引擎为 MyISAM 的表中创建。

空间索引主要用于地理空间数据类型 GEOMETRY。这类索引很少会用到。

5) 全文索引(了解)

全文索引主要用来查找文本中的关键字，只能在 CHAR、VARCHAR 或 TEXT 类型的列上创建。

全文索引允许在索引列中插入重复值和空值。

不过对于大容量的数据表，生成全文索引非常消耗时间和硬盘空间。

创建全文索引使用 FULLTEXT 关键字。

实际使用区分

索引在逻辑上分为以上 5 类，但在实际使用中，索引通常被创建成单列索引和组合索引。

1）单列索引

单列索引就是索引只包含原表的一个列。在表中的单个字段上创建索引，单列索引只根据该字段进行索引。

单列索引可以是普通索引，也可以是唯一性索引，还可以是全文索引。只要保证该索引只对应一个字段即可。

ALTER TABLE user ADD UNIQUE INDEX index1(name);

# 只根据前四个字符建立索引
ALTER TABLE user ADD UNIQUE INDEX index1(name(3));

2）多列索引

组合索引也称为复合索引或多列索引。相对于单列索引来说，组合索引是将原表的多个列共同组成一个索引。多列索引是在表的多个字段上创建一个索引。该索引指向创建时对应的多个字段，可以通过这几个字段进行查询。但是，只有查询条件中使用了这些字段中第一个字段时，索引才会被使用。

# 在student表中的 name 和 address 字段上建立名为 index1 的索引
ALTER TABLE user ADD UNIQUE INDEX index1(name,address);

是否是主键索引

仅限InnoDB

1）主键索引

2）二级索引

InnoDB存储引擎，需要回表

一条SQL的执行过程

连接器
一条SQL语句从客户端传过来首先会创建一个连接，用username和password认证身份
连接完成后如果没有其他操作便处于空闲状态默认8h自动断开空闲连接
连接还分为长连接和短连接
长连接：持续使用同一个连接处理请求
短连接：一个连接仅执行几次后便断开，然后重新建立连接
因为创建连接的过程比较复杂，所以建议尽量使用长连接

查询缓存
建立连接后先去查询缓存
但是大家基本不用mysql的缓存功能
因为只要有对该表数据更新，表上的所有缓存都会清空然后重新创建缓存
所以一般默认不查缓存
PS.MySQL8.0直接将查询缓存功能删掉了

分析器
经过缓存器后来到分析器
先做词法分析分析出sql语句中的关键字
然后做语法分析判断是否有语法错误

优化器
经过分析后MySQL知道你要做什么了，但是在实际执行之前还得经过优化器优化一下
在表中有多个索引的时候，由优化器来决定使用哪个索引
或者有多表关联（join）的时候决定连接顺序，选择效率高的方案

执行器
执行器开始执行之前会验证是否有读/写权限，没有则返回权限错误
有的话就打开表调用指定的存储引擎接口获取执行结果集，返回给客户端

索引实践

1. 全值匹配

全值匹配指的是和索引中的所有列进行匹配

2. 最左前缀法则

如果索引了多列, 要遵守最左前缀法则。指的是查询从索引的最左前列开始并且不跳过索引中的列。

name  birthday email
SELECT * FROM user WHERE name= 'LiLei' AND birthday = '2018-09-30 00:00:00';

SELECT * FROM user WHERE name= 'LiLei' AND email = '123@qq.com' AND birthday = '2018-09-30 00:00:00';

3. 不在索引列上做任何转换、函数操作

不在索引列上做任何转换、函数操作，会导致索引失效而转向全表扫描

SELECT * FROM user WHERE left(name,3) = 'LiLei';
SELECT * FROM user WHERE name = 'LiLei';

select * from user where date(birthday) ='2018-09-30';
select * from user where birthday >='2018-09-30 00:00:00' and birthday <='2018-09-30 23:59:59';

4. 存储引擎不能使用索引中范围条件右边的列

# index(name, age, email)
# age > 22为范围条件，其后的email不能使用索引
SELECT * FROM user WHERE name= 'LiLei' AND age > 22 AND email = '123@qq.com';
SELECT * FROM user WHERE name= 'LiLei' AND age = 22 AND email = '123@qq.com';

5. 尽量使用覆盖索引

尽量使用覆盖索引（只访问索引的查询（索引列包含查询列）），减少select *语句

6. 不等于（!=或者<>）索引失效

7. is null, is not null 索引失效

8. like以通配符开头('%abc...')索引失效

9. 字符串不加单引号索引失效

SELECT * FROM user WHERE name = '1000';
SELECT * FROM user WHERE name = 1000; #不加单引号，会转换数字为字符串，索引失效

10. 少用or或in

少用or或in，用它查询时，mysql不一定使用索引，mysql内部优化器会根据检索比例、表大小等多个因素整体评估是否使用索引，详见范围查询优化

11. 范围查询优化

# 没走索引原因：mysql内部优化器会根据检索比例、表大小等多个因素整体评估是否使用索引。比如这个例子，可能是由于单次数据量查询过大导致优化器最终选择不走索引
select * from user where age >=1 and age <=2000;

# 优化方法：可以讲大的范围拆分成多个小范围
select * from user where age >=1 and age <=1000;
select * from user where age >=1001 and age <=2000;

Explain详解

每个表会输出一行，如果有两个表通过 join 连接查询，那么会输出两行

Explain两个变种

explain extended：会在 explain 的基础上额外提供一些查询优化的信息。紧随其后通过 show warnings 命令可以得到优化后的查询语句，从而看出优化器优化了什么。
explain partitions：相比 explain 多了个 partitions 字段，如果查询是基于分区表的话，会显示查询将访问的分区。

Explain中的列

id列

id列的编号是 select 的序列号，有几个select 就有几个id，并且id的顺序是按 select 出现的顺序增长的。

id列越大执行优先级越高，id相同则从上往下执行，id为NULL最后执行。

select_type列

select_type 表示对应行是简单还是复杂的查询。

simple：简单查询。查询不包含子查询和union
primary：复杂查询中最外层的 select
subquery：包含在 select 中的子查询（不在 from 子句中）
derived：包含在 from 子句中的子查询。MySQL会将结果存放在一个临时表中，也称为派生表
union：在 union 中的第二个和随后的 select

table列

这一列表示 explain 的一行正在访问哪个表。当 from 子句中有子查询时，table列是格式，表示当前查询依赖 id=N 的查询，于是先执行 id=N 的查询。当有 union 时，UNION RESULT 的 table 列的值为，1和2表示参与 union 的 select 行id。

type列

表示关联类型或访问类型，即MySQL决定如何查找表中的行，查找数据行记录的大概范围。

依次从最优到最差分别为：system > const > eq_ref > ref > range > index > ALL

一般来说，需要保证查询达到range级别，最好达到ref

NULL：mysql能够在优化阶段分解查询语句，在执行阶段用不着再访问表或索引。例如：在索引列中选取最小值，可以单独查找索引来完成，不需要在执行时访问表

const, system：mysql能对查询的某部分进行优化并将其转化成一个常量（可以看show warnings 的结果）。用于 primary key 或 unique key 的所有列与常数比较时，所以表最多有一个匹配行，读取1次，速度比较快。system是const的特例，表里只有一条元组匹配时为 system

eq_ref：primary key 或 unique key 索引的所有部分被连接使用，最多只会返回一条符合条件的记录。这可能是在 const 之外最好的联接类型了，简单的 select 查询不会出现这种 type

ref：相比 eq_ref，不使用唯一索引，而是使用普通索引或者唯一性索引的部分前缀，索引要和某个值相比较，可能会找到多个符合条件的行。

index：扫描全表索引,不获取索引的数据，这通常比ALL快一些。

ALL：即全表扫描，意味着mysql需要从头到尾去查找所需要的行。通常情况下这需要增加索引来进行优化了

key列

这一列显示mysql实际采用哪个索引来优化对该表的访问。如果没有使用索引，则该列是 NULL。

key_len列

这一列显示了mysql在索引里使用的字节数，通过这个值可以算出具体使用了索引中的哪些列。

举例来说，film_actor的联合索引 idx_film_actor_id 由 film_id 和 actor_id 两个int列组成，并且每个int是4字节。通过结果中的key_len=4可推断出查询使用了第一个列：film_id列来执行索引查找。

rows列

mysql估计要读取并检测的行数

Extra列

这一列展示的是额外信息。常见的重要值如下：

using index: 索引覆盖。什么是索引覆盖呢？就是，查询的列都在索引里面可以找到，这样就不用去数据库里面查找了。性能全表扫描高。如果这里用到了where条件，那么条件必须是索引的前缀列。
using where: 查询的列没有被索引覆盖，并且where 的条件非索引的前缀列。没有从索引里面查数据
using where，using index：查询的列被索引覆盖，且where条件非索引前缀列。从索引取数据，但是没有从索引里面查数据
null ：查询的列没有被索引覆盖，但是where条件是索引前缀列。没有从索引取数据，但是从索引查数据
using index condition: 未被索引覆盖，where条件是前缀列，但是是前缀列的范围查询。就是说前缀列使用了大于小于等符号。
using temporary：使用了临时表来处理数据。这里讲一下临时表和衍生查询，衍生查询侧重的是查询，查询的表来自于select产出的表，不是直接查找数据库的表。临时表是经过处理的表，比如group by，distinct 等。
using filesort: 文件排序。这里说明没有走索引排序

Select tables optimized away：使用某些聚合函数（比如 max、min）来访问存在索引的某个字段

nice

MySQL索引简析

B+树