开始
MySQL为什么选择Innodb？
首先我们介绍一下MySQL的默认引擎为什么会使用Innodb。
- 5.1之前MySQL使用的一直都是MyISAM，MyISAM存储方式是非聚集索引，也就是说索引与行记录分开存储的。5.1之后MySQL换成了Innodb，Innodb存储方式是聚集索引，也就是索引与记录是存在一起的。通过这一点可以看出从查询效率上Innodb优于MyISAM。一定程序上节省了很多磁盘IO的消耗问题
- 随着数据库的发展对数据一致性要求越来越高，事务就出现了，MySQL选择Innodb有很大的原因则是因为事务的支持问题。而且也没有事务的日志。无法保证数据的安全性
- innodb支持行级锁，MyISAM只支持表锁，在数据量稍大的时候无法满足并发的要求。
最主要的还是随着现在的发展事务是比较重要的因素。
Innodb的底层算法又是如何抉择
哈希索引
我们先来了解一下哈希索引，哈希索引不管是存还是取的时候，都会进行一遍哈希值处理，会把key换算成一个一串计算机地址进行存储。在进行查询取值的时候也是一样的。所以查询效率是非常高的，但是不支持范围查找，所以无法满足当前数据查询的需求。但是如果查单个数值的时候利用哈希索引查找是非常优秀的。
有序数组
这个有序数组就是类似于链表一样，如果数据量过于庞大的话，查询数据要一个一个遍历之后才可以。这样的效率是非常慢的。所以不完成采用这种方式。
二叉树索引
平时我们遍历数据的时候会遍历一个链表，数组等操作。从0开始的效率是比较慢的。为了提升查询效率，采用二叉树的查询方式极大的优化的查询性能。但是的新增数据的时候会有一种极端的情况。以下就是举个一个例子，按照二叉树的特性，新增节点之前会先判断一下当前节点应该归到哪个节点上。如果新增的数据一个比一个大那么就会出现二叉树倾斜的场景。
倾斜的二叉树和链表的查询性能是一样的，这显然不是我们要的效果。于是二叉树pass
1,2,3,4,5,6,8,9
红黑树
随着二叉树的演变，最终采用了红黑树作为底层数据结构。
红黑树是一个平衡二叉树，可以完美的解决二叉树遗留下来的不足。但是也正是因为平衡这一特性，导致红黑树也同样不适合作为默认的数据结构，因为，平衡后的树过于庞大，这一对数据的存储非常的不利。因为树过高在查询数据的时候，会采用多次磁盘IO，因为一个数据页只有4K，不可能存储所有的数据。
据我们所知，磁盘IO寻址时间大概在10ms，如果数据量上了一定百万级。这样的查询速度是有点头疼的。所以为了继续优化底层数据结构。最终转移到了B树上。
B树
B树的出现，解决了红黑树(平衡二叉树)，树高的问题。他的实现方式是使叶子节点具有相同的深度，但是有出现了一个查询数据的毛病，在查询一段时间的时候往往要通过上层的节点进行反查，这样极大的降低了查询数据的效率。于是B树pass
B+树
开发人员兜兜转转最终到了B+树上，B+树是在B树上做的扩展。兼容B树的同时使 底层节点类似于链表那样一一串起来。这样最终解决了上面所有数据结构中的问题。
索引类型
主键索引
它是一种特殊的唯一索引，不允许有空值。一般是在建表的时候指定了主键，就会创建主键索引， CREATE INDEX不能用来创建主键索引，使用 ALTER TABLE来代替。
聚集索引其实就是主键索引
举例看一下
create table T( id int primary key, k int not null, name varchar(16), index (k))engine=InnoDB;
ID是一个主键所以会有一个主键树，k是一个索引字段，name是一个普通字段。
从图中不难看出，根据叶子节点的内容，索引类型分为主键索引和非主键索引。主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引。非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引。
首先我们执行以下SQL，因为这里的ID是主键，根据数据存储的结构，我们只需要查询ID这颗B+树就好了，因为这颗B+树上存储着这个数据表中ID=500的所有列名数据。如果节点中有些数据不在这颗树上的时候，就无法实现这样的效果了。必须通过回表的方式查询对应的列名数据才可以返回数据到客户端。
select * from T where ID=500 主键索引查询
我们再讲述一下这条SQL，因为这里查询的是k这个字段的值，k这个字段是普通索引，所以数据结构的存储方式是如右图的。如果用户想查出所有 T 表中的所有列名数据，就必须先查 k 树上的 k=5 的数据，得到 ID等于 500 之后，再带着 500 回到 ID 树上进行查询 R4 这个数据。这个过程就是回表，回表次数越多，耗时越慢。
select * from T where k=5 普通索引查询
综上所述，工作过程中很多人在解决数据查询慢的时候往往是通过加一个索引达到提高查询效率的原因就是这个。所以开发过程中尽量采用主键查询。
唯一索引
与普通索引类似，不同的就是：索引列的值必须唯一，但允许有空值。如果是组合索引，则列值的组合必须一样
普通索引
这是最基本的索引，它没有任何限制
全文索引
FULLTEXT索引用于全文搜索。只有InnoDB和 MyISAM存储引擎支持 FULLTEXT索引和仅适用于 CHAR， VARCHAR和 TEXT列
索引维护
工作中，通常为了提升性能，随随便便的就加了一些索引，会导致索引过多，适得其所。所以平时我们要对索引有一个维护的过程。
索引维护的常见问题是：如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。而更糟的情况是，如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。
相反，如果一条数据在删除的时候，利用率很低的时候，会有一个数据合并的过程，这个过程就是分裂过程的逆工程。
不管是页分裂还是分裂逆工程，除了性能外，整体空间的利用率降低大概50%。
覆盖索引
这个不太好说，举个例子自己体会一下吧。
我们要查询 user 这个表上的 k 在 3 - 7 的范围上的ID所有数据。这个时候 k 是一个索引，所以存在一个索引树。这个索引树上刚好存有ID的这个叶子节点的数据。所以就可以直接在这颗k索引树上查询，不需要回到主键索引树上查询，也就是回表操作。
这样就是大概的覆盖索引！
select ID from user where k between 3 and 7
核心： 覆盖索引可以完美的解决回表的操作。可以显著的提升查询性能。所以覆盖索引往往是一个性能优化比较实用的手段之一。
最左前缀索引
这里就是大家常说的最左前缀原则。那么到底是一个什么东西呢？
这个是B+树索引结构，可以利用最左前缀原则来定位记录。
这里我们举一个联合索引的例子，性能和年龄都是索引的情况，如果我们要查询姓名为张三的人，那么很快就能定位到ID4并且后面的所有数据。如果要查姓名是张开头的人，那么我们也能很快定位到ID3之后的所有数据。这个就是最左前缀原则的好处。他可以减少很多不必要的索引。
索引下推
上面我们介绍了最左前缀索引，这里的索引下推跟上文是息息相关的。索引下推这个概念是在MySQL5.6版本引入的，属于是一个查询内部的优化。
举个例子吧。我们要查询 tuser 表中哪些是姓张的人，并且年龄是20岁的人，没有被删除过的人。
select * from tuser where name like '张%' and age=20 and isdelete=1;
5.6之前的版本会通过 name 树查询姓张的。然后数据查询之后就要开始判断，当前数据是否满足后面的条件，age是否等于20以及是否处于未删除的状态。只有这样这条SQL也完成。那么判断age=20，需要进行回表。回表的操作就是拿着当前这条数据的ID号，去主键索引查询这个ID对应的age。判断满足之后这条数据也完全匹配。然后继续下一条操作。
5.6之后的版本,引入了索引下推这个概念。会优先判断当前这条记录是否满足age=20，并且是没有被删除过后的。判断结果成立之后再进行回表操作。这样减少了回表次数，优化了查询效率。
