Mysql Innodb 索引分析

什么是索引

数据库索引是我们每个开发人员既熟悉又陌生的东西，几乎所有的业务系统都要与索引打交道，如果数据库查询慢了，第一时间想到的也是添加一个索引试试。但是大多数人并没有去深究这个神奇的东西究竟是如何起作用的。

其实索引就像一本书的目录，没有目录的书，我们只能一页一页的往下翻，边看边找自己感兴趣的内容。而有了目录，我们想看书的哪一部分只需要翻翻目录的介绍，找到对应的页码，然后就可以快速的翻到感兴趣的部分了。数据库也是同样的道理，数据通常是保存到磁盘中的（ssd或者hdd），而磁盘的读取速度远远不如内存那么快。数据量较大的情况下，如果不能定位数据的大致位置，而采用顺序扫描的方式去查找匹配的数据，那用户每次操作后等待结果的时间大概都能打一把王者了，这个时候就需要索引出场了。

索引的原理其实很简单，就是通过某种数据结构把要查询的关键字与实际的数据存储位置进行映射。这样我们在搜索数据的时候，就不是直接把数据逐条从磁盘上查出来和关键字进行比较，而是先从索引中查找到这个关键字，然后得到关键字所映射的数据记录的实际位置，再根据存储位置到磁盘上去读取相应的记录。索引都是排好序的，而且索引的部分结构可以加载到内存中，这些都能极大的提升检索的速度。

基于BTree的索引实现

原理上很简单，但是要实现一个高效的数据索引并不容易。目前主流的关系型数据库基本还是使用Btree(也叫B-Tree)的各种变形结构来实现数据索引的。顾名思义，btree也是一种树形结构，中文名称叫做平衡多路查找树，结构类似于下图：

Btree数据库结构图 (1).png

Btree的每个节点主要包含三类信息：数据的关键字（key），数据本身，指向子节点的指针。key与指针交替间隔的，而且从图上可以很直观的看出，所有的key都是从左到右升序排列的，每个key在整个Btree中只会出现一次。

在Mysql的索引实现中，每个Btree的节点存储到一个页（Page）中,这是Mysql磁盘管理的最小单位，InnoDB 读取数据时必须以Page为单位整体读出来放到内存中。我们以查询关键字10为例，大致的过程如下：

1. 根据根节点找到Page1，读入内存。【磁盘I/O操作第1次】
2. 比较关键字10在区间<17，找到Page2的指针P1。
3. 根据P1指针找到Page2，读入内存。【磁盘I/O操作第2次】
4. 比较关键字29在区间（8,12），找到Page6的指针P2。
5. 根据P2指针找到Page6，读入内存。【磁盘I/O操作第3次】
6. 在Page6中的关键字列表中找到关键字10以及对应的数据。

整个过程只需要3次磁盘IO操作，3次内存操作，效率比逐条读取比对的方式提升了很多。

B+Tree的优化

Btree能够极大的提升数据查询的效率，但仍然存在一些缺点，比如：数据和关键字都存储到节点中，占用的空间较大，导致单个节点能容纳的Key的数量较少，每次能读入内存的key也就越少，这样可能会影响搜索效率；另外Btree的查询效率页不稳定，如果关键字位于上层节点，则可以很快的返回结果，但关键字如果在更深的节点上，则查询的效率会大大降低。针对这些问题，人们又对Btree进行一些细节上的优化，使其能够更加满足数据库索引的需求，这就是B+Tree。Mysql InnoDB的索引就是采用B+Tree实现的：

B+tree数据库结构图.png

B+Tree的改进主要有3点：

1. B+Tree的非叶子节点并不存储数据本身，只存储Key和子节点指针。因此单个节点可以存储更多的Key，一次性读入内存的关键字也就越多，相对IO读写次数就降低了。

2. B+Tree的叶子节点包含了所有的Key和数据，而且每个叶子节点都存储了前后两个叶子节点的位置指针，这样在区间查询时可以直接从叶子节点进行遍历，跳过上层的根节点，可以提高区间查询的效率。

3. B+Tree的Key可能出现在多个节点中，而Btree的Key只会出现在唯一的一个节点，由于B+Tree的数据都只存储在叶子结点中，所以不管查询什么Key，最终都需要沿着根节点逐次搜索到叶子节点才能找到数据，这样可以避免不同的Key查询效率差异过大的问题。

聚簇索引(Clustered Index)和非聚簇索引 (Non- Clustered Index)

聚簇索引就是数据和索引本身是存储在一起（物理上的），比如上面B+Tree的示意图，黄色小格里面的Data就是数据本身；聚簇索引的查询效率肯定是最高的，只要找到了数据就可以直接读取了，不需要再进行任何跳转。但是因为数据只能存储在一个位置，所以每张表的聚簇索引肯定也就只有一个。在Mysql InnoDB中，主键索引就是聚簇索引，不能修改（没有主键的表就看第一个唯一索引，都没有Mysql就自己生成一个），所以主键查询的效率是最高的。和数据的存储位置无关的索引都是非聚簇索引（也叫二级索引），这个时候叶子节点里面存储的Data实际上是数据的主键（而不是数据本身），所以非聚簇索引的查询会多一个步骤，找到数据主键之后还要到聚簇索引中去查找实际的数据。

主键的选择

根据以上对索引结构的分析，我们就能了解一些Mysql InnoDB数据表主键的一些限制：

1. 不要用过长的字段作为主键：因为所有的二级索引的data区域都是存放到数据记录的主键，如果主键过长会导致二级索引的空间占用变大，影响查询效率；
2. 尽量使用单调自增的字段作为主键：主键索引本质上是一棵B+Tree，key是有序排列的；如果主键是单调自增的，那么产生新数据的时候，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页，如图：
   新增数据时B+Tree分裂示意图.png
   这样可以形成一个紧凑的存储结构（没有磁盘碎片），也无需移到其它已有的节点，索引的插入效率较高；反之，如果主键是类似于身份证号码那样的非自增结构，索引在插入时会产生大量额外的节点移动开销，导致大量的磁盘碎片，而且已被缓存的索引页可能会被强制刷新，影响插入效率。

使用索引的一些注意事项：

1. 索引不能解决一切问题，好的索引会提高查询效率，但同时也会增加插入数据的开销，需要综合考虑系统的性能瓶颈来进行设置；

2. 如果需要索引的列是一个很长的字符列时，可以考虑使用前缀索引，前缀的长度计算需要综合实际的数据来考虑。例如：

ALTER TABLE `city_demo` ADD KEY `idx_city` (`city`(7))

3. SQL查询时，如果索引列必须要是独立的，否则无法使用索引，索引。“ 独立的列” 是指索引列不能是表达式的一部分， 也不能是函数的参数。例如下面的情况都无法使用索引：

SELECT actor_id FROM sakila.actor WHERE actor_id + 1 = 5;

SELECT ... WHERE TO_DAYS( CURRENT_DATE) - TO_DAYS( date_col) <= 10;

4. 复合索引的索引列序非常重要：建立复合索引时，多个字段的排列顺序是能够影响索引是否生效的重要问题。简单的说，复合索引是按照从左到右的顺序生效的，如果查询条件中缺少中间的部分字段，则仅左边能够匹配的索引部分可以生效。假设有一个复合索引（a,b,c），则有以下的规则：

select * from exp_tbl  where a=3  and b=45 and c=5 --这种三个索引顺序使用中间没有中断，全部发挥作用；
select * from exp_tbl  where a=3  and c=5 -- 这种情况下b就是断点，a发挥了效果，c没有效果
select * from exp_tbl  where b=3  and c=4 -- 这种情况下a就是断点，在a后面的索引都没有发挥作用，这种写法联合索引没有发挥任何效果；
select * from exp_tbl  where b=45 and a=3 and c=5 -- 和第一种情况是一样的，条件书写的顺序无关

5. 如果一个查询中条件经常都是不固定的（比如用户输入条件进行查询，这种情况很常见），就不太好设置复合索引了，还有一种方式就是把潜在的可能成为条件的数据列都设置成单列索引。Mysql从5.1开始支持index merge技术（索引合并），简单的说就是如果一个查询有个多个条件，在没有合适的复合索引可以使用的情况下，Mysql会同时使用多个单列索引进行扫描，再把扫描的结果进行合并（并集，交集）。但索引合并在性能是可能是不可控的（并集，交集操作可能消耗大量的资源），所以使用时需要慎重，如果可能的话使用复合索引仍然是最佳的选择。