我记得之前博客我也写过关于索引使用的文章，但是并不全面，这次尽量针对重点铺全面一点。
因为索引是数据引擎层的结构我们只针对最常见使用的 Innodb 使用的 B+Tree 搜索树结构进行介绍。
每一个在 InnoDB 的中的索引都对应一颗 B+Tree。举个栗子：
创建这样一个表，并且在字段 k 上创建索引
mysql> create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;
这个时候我们插入值
(100,1)、(200,2)、(300,3)、(500,5) 和 (600,6) 这个时候主键的聚簇索引对应一颗树，然后 k 索引值对应一棵树。
基于 Innodb 引擎的特性，一个表只能有一个聚簇索引，聚簇索引上面会记录所有表字段的有序的信息。普通二级索引上面只有该索引字段和主键索引字段的对应信息。（如果可以看得比较明确）。当我们使用语句
select * from xxx where k = x
的时候，我们使用了二级索引。并且由于在二级索引上面没有索引覆盖到 name 字段，所以我们需要在二级索引里面拿到 id = x 的值然后再去聚簇索引树中搜索对应的 name 记录。这个过程被称作回表。
在频繁查询大表特别是字段非常多的表的时候，回表操作是非常消耗性能的。所以当我们设计索引的时候也尽量考虑能进行索引覆盖。也就是直接能在索引列就覆盖到我们需要经常取到的数据而不用回表。我实际中就遇到了类似的栗子，查询一个 5 e 左右的表，消耗高达多余的 50% cpu 都用在回表上面。还好我使用的 TokuDB ，TokuDB 支持多聚簇索引，才解决了这个问题。
索引维护
B+Tree 为了维护索引的有序性需要保持一定的规则和平衡。所以当我们在插入数据的时候就会需要考虑到这些问题。当我们插入一个新的 id 值为 700 ，我们需要在 r5 后面增加一个新的记录。如果插入 id 为 400 就麻烦一点，需要将r4后面的数据向后挪动空出位置。更糟糕的事情是如果 r5 所在的数据页正好满了，我们需要申请一个新的数据页并且挪动一些数据过去，这个过程性能会受到影响。这个过程被称作页分裂，而当我们进行多次分裂之后数据页利用率会变得很低，这是还会触发页的合并。
经常写业务的我们会注意到，目前很多公司的 DBA 都会建议我们使用自增 id 作为表的主键。
自增 id 作为主键有非常多的好处。比如数据拷贝，数据复制等带来的优越性。更重要的是主键递增插入，正好可以让我们避免之前说的挪动数据的情况，让我们的数据一直是以追加的形式增加进数据库的。如果以业务字段做主键，往往很难保证是一直追加。另外不要忘记，我们的二级索引上面存储的是索引列和主键列，如果主键列越小，当然性能就会越高。
使用二级索引查询执行过程
select * from T where k between 3 and 5
1. 在 k 索引树上找到 k=3 的记录，取得 ID = 300；
2. 再到 ID 索引树查到 ID=300 对应的 R3；
3. 在 k 索引树取下一个值 k=5，取得 ID=500；
4. 再回到 ID 索引树查到 ID=500 对应的 R4；
5. 在 k 索引树取下一个值 k=6，不满足条件，循环结束。
在这个过程中，回到主键索引那边去查询值的行为我们叫做回表。如果要不回表操作，就需要像我们上面说到的那样进行索引覆盖。如果二级索引上进行了索引覆盖，对应的查询就理所当然不需要回表了。
索引匹配列前缀
B+Tree 可以使用这一原则来进行索引搜寻
这是我们创建的一个二级索引
如果我们查找 like '张%' 的需求的时候，我们会搜到 id3 张六然后继续往后进行搜索直到条件不满足为止。
索引下推
而 MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。
例如执行：
mysql> select * from tuser where name like '张 %' and age=10 and ismale=1;
我们有索引 (`name`,`age`) 的索引的情况下，会进行如下优化。
Reference:
本读书笔记皆来自发布在极客时间的 林晓斌（丁奇）的 MySQL 实战45讲：
极客时间版权所有: https://time.geekbang.org/ 版权所有:
https://time.geekbang.org/column/article/69236
https://time.geekbang.org/column/article/69636
https://segmentfault.com/a/1190000008545713 MySQL 中 InnoDB 引擎中页的概念
https://blog.51cto.com/thuhak/1261783 关于 Btree
http://wiki.jikexueyuan.com/project/python-actual-combat/tutorial-11.html 关于 B+tree (附 python 模拟代码)