一、前置知识
1、常见索引面试题
▪ 数据库中最常见的慢查询优化方式是什么？
▪ 为什么加索引能优化慢查询？
▪ 你知道哪些数据结构可以提高查询速度？
▪ 那这些数据结构既然都能优化查询速度，Mysql为何选择使用B+树？
2、基础知识储备
▪ 局部性原理
▪ 磁盘预读(预读的长度一般为页（page）的整数倍)
– 页是存储器的逻辑块，操作系统往往将主存和磁盘存储区分割为连续的大小
相等的块，每个存储块称为一页（在许多操作系统中，页大小通常为4k），
主存和磁盘以页为单位交换数据。
3、mysql执行流程
二、索引
1、索引是什么
▪ 索引是帮助 MySQL 高效获取数据的数据结构
▪ 索引存储在文件系统中
▪ 索引的文件存储形式与存储引擎有关
2、索引文件的结构
hash
哈希表可以完成索引的存储，每次在添加索引的时候需要计算指定列的hash值，取模运算后计算出下标，将元素插入下标位置即可
适合的场景：等值查询表中的数据是无序数据(返回查找的时候比较浪费时间，需要挨个进行遍历操作)
返回查找不合适
hash表在使用的时候，需要将全部数据加载到内存，比较耗费内存的空间，也不是很合适
树
在树的结构中，左子树必须小于双亲节点，右子树必须大于双亲节点，如果是多叉树，从左到右是有序的
树：多叉树->二叉树(二分查找)->AVL树(平衡树)->红黑树
AVL树：是一种严格意义上的平衡树，最高子树跟最低子树高度只差不能超过1，因此在进行元素插入的时候，会进行1到N此旋转，严重影响插入的性能红黑树：是基于AVL树的一个升级，损失了部分查询的性能，来提升插入的性能，在红黑树中最低子树跟最高子树之差小于2倍即可，在插入的时候不需要进行N多次的旋转操作，而且还加入了变色的特性，来满足插入和查询的性能的平衡
二叉树及其N多的变种，都不能支撑索引，要么是树的深度无法控制，要么是
B树
所有键值分布在整颗树种
搜索有可能在非叶子节点结束，在关键字全集内做一次查找，性能逼近二分查找
每个节点最多拥有m个子树
根节点至少有2个子树
分支节点至少拥有m/2颗子树（除根节点和叶子节点外都是分支节点）
所有叶子节点都在同一层，每个节点最多可以有m-1个key，并且升序排列
缺点：
1、每个节点都有key，同时也包含data，而每个页存储空间是有限的，如果data比较大的话会导致每个节点存储的key数量变小
2、当存储的数据量很大的时候会导致树的深度较大，增大查询时磁盘的IO次数，进而影响查询性能
B+树
B+树是在B树的基础之上做的一种优化，变化如下
(1)B+Tree每个节点可以包含更多的节点，这么做的原因有两个，第一个是为了降低树的高度，第二个是将数据范围变为多个区间，区间越多，数据检索越快(2)非叶子节点存储key，叶子节点存储key和数据
(3)叶子节点两两指针相互连接（符合磁盘的预读特性），顺序查询性能更高
3、索引的分类
▪ mysql索引的五种类型：主键索引、唯一索引、普通索引和全文索引、组合索引。通过给字段添加索引
可以提高数据的读取速度，提高项目的并发能力和抗压能力。
主键索引
– 主键是一种唯一性索引，但它必须指定为PRIMARY KEY，每个表只能有一个主键。
唯一索引
– 索引列的所有值都只能出现一次，即必须唯一，值可以为空，唯一索引不会回表。
普通索引
– 基本的索引类型，值可以为空，没有唯一性的限制。（覆盖索引）
全文索引,MyISAM支持，Innodb在5.6之后支持
– 全文索引的索引类型为FULLTEXT。全文索引可以在varchar、char、text类型的列上创建
组合索引
– 多列值组成一个索引，专门用于组合搜索（最左匹配原则）
4、Mysql存储引擎
不同的存储引擎，数据文件和索引文件存放的位置是不同的，因此有了分类：
聚簇索引：数据和文件放在一起：InnoDB
.frm:存放的是表结构
.ibd:存放的是数据文件和索引文件
注意：mysql的InnoDB存储引擎默认情况下会把所有的数据文件放到表空间中，不会为每一个单独的表保存一份数据文件，如果需要每一个表单独使用文件保存，设置如下属性：set global innodb_file_per_table=on;非聚簇索引：数据和文件分开放：MyISAM
.frm:存放表结构
.MYI:存放索引数据
.MYD:存放实际数据
5、mysql索引机制
6、索引难点
回表
1、InnoDB是通过B+树结构对主键创建索引，然后叶子节点种存储记录，如果没有主键，那么会选择唯一键，如果没有唯一键，那么会生成一个隐藏的6位的row_id来作为主键
2、如果创建索引的列是其他字段，那么在叶子节点中存储的是该记录的主键，然后再通过主键找到对应的记录，叫做回表
3、MyISAM:不存在回表问题，原因是MySIAM存储引擎，索引文件和数据文件是分开存放的，在B+树的叶子节点存储的是数据行所在的磁盘地址，普通索引也是如此，所以不存在回表问题
覆盖索引
1、针对InnoDB,覆盖索引是指，如果查询的时候用到的是普通索引，而查询的列正好是主键id，那么在普通索引的B+树中叶子节点存储的正好就是主键id，直接返回即可，便不需要再去主键索引的B+树中遍历
最左前缀
1、最左前缀，是指使用组合索引的时候，必须从左到右依次匹配索引列
