MySQL中的InnoDB索引

为什么是B+树？

在MySQL的InnoDB存储引擎中，索引的数据结构是B+树。B+树是一棵N叉树，在总结点数不变的情况下，当N越大，树高会越矮。以int型为例，这个N大概是1200。当树高是4的时候，就可以存1200的3次方个值，大概是17亿。在这棵B+树上检索一个值最多只需访问4次磁盘（值是保存在叶子节点上的，从根节点到叶子节点总共要访问4个节点，每访问一个节点相当于访问一次磁盘）。所以B+树能很好的减少磁盘的访问次数。

索引的类型

在InnoDB存储引擎中，根据叶子节点保存的内容，索引分为聚簇索引和二级索引。聚簇索引的叶子节点保存的是整行数据，InnoDB中主键索引就是聚簇索引，二级索引的叶子节点保存的是主键的值。当使用二级索引进行查询的时候，如果要返回的字段不在二级索引中，还要在找到叶子节点后根据主键去主键的聚簇树获取其他的字段信息，此过程称为回表。

最左前缀匹配原则

如果创建了联合索引，会遵循最左前缀匹配原则来使用这个索引。假如在表test中有联合索引(a,b,c)，以下三个SQL都会用到该索引：

• select * from where a = ?
• select * from where a = ? and b = ?
• select * from where a = ? and b = ? and c = ?

覆盖索引

假如索引中包含了要返回的字段，此时就不会再回表，利用此特性可以提高查询速度。如：

select a,b,c from test where a = ? and b = ? and c = ?

此SQL语句使用了索引(a,b,c)，因为索引中已包含要返回的字段a、b、c，所以可以直接在这棵索引树上获取结果，不用再回表。

索引的维护

随着数据的不断新增，MySQL需要维护索引的有序性，当新增的值要插到已满的数据页中，此时需要新增一个数据页，移动一部分原有的数据到该页中，此过程为页分裂，会导致数据页的利用率降低大约50%。相反，当相邻两个页由于数据的删除导致利用率很低时，会将这两个数据页合并，是页分裂的逆过程。
可以通过重建索引来使数据页有空洞的索引更加紧凑。