mysql的索引呢？你又知道多少？

在Java面试中必问mysql，问mysql的时候索引也是必问，可见索引有多么重要。简单的说索引是一种为了提高数据检索效率的一种数据结构。

索引的常⻅模型

索引的出现是为了实现数据检索的高效，只所以引入索引的概念是为因为能实现数据高效索引的数据结构很多，我们先看一下常见的三种数据结构哈希表、有序数组和搜索树。

哈希表是一种key-value键值对，输入key就可以找到value的值。实现一个哈希表很简单，把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。不可避免地，多个key值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。假设你现在在维护一个订单信息和订单号sn的表，需要根据订单号sn查找订单信息。此时对应的哈希索引如下图：

订单m和订单n算出来的都是m，但是没关系，后面跟的是一个链表，如果要查询order_m首先计算order_sn算出为m时间复杂度为O(1)再遍历后面的链表时间复杂度为O(n),这种情况对于取区间的值就比较慢了，必须一个一个的遍历。所以哈希表只适合等值查询的场景。

有序数组在等值查询和范围查询场景中的性能就都非常优秀，但是有序数组索引只适用于静态存储引擎，因为维持有序的成本非常高，每次插入和删除都需要维持有序，下标需要移动。如果仅仅看查询效率，有序数组就是最好的数据结构了。在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。
跳表 skiplist，我们知道链表在每次查找的时候都需要遍历一次表，我们能不能改造一下链表提高检索的效率，可以使用索引的思想对链表进行改造，将部分关键提取出来当做关键节点，如果检索效率还是太低，再将关键节点的数据取出来当关键节点的关键节点。
二叉搜索树，如果我们有个用户表用二叉搜索树实现的话如下图:

二叉搜索树的特点是:每个节点的左儿子小于父节点，父节点又小于右儿子。这样如果你要查ID_card_n2的话，按照图中的搜索顺序就是按照UserA -> UserC -> UserF -> User2这个路径得到。这个时间复杂度是O(log(N))。

用一张动图来表示搜索过程假设在这个树中搜索20流程如下:

当然为了维持O(log(N))的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是O(log(N))。所谓维持平衡就是要避免出现类似于链表的树，要让数据分布在树的两侧。树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。你可以想象一下一棵100万节点的平衡二叉树，树高20。一次查询可能需要访问20个数据块。*为什么树高是1就要io一次？因为每一次io只能取出一个节点的数据对于二叉树也就是2个，只取两个因为要根据取出来的数据的指针去获取后面的数据，除非后面节点的数据刚好和硬盘中取出的数据相邻。*为了减少io成本就应该把树高降低，所以数据库使用了N插树。在一次io中查出来一个节点的数据包含N个指针，从而降低io次数。

InnoDB 的索引模型

InnoDB使用了B+树索引模型，B+树是在搜索树的基础上改进的。为了方便理解我们就把模型简化为二叉树，树中的节点并不存储数据本身，而是只是作为索引。除此之外，我们把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。经过改造之后的二叉树，就像图中这样，看起来有点像跳表。

改造之后，如果我们要求某个区间的数据。我们只需要拿区间的起始值，在树中进行查找，当查找到某个叶子节点之后，我们再顺着链表往后遍历，直到链表中的结点数据值大于区间的终止值为止。所有遍历到的数据，就是符合区间值的所有数据。但是如果在千万上亿级别的数据中构建索引，如果索引都放入内存中尽管检索非常好但是也是非常耗费内存的一件事，所以不能不索引全部放内存中，放硬盘就涉及到了io性能的问题，前面我们提到了降低树高，将二叉变为M叉，这个M的数值放多少合适？不管是内存中的数据，还是磁盘中的数据，操作系统都是按页(一页大小通常是4KB，这个值可以通过getconfig PAGE_SIZE命令查看)来读取的，一次会读一页的数据。如果要读取的数据量超过一页的大小，就会触发多次IO操作。所以，我们在选择m大小的时候，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘IO操作。对于一个B+树来说，m值是根据页的大小事先计算好的，也就是说，每个节点最多只能有m个子节点。在往数据库中写入数据的过程中，这样就有可能使索引中某些节点的子节点个数超过m，这个节点的大小超过了一个页的大小，读取这样一个节点，就会导致多次磁盘IO操作。当出现超过m的情况我们就进行列表操作，裂变之后父节点也会超过m，同样的操作我们将父节点也进行一遍。这种级联反应会从下往上，一直影响到根节点。我们用一个动图(图中的m为3)来表示:

B+树的特点：

每个节点中子节点的个数不能超过m，也不能小于m/2;
根节点的子节点个数可以不超过m/2，这是一个例外;
m叉树只存储索引，并不真正存储数据，这个有点儿类似跳表; 通过链表将叶子节点串联在一起，这样可以方便按区间查找;
一般情况，根节点会被存储在内存中，其他节点存储在磁盘中。

“N叉树”的N值在MySQL中是可以被人工调整的么?

5.6以后可以通过page大小来间接控制。

最左前缀原则

B+树这种索引结构，可以利用索引的**“最左前缀”，来定位记录。假设我们有张表里面用name、age建立了联合索引，索引示意图为

当你的逻辑需求是查到所有名字是“张三”的人时，可以快速定位到ID4，然后向后遍历得到所有需要的结果。如果你要查的是所有名字第一个字是“张”的人，你的SQL语句的条件是"where name like ‘张%’"。这时，你也能够用上这个索引，查找到第一个符合条件的记录是ID3，然后向后遍历，直到不满足条件为止。可以看到，不只是索引的全部定义，只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左N个字段，也可以是字符串索引的最左M个字符，在建立联合索引的时候，如何安排索引内的字段顺序。如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

索引下推

以市⺠表的联合索引(name, age)为例，如果现在有一个需求:检索出表中“名字第一个字是张，而且年龄是10岁的所有男孩”。那么，SQL语句是这么写的:

select * from tuser where name like '张%' and age=10 and ismale=1;

在MySQL 5.6之前，只能从ID3开始一个个回表。到主键索引上找出数据行，再对比字段值。而MySQL 5.6 引入的索引下推优化(index condition pushdown)，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。没有索引下推的情况为：

5.6以后有索引下推的情况

问题：

CREATE TABLE `test` ( `a` int(11) NOT NULL, `b` int(11) NOT NULL, `c` int(11) NOT NULL, `d` int(11) NOT NULL, PRIMARY KEY (`a`,`b`), KEY `c` (`c`),
KEY `ca` (`c`,`a`),
KEY `cb` (`c`,`b`) ) ENGINE=InnoDB;

既然主键包含了a、b这两个字段，那意味着单独在字段c上创建一个索引，就已经包含了三个字段了呀，为什么要创建“ca”“cb”这两个索引?

如果c列上重复率很低的情况下,两个索引都可以不用建。因为如果过滤只剩下几条数据,排序也不影响,如果C列重复度比较高,就需要建立(c,b)的联合索引了,来消除排序了。因为在数据量大的情况下,排序是一个非常耗时的操作,很有可能还需要磁盘临时表来做排序。而且如果没有(c,b)联合索引,limit 1仅仅表示返回给客户端一条数据,没有起到限制扫描行,数的作用ca列上的索引,由于满足最左前缀,不用加。因为c是固定值,那么a列就是有序的.那么这里limit 1就很好限制了只用精准扫描一条数据.所以有时候如果在where条件建立索引的效率差的情况下,在order by limit这一列建索引也是很好的方案,排好序,在回表,只要过滤出满足条件的limit行,就能及时停止扫描

总结:

覆盖索引:如果查询条件使用的是普通索引(或是联合索引的最左原则字段)，查询结果是联合索引的字段或是主键，不用回表操作，直接返回结果，减少IO磁盘读写读取正行数据
最左前缀:联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符
联合索引:根据创建联合索引的顺序，以最左原则进行where检索，比如(age，name)以age=1 或 age= 1 and name=‘张三’可以使用索引，单以name=‘张三’ 不会使用索引，考虑到存储空间的问题，还请根据业务需求，将查找频繁的数据进行靠左创建索引。
索引下推:like 'hello%’and age >10 检索，MySQL5.6版本之前，会对匹配的数据进行回表查询。5.6版本后，会先过滤掉a ge<10的数据，再进行回表查询，减少回表率，提升检索速度