1、索引初探

索引的出现，其实就是为了提升查询效率，就像书的目录一样。
索引就是一种数据结构。

索引的实现方式

索引的实现方式有很多种，最常见的也比较简单的有三种，它们分别是哈希表，有序数组和搜索树。
（1）哈希表
哈希表的索引模型参见HashMap的实现方式，比较简单就不再赘述。
由于引入了数组和链表，所以适用于等值查询的场景，不十分适用范围查询
（2）有序数组
深入浅出索引 - 图1
假设我们存储的身份证号没有重复，且是按照递增的顺序保存的。这时候如果要查2的名字，用二分法就可以快速查到，时间复杂度为O(Log(N)).
那么范围查询呢？如果要查x到y区间的user，可以先用二分法查到x然后向右遍历直到查到第一个大于y的数据，退出循环。
如果仅看查询效率的话，有序数组是最好的数据结构了，但是我们的数据库并不是一个固定的数据文件，当我们插入或者删除数据 时候就比较麻烦了，就必须挪动后面所有的记录，成本太高。
所以，有序数组只适用于静态存储引擎。

（3）二叉搜索树
至于二叉搜索树，是很经典的数据结构了。如果上边的数据用二叉树实现的话，则是下图的样子：
深入浅出索引 - 图2
这种二叉搜索树的特点是：父节点左子树所有节点的值小于父节点的值，右子树所有节点的值大于父节点的值。这样如果要查2的话，按照图中的搜索顺序就是按照 A-C-F-2这个顺序得到，这个时间复杂度为O(Log(N))。当然，为了维持查询复杂度，这棵树需要时平衡二叉树。
但是我们的数据量是巨大的，如果组织成二叉树的话，树高会很大，我们写道硬盘上，一次访问可能需要方位很多个数据块，这是很耗时的。所以我们应该是用N叉树。**以InnoDB的一个整数字段索引为例，这个N大概是1200。当这棵树树高为4的时候，就可以存储1200的3次方个值，17亿数据。

InnoDB的索引模型

在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式被称为索引组织表。
每一个索引在InnoDB中对应一棵B+树。
假设我们有个主键为id的表，表中有字段k，并且k上有索引，如下图：

深入浅出索引 - 图3其中R1代表Row1，即整行数据。

我们可以看出，索引类型分为主键索引（聚簇索引）和非主键索引（二级索引）。主键索引的叶子节点存储的是整行数据，而非主键索引存储的是主键。当我们按照非主键索引查询的时候，拿到主键还要按主键再查询一次，这个过程叫做回表。
举个栗子：
如果语句 select from T where id = 500,即直接用主键查，则只需要搜索Id这棵树就可以了，可以直接得到整行数据
如果语句 select from T where k = 5；即按普通索引查询，则需要先搜索k这棵树，得到id为500，再拿着id去id索引查询一次得到整行数据。
所以我们在查询过程中尽量使用主键索引。

InnoDB的索引维护

B+树为了维护有序性，在插入新值的时候需要做必要的维护。
还是拿上边的数据为例，如果要插入新的数据行id是700，则只需要在R5后插入一个新纪录；如果要插入的是400，那就麻烦了，需要逻辑上挪动后面的数据，腾出位置。更糟糕的是如果R5所在的数据页满了，这时候就需要申请一个新的数据页，然后挪动部分数据过去，这叫做页分裂，性能自然也大受影响。除了性能之外，页分裂还影响数据页的利用率，原本放在一个页的数据，现在分到两页，整体利用率降低了约50%。所以，我们一般要求主键是递增的，就是为了防止页分裂。
有分裂就有合并，当相邻的两个页由于删除了数据，利用率很低的时候，会将数据页做合并，同样效率很低，所以很多时候，我们删除数据，并不是直接物理删除，而是逻辑删除。
**

2、MySQL的索引

例1：在表T中，如果我们执行 select * from T where k between 3 and 5;需要执行几次树的搜索操作呢，会扫描多少行呢？
表结构如下：

  2. mysql> create table T (
  3. ID int primary key,
  4. k int NOT NULL DEFAULT 0, 
  5. s varchar(16) NOT NULL DEFAULT '',
  6. index k(k))
  7. engine=InnoDB;
  9. insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

索引组织如下图：
深入浅出索引 - 图4
来看一下这条语句的执行过程：
a、在k的索引树上找到k=3的记录，得到id为300
b、再到id索引树查到id为300的记录对应的R3
c、在k树上查到k=5的记录得到id为500
d、再回到id树上得到记录R4
e、在k树上取下一个值k=6，不满足条件，查询结束

可以看到，这个过程读了k树3次，回表了两次。
那应该如何去优化搜索次数呢？

覆盖索引

如果我们执行的语句是 select ID from T where k between 3 and 5；这时候查询结果是id的值，而id的值是已经在k索引树上的，所以可以直接提供查询结果，就不需要回表。在这个查询里边，k索引树已经覆盖了我们的查询需求，我们称之为覆盖索引。
由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的优化手段。（虽然在引擎内部扫描了三条数据，分别是3,5,6其中3和5为符合条件的数据，6不符合，但是对于MySQL的server来说，他就是找引擎拿到了两条记录，所以认为扫描行数为2）
我们可以举一个实战例子来说明覆盖索引的作用。
假设我们现在有一张市民表，有字段 id，name，身份证号等信息，详细建表语句如下：

  2. CREATE TABLE `tuser` (
  3.   `id` int(11) NOT NULL,
  4.   `id_card` varchar(32) DEFAULT NULL,
  5.   `name` varchar(32) DEFAULT NULL,
  6.   `age` int(11) DEFAULT NULL,
  7.   `ismale` tinyint(1) DEFAULT NULL,
  8.   PRIMARY KEY (`id`),
  9.   KEY `id_card` (`id_card`),
  10.   KEY `name_age` (`name`,`age`)
  11. ) ENGINE=InnoDB

当其中一个需求为：需要按身份证号查询名字 时，我们该如何设计索引来为此种查询提供更好的查询性能呢？
按照正常的索引来说，给身份证号设计索引，或者给name设计索引，但是这样设计索引，每次查询都要经历一次回表，浪费了一倍的性能（夸张，不过两次对一次，也算）。这时我们就可以使用覆盖索引，将身份证号和名字设计成联合索引，它可以在这个高频请求上使用到覆盖索引，从而避免回表查询整行数据，减少语句的执行时间。

最左前缀原则

看完上述的覆盖索引，那我们扩展一下，如果还有按身份证号查询年龄或者住址的需求呢？总不能再创建一个覆盖索引吧，是不是太浪费了？没错，当此类需求较多时，我们可以使用B+树这种索引结构的特点，即：可以利用索引的左前缀，来定位记录。
举个栗子：
深入浅出索引 - 图5
如上图我们创建了(name,age)的联合索引，当我们那张三去查询时，能够匹配到ID4，然后向后遍历得到结果
如果你要查的所有名字第一个字为“张”的时候，即 like ‘%张’,也能用到这个索引。
可以得知，不只是索引的全部定义，只要满足最左前缀，就可以利用这个索引来加速检索，这个规则可以是联合索引的最左n个字段，也可以是字符串索引的最左n个字符。
那么如何安排联合索引的前后顺序就是个技术活儿了。（自己想吧）
针对联合索引来说，如果想直接按name查询，可以走到索引，但如果想直接按照age查询，那不行，因为不满足左前缀了，无法走索引加速检索。

索引下推

如果是这样的查询语句：select from tuser where name like ‘%张’ and age = 10 ;
按照索引前缀规则，这个sql的查询用到索引“张”，用到索引“张”然后呢，需要判断其他条件是否满足，也就是age是否为10.（如果你在疑问为什么没用到索引age，请继续看）
在MySQL5.6之前，只能从ID3一个一个回表，找出数据行，再做条件判断；在5.6之后，MySQL推出了*索引下推，可以在索引遍历过程中，对联合索引中未使用到的字段（如果条件有它）先做判断，直接过滤掉不满足条件的记录，从而减少回表次数（在我理解看来，其实就是两个索引都用到了而已，两个字段都在联合索引里判断，5.6之前机制不合理。）。
以下两张图是5.6以前和5.6及以后的执行图，虚线代表回表：
深入浅出索引 - 图6
深入浅出索引 - 图7

极客时间学习总结，原课程点击此处