Mysql InnoDB索引原理
理解Mysql索引的原理和数据结构有助于我们更好的使用索引以及进行SQL优化，索引是在存储引擎层面实现的，所以不同的引擎实现的索引也有一定的区别，但是在生产环境中，我们最常用的就是InnoDB引擎和B树索引，OK，那本文要讨论的重点也同样是InnoDB引擎下的B树索引。
我们建立一个表来进行测试，表的DDL如下所示，我们要关注的是表t_book上的主键索引id和name author publish_date三列组成的索引test_index。
CREATE TABLE `t_book` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(50) NOT NULL,
`author` varchar(50) NOT NULL,
`publish_date` date NOT NULL,
PRIMARY KEY (`id`),
KEY `test_index` (`name`,`author`,`publish_date`)
) ENGINE=InnoDB AUTO_INCREMENT=8 DEFAULT CHARSET=utf8;
B树数据结构
Mysql中的B树索引是使用B+树实现的，关于B+树的数据结构个人认为美团点评技术博客中Mysql索引原理及慢查询优化一文中介绍的非常详实，B+树的数据结构如下图所示。
图中浅蓝色块即磁盘块，根节点磁盘块中存储17和35两个数据，其中指针P1指向小于17的数据，指针P2指向大于17小于35的数据，指针P3指向大于35的数据。显然通过B+树索引查询数据与B+树的高度有关，如上图的B+树索引查找一个叶子节点的数据只需要三次磁盘IO，对于Mysql来说三层的B+树可以索引上百万的数据，这对于查询效率的提升是巨大的。
总结起来Mysql中B树索引有以下关键特点：
- 真实数据存储在叶子节点上，例如根节点的磁盘块中17和35并不是真实数据
- B树索引中的值是按顺序存储的，这一方面说明可以利用B树索引可以用于完成ORDER BY排序操作，当SQL可以使用索引排序时，EXPLAIN查看查询计划EXTRA列是不会出现USING FILESORT的（USING FILESORT为文件排序）；另一方面，这也解释了Mysql索引的最左前缀匹配原则。
- Mysql在上图所示的B+树数据结构的基础上，为每一个叶子节点增加了指向下一个叶子节点的指针，用于方便叶子节点的范围遍历。
如果对以上介绍的特点有疑问，可以直接往下看，我们将在聚簇索引和二级索引的介绍中举例说明以上特点的原理。
Mysql中的B树索引有两种数据存储形式，一种为聚簇索引，一种为二级索引。
聚簇索引
InnoDB一般会使用表的主键来作为聚簇索引，如果一个表没有主键（不建议这么玩）InnoDB会选用一个唯一非空索引来代替，如果没有这样的索引，InnoDB会隐式建立一个聚簇索引。聚簇的含义即是数据行和相邻的键值紧凑的存储在一起，占据一块连续的磁盘空间，因此通过聚簇索引访问数据可以有效减少随机IO，通常使用聚簇索引查找比非聚簇索引查找速度更快。以我们建立的表t_book为例，聚簇索引即为自增主键id，其B树索引数据结构可以用下图来表示。
聚簇索引有以下关键特点：
- 在InnoDB中聚簇索引即为表的存储结构，表的其他列数据也会存储到叶子节点中，从聚簇索引中获取数据比二级索引获取数据要快。
- 聚簇索引是按顺序存储的，因此Insert速度严重依赖于插入顺序，如果在聚簇索引的中间一行插入数据，会导致后面行都会被移动，可能面临页分裂的问题。所以，在插入频繁的表中不建议使用varchar类型的列作为主键，如果真的有这种情况，建议为表增加一个自增主键作为代理键，哪怕这个自增主键没有任何意义（最好避免不连续且值的范围分布很大的聚簇索引）。
- 由于把相关数据保存在连续的硬盘空间上，所以通过聚簇索引聚集数据只需要一次磁盘IO，可以有效加快查询速度。
图中仅画了叶子节点和和其父亲节点，第一个表格存储了id为1~10的数据，第二个表存储了id为11
~20的数据，注意，P1即为上文中提到的指向下一个叶子节点的指针。
二级索引
InnoDB的B树索引中除了聚簇索引，就都是二级索引了，二级索引的含义是索引的叶子节点除了存储了索引值，还存储了主键id，在使用二级索引进行查询时，查找到二级索引B树上的叶子节点后还需要去聚簇索引上去查询真实数据，但是这里有一种特殊情况，即查询所需的所有字段在二级索引中都可以获取，此时就不需要再去回表查数据了，这种情况就是索引覆盖（EXPLAIN中EXTRA列中会出现USING INDEX，本文只关注索引结构，不详细讨论索引覆盖等技术的使用，如果深入理解索引的数据结构，索引覆盖等技术也没有那么神秘）。
在我们的测试表t_book中，test_index即为二级索引，由于我们把除了主键id所有的列都作为一个联合索引，所以在这个表上的查询都可以使用索引覆盖技术，但是具体生产环境中也不建议总是采用这种做法，索引列的增加也会增大插入更新数据时的索引更新成本，具体的优化要视具体情况决策。t_book上的二级索引test_index的索引结构由下图表示。
通过以上结构，我们可以推断出二级索引的以下关键特点：
- InnoDB二级索引中存储主键值，当发生行移动时，不影响二级索引的维护工作
- 通过以上的索引结构我们现在可以非常清晰的理解B树索引的最左前缀匹配原则，例如，如果匹配以Book为后缀的书名，InnoDB引擎需要全量扫描索引test_index才能找到匹配的记录（EXPLAIN中Type列为Index，实际仍然是全表扫描），但是如果要搜索以Book为前缀的记录，则会直接命中索引找到查找的记录
- 另外特别特别特别重要的是，可以通过这个结构图可以理解索引的列前缀匹配原则，我们无法通过这个二级索引树去直接命中搜索作者为Brian Goetz的记录，同样，当我们搜索书名为Thinking in Java，作者名字为B开头的名字，出版时间为2008-3（好吧，这个例子不太合理，假如我们有N本书的书名叫Thinking in Java且作者名字都是B开头的），那我们可以使用二级索引的name和author字段，但是在查询出的N条记录中无法再使用索引中publish_date字段，即Where子句中如果使用了范围条件，后面的字段就无法再使用索引了，当然我们也不能跳过任何一个字段去使用索引（只用name和publish_date字段去搜索）。
索引覆盖：
最左前缀匹配：
列前缀：
二级索引可以说是我们在Mysql中最常用的索引，通过理解二级索引的索引结构可以更容易理解二级索引的特性和使用。
哈希索引
最后聊点轻松的索引结构，哈希索引就是通过哈希表实现的索引，即通过被索引的列计算出哈希值，并指向被索引的记录。
哈希索引有如下特性：
- 哈希索引只包含哈希值和行指针，不包含数据，使用哈希索引必须回表查找
- 哈希索引顺序并不是按顺序存储的，所以不能用于排序
- 哈希索引也不支持部分索引列匹配查找，必须匹配全部列，才能计算出哈希值找到对应记录
参考文献
高性能Mysql 第三版
