索引的引入

什么是索引，建立索引的目的

索引就是用来加快查找速度的数据结构，索引的作用就好比字典的目录一样，可以快速检索到你想要查询的位置。

索引的优缺点

优点：索引最大的优点是加快数据检索速度，建立唯一索引，还能够保存数据不重复。
缺点：建立索引需要一定的物理空间，对索引列进行修改操作维护代价比较大

索引的常见模型

索引的出现就是为了提高查询效率，常见的索引模型有，哈希表，有序数组和搜索树，它们有各自适合的应用场景。

哈希表

哈希表就是一种以键—值对存储的数据结构，只要输入键key，通过哈希函数就能对应到特殊的位置，也就是能找到与之对应的值value,不可避免的我们通过哈希函数计算出对应的位置有可能出现重复的位置，此时需要用一个链表将重复的位置连接起来。
比如有4个学生，它们有id,name属性，用id去哈希得到对应的位置，学生3和学生4得到同样的位置，将它们用链表连接起来，如图所示：

哈希表的缺点：哈希表结构只能查询等值查询，不适合范围查询，范围查询要一个一个查询，时间复杂度为O(N)

有序数组

有序数组是一种特殊的数组，里面的元素，按一定的顺序排列，我们这里假设由小到大排列，有序数组既适合等值查询，又适合范围查询
例如学生id,nama属性，id的属性依次增加，其有序表如图所示，因为是有序排列的查询某个学生的字段可以用二分法进行查询，其时间复杂度为O(log(N))

缺点：维护成本高，在更新和删除操作的时候代价很高，往中间插入一个位置就需要挪动后面的所有位置
适用场景：有序数组知适用于静态存储引擎，保存了之后就不修改数据的那种，比如某一年的城市人口的信息、

二叉搜索树

如图所示，二叉搜索树的特点，首先是一颗平衡二叉树，然后其左子树的值比根节点的节点小，右子树的值也比根节点的值小

如果要想查询到某个用户新的的话，比如说查询user4只需要走UserA->UserC->UserG->User3,就是树的高度，时间复杂度为O(logN)

InnoDB的索引模型

在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表，Innodb的索引都是存储在B+里面的，每一个索引对应一个B+树中。
例如，我们有一个主键列为id的表，表中有字段k,并且在k上有主键索引

create table t(
  id int primary key.
  k int not null
  name varchar(20)
  index(k)
)engine = InnoDB;

插入5组数据为R1-R5 分别为（100，1），（200，2），（300，3），（500，5），（600，6）两个树的示意图如下：

从图中可以看出，根据叶子节点的内容，索引类型分为主键索引和非主键索引，主键索引的叶子节点存储的是整行数据，非主键索引存储的值是主键，通过回表操作才能查询其他的索引的数据。
小tip:主键索引又称为聚簇索引，非主键索引又称为二级索引
思考：基于主键索引和普通索引的查询又什么区别。
查询语句select * from t where ID = 500,即主键查询操作，只需要搜索ID这颗B+树
select * from t where k = 5,即通过普通索引方式查找，因为普通索引的叶子节点存储的是主键，需要通过主键进行回表操作。
结论：在应用中如果要查询全部的数据，通过主键查询更为合适

索引的分类

• 主键索引
• 普通索引
• 单列索引
• 唯一索引
• 全文索引

  索引维护

  B+树为了维护索引有序性，那么插入数值的时候就需要做必要的维护，如果插入的那一页慢了就会造成页分裂，数据就会挪到另一半维护成本就又增加了。
  例如：基于上面B+，如果插入的值是400的话，就会出现也分裂，性能跟着就下降了。

  覆盖索引

  有一个这么一个场景，通过普通索引，查找主键的值，即找到叶子节点的索引，由于普通索引的叶子节点保存了主键值，不通过回表操作就能够直接查询到主键值这种不需要回表的索引查询就是索引覆盖；
  总结：由于索引覆盖可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化的手段。

  冗余索引

  有一个这么一个场景，市民信息有身份证号和名字，如果将这两个字段添加索引的话，由于身份证号肯定就对应固定的名字，一一对应的，根据身份证号也能查询名字，如果是要查询全部的信息，根据联合索引查询还是需要回表，倒不如用单值索引，也需要回表，联合索引占的物理空间更多，这就是冗余索引了、

  最左前缀匹配

  最左前缀原则就是最左优先，在创建多列索引时，要根据业务需求，where子句中使用最频繁的一列放在最左边。，在进行查询的时候从左往右匹配查询。

  索引下推

  索引下推就是为了减少回表次数的，在索引遍历过程中，对索引的字段做判断，直接过滤掉不满足条件的记录，减少回表的次数。

  普通索引和唯一索引应该怎么选择

  查询过程

  通过一个查询语句select id from T where k = 5.如果是普通查询，通过普通索引的话查询到第一条数据需要往后遍历查询，知道查询到索引关键字不是所查询的停止，若是唯一索引，查询到索引关键字之后就立即停止，相比普通索引性能会高一点点，但但是对于CPU来说微乎其微。。更新过程

  当更新的页在内存中

  对于唯一索引，进行插入操作时，需要把所有的数据读进内存，来判断索引是否存在了，如果不存在在进行插入，对于修改来说，直接在内存的缓冲区直接修改，对于普通索引来说，如果所在的页在内存插入和修改都直接进行，都在change buffer中进行。

  当更新的页不再内存中

  对于普通索引来说，更新的页不再内存中，就直接在change buffer中进行相应的操作，进行下一层查询的时候，就直接在change buffer中查询就可，在合适的时候merge就行了，对于唯一索引，进行插入操作需要对表中的数据进行磁盘IO进行读进内存的操作，然后更新插入，