索引有什么用？
在生活中当我们遇到不认识的字的时候，可以通过汉语字典，先通过字的部首，根据部首的笔画在《部首目录》中找到这个部首及它在《检字表》中的页码。再数清这个字余下部分的笔画，就在部首下找到相应的笔画栏，找到要查的字及它的页码。或者通过汉语拼音音节查字法（这里就不多介绍了）也可以快速地在上万个字的词典中找到对应的字。
那么在mysql数据中，也存在跟字典一样的索引，可以高效地在上万条的数据中，很快地找到你想要的数据。只不过他们的索引方式不同而已，查询的效率也不一样，那么我们就来看看mysql的一些索引，选择合适的索引，让你的查询更快。
基础·索引的常见模型
这里我先给你介绍三种常见、也比较简单的数据结构，它们分别是哈希表、有序数组和搜索树。
-
哈希表
哈希表是以（key-value）的形式存储的一种数据结构，在key不冲突的情况下找value的时间复杂度为O(1)。但是实际中数据量越大，key重复的几率就越高，这个时候重复的key，所对应的value也会形成一个链表，链表的时间复杂度就是O(n)了。但这都不算是他最大缺点。最大的不足之处就是做区间查找的时候就很慢,因为它不是有序的。所以哈希表这种结构适用于只有等值查询的场景。 -
有序数组
有序数组在等值查询和范围查询场景中的性能就都非常优秀。
拿有序的订单号举个例子：
想要找到某个xxx007的订单号所对应的信息，我们只要通过2分法（时间复杂度O(log(N))），就可以快速的找到你想要的数据。如果是[xxx007,xxx009]这个范围的数据也一样先通过2分法找到xxx007的订单，如果订单不存在那就往右遍历一个，然后直到查到第一个比xxx009大的订单号就可以退出查找，得到你想要的区间数据。
但是有序数组也有缺点。比如在新增数据的时候，这个数据大小在中间，这个时候就必须要挪动大量的记录位置。所以，有序数组索引只适用于静态存储引擎。 -
搜索树
二叉树是一个经典的数据结构。我们知道它的时间复杂度是O(log(N))。为了维持这个时间复杂度，我们需要将它整成一颗平衡二叉树，因此更新的时间复杂度也是O(log(N))。
但是如果树高为10，一次查询可能需要访问20个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要10 ms左右的寻址时间，这就很慢了。为了增加它的效率，我们可以就得让查询访问尽量少的数据块，于是可以把这个二叉树改为n叉树，n取决于数据块大小。以InnoDB的一个整数字段索引为例，这个N差不多是1200。这棵树高是4的时候，就可以存1200的3次方个值，这已经17亿了。由于根节点常驻内存所以在这么大量的数据下只需要访问3次磁盘。
这是一颗3叉树
B-Tree和B+Tree
目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构
先上图可以看到这2种树都是上面所说的n叉树，但是它们也有区别的。
- B+树的数据只存在叶子节点，而B-树的数据存在于每个节点。
- B+树给所有叶子节点增加了一个指针让他们首尾相连（没错，是不是想到了上面的有序数组，就是为了区间查询）
所以B-树找到索引key就能立马找到数据了，但是B+树是需要到跟节点下才能拿到数据，所以说同样的内存大小，或者说同样的页大小，B+树比B-树能放更多的数据。将data放到外部存储即可比如磁盘。
看到这里，我想大家就能知道了，是的，Mysql的索引采用的就是B+树的方式。
MyISAM和InnoDB
id | age | name
假如有一张User表，有上面3个字段。id为主键索引，age为辅助索引,name也为辅助索引。那么来看2种索引的实现图
可以看到MyISAM无论是根据主索引找还是辅助索引找，都能在叶子节点找到地址，然后根据地址直接找到对应磁盘的完整数据。
而InnoDB通过id找也可以。但是当InnoDB通过name这个辅助索引去找，只能找到对应的id，然后再通过id再去找到对应的记录数据。
聚集索引和非聚集索引
可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形，相应地我们称MyISAM为“非聚集”索引。所以我们要尽量地缩短主键id，防止辅助索引过大。还有就是最好采用有规律的自增id，防止id插入的时候调整B+树的节点位置。
MyISAM和InnoDB一些其他区别：
- 是否支持行级锁 : MyISAM 只有表级锁(table-level locking)，而InnoDB 支持行级锁(row-level locking)和表级锁,默认为行级锁。
- 是否支持事务和崩溃后的安全恢复：MyISAM不提供事务，所以强调的是性能，每次查询具有原子性,其执行比InnoDB类型更快。InnoDB 提供事务支持事务，外部键等高级数据库功能。具有事务(commit)、回滚(rollback)和崩溃修复能力(crash recovery capabilities)的事务安全(transaction-safe (ACID compliant))型表。
- 是否支持外键： MyISAM不支持，而InnoDB支持
- 是否支持MVCC ：仅 InnoDB 支持。应对高并发事务, MVCC比单纯的加锁更高效;MVCC只在 READ COMMITTED 和 REPEATABLE READ 两个隔离级别下工作;MVCC可以使用 乐观(optimistic)锁 和 悲观(pessimistic)锁来实现;各数据库中MVCC实现并不统一
覆盖索引
针对InnoDB的name这种2次查询才能找到完整数据的方式，我们叫做回表查询。如果是个通过辅助索引的范围查找，那么回表查的次数是不是会有点过分了呢？我们是否有解决方法呢？
select id from User where age = 18;
哈哈，因为InnoDB辅助上是能拿到主键索引的，所以这么查，我们就不需要回表了。因为有的业务场景我们可能只需要找到一个id就行了“覆盖”了我们的需求，我们称为覆盖索引。
最左前缀原则
1）select id from User where name like 'A%';这条SQL是走索引的
2）select id from User where name like '%A';这条SQL不走索引的
这个在我们建立联合索引的时候很有用：
- 当你想建（age,name）的联合索引时，还想建一个（name）索引。这时我们只要调整联合索引的顺序为（name,age）,就可以省一个（name）的索引空间下来。
- 但是当你的查询基于（name）、（age）各自查询又有（age,name）联合查询的时候怎么建索引呢。基于上面那一条规则，然后age一般比name短，所以我们可以（name,age）,(age) 这么建，是不是又能省空间了。
索引下推
id | name（有索引） | sex（无索引）
当查询一个名字为”阿“开头的，性别为男时
select * from User where name like '阿%' and sex = 1;
这样子我们可以先通过索引快速找到’阿‘开头的所有同学。在通过sex条件判断即可
在MySQL 5.6之前，只能从ID3开始一个个回表。到主键索引上找出数据行，再对比字段值。
而MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。
