索引模型

在InnoDB中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表被称为索引组织表。InnoDB 使用了B+树的索引模型，所以数据都是存储在B+树中。

每一个索引在 InnoDB 里面对应一棵 B+ 树。

建表语句如下： mysql> create table T(id int primary key, k int not null, name varchar(16),index (k))engine=InnoDB;

表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下。

从图中不难看出，根据叶子节点的内容，索引类型分为主键索引和非主键索引。

因此，如果直接查询主键，例如 select * from T where id = 300，则只需要搜索ID这棵B+树。

而如果是select * from T where k = 5，则需要先搜索k索引树得到id值后，再去搜索ID索引树，这个过程叫做回表。

索引维护

B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。

以上面这个图为例，

如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。而如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能会受影响。

除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%。

当索引占用空间过大时，可以通过alter table T engine=InnoDB来进行索引重建，从而压缩空间。

一个例子：

线上的一个表, 记录日志用的, 会定期删除过早之前的数据. 最后这个表实际内容的大小才10G, 而他的索引却有30G. 在阿里云控制面板上看,就是占了40G空间.InnoDB 这种引擎虽然删除了表的部分记录,但是它的索引还在, 并未释放. 只能是重新建表才能重建索引.

这种情况即可使用alter table T engine=InnoDB来进行索引重建。

覆盖索引是指，例如 select id from T where k = 3这种形式，因为id值已经被k索引树所记录，不需要回表查询。否则如果有字段没有在本索引树内，则需要回表。覆盖索引可以有效提高性能，因为只需要搜索一次树。

按照这种思路，联合索引在进查询联合索引内的字段时，也能产生覆盖索引，不需要回表。

B+ 树这种索引结构，可以利用索引的“最左前缀”，来定位记录。索引项是按照索引定义里面出现的字段顺序排序的。这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符。

MYSQL做词法分析语法分析的时候是通过建立最左子树来建立语法树的，解析的过程也是从左到右所以遵循最左前缀的原则。

因此第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。

MySQL 5.6 引入的索引下推优化（index condition pushdown)，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。