Mysql索引杂谈

结论：索引是把双刃剑，可以提高数据库性能，也会影响数据库性能

1. 利：

• 索引加快数据查询速度，提高数据库查询性能。

2. 弊：

• 数据库中索引是以文件的方式存储的，需要用的时候读取到内存中，因此索引的I/O操作会影响数据库的性能；
• 此外插入和更新操作会更改索引，因此会影响数据库插入和更新的性能，并且索引会占用一定的磁盘空间，使数据库变大。

背景知识

• 索引的本质： MySQL官方定义为：索引是帮助MySQL高效获取数据的数据结构，所以索引的本质是一种数据结构。常用的数据结构有：集合，线性结构，树，图等。
• 索引的目的：数据库查询是数据库最主要的功能之一，索引的目的在于加快数据库的查询速度，从而提高数据库的使用性能。
• 最基本的查询算法是顺序查找，复杂度为O(n)，在数据量较大的情况下性能较差；其次有二分查找，复杂度为O(logn)，在数据量大的情况下性能较好。不同的查询算法需要适配不同的数据结构，顺序查找主要针对的是线性结构；而二分查找主要适用于二叉查找树。
• 在数据库中，数据本身的组织结构不可能完全满足各种数据结构（比如，二叉查找树需要排序），所以数据库需要在数据之外，还维护满足特定查找算法的数据结构，这些数据结构以某种方式指向具体的数据，通过查找这些数据结构，就可以快速的查询数据。这种数据结构，就是索引。一个简单的示例如下：
  图1.png
• 图1中展示了一种简单的索引方式，左边记录是物理地址，存放在磁盘上，为了加快col2的查找，可以维护一个右边所示的二叉查找树，每个节点包含索引键值和对应记录在磁盘上的物理地址，这样通过查找树就可以在O(logn)的复杂度内获取相应的数据。（图中示例使用了二叉树做为索引是数据结构，其实是一种不好的结构，后续拓展中会说明）

Mysql索引

在Mysql中，索引是属于存储引擎级别的概念，因此不同的存储引擎对索引的实现方式是不同的，主要常用的是MyISAM和InnoDB两个存储引擎。（MyISAM提供表级锁，适用于基本上是查询操作的数据库；InnoDB提供行级锁，适用于更新，插入较频繁的表）

MyISAM和InnoDB两个存储引擎主要使用B+树做为索引。B+树是一个树形的数据结构，特点是：

• 每个节点的指针上限是2d
• 内节点不存储data，只存储key；只有叶子节点才存储数据

聚簇索引和非聚簇索引区别：

聚簇索引和非聚簇索引

MyISAM索引结构：

MyISAM存储引擎中数据文件和索引文件是分离的。
MyISAM的索引主要分为主索引和辅助索引：MyISAM索引方式也称为“非聚集”索引

• 主索引（primary key）：以主键做为索引，因此key是唯一的；索引示例图如下所示：

  
  图2
  

  图2中按照主键构造了个B+树，叶子节点中存储了主键记录在磁盘上的地址，因此通过O(logn)的复杂度就可以索引到记录。

• 辅助索引（secondary key）：辅助索引以非主键做为索引，因此key是可以重复的

  
  图3
  

  图3中的辅助索引B+树，叶子节点的内容中也保存了磁盘上记录的地址，然后读取相应的数据记录。

InnoDB索引结构：

InnoDB存储引擎也分为主索引和辅助索引：InnoDB索引方式也称为聚集索引
InnoDB和MyISAM最大的区别是：InnoDB数据文件本身就是索引文件。因为InnoDB的数据文件本身是按主键聚集的，所以InnoDB要求表必须有主键，如果没有显示指定主键，InnoDB会自动选择可以唯一标识数据记录的列做主键；如果不存在，则表生成一个隐含字段作为主键（字段为6个字节，长整形）。

• 主索引：主键做索引

  
  图4
  

  数据记录在叶子节点中，通过查找直接访问查询数据。

• 辅助索引：非主键做索引

  
  图5
  

  辅助索引的叶子节点中值存储索引键值和主键值，然后通过主键值在主索引中进行搜索数据。

索引总结

• 不要使用过长的字段做为索引，过长的字段会使索引的数据结构变大，占用更多的空间，因此影响数据库的性能。（索引做为文件保存在磁盘上，当需要查询索引的时候会从文件读取，因此过长的字段会影响索引整体的I/O性能）
• 在数据库中尽量使用单调增的字段做为主键，因为索引本身是一个B+树，如果字段是非单调增的，则插入操作会频繁的分裂B+树来调增数据的有序性和平衡性，效率十分低下。

索引优化策略

MySQL的优化主要有结构优化和查询优化。索引策略属于结构优化的范畴。下面使用Mysql官方提供的employees数据库示例来演示索引策略。

employees数据库安装：

数据下载：https://launchpad.net/test-db/employees-db-1/1.0.6
参考网页：http://dev.mysql.com/doc/employee/en/employees-installation.html
Mysql5.7版本可能会报错，参考网页：http://stackoverflow.com/questions/36322903/error-1193-when-following-employees-database-install-tutorial-with-mysql-5-7-1

图6

最左前缀匹配原理

要想高效的使用索引，首先需要知道查询操作怎么使用索引，目前常用的是两种索引：单列索引，组合索引（多列顺序组合）。

以employees数据库中的titles为例，索引如下图所示：

• 图7

从图7中可以看出，titles存在两个索引，第一个是<emp_no,title,from_date>元组的组合索引（主索引）；第二个是单列的辅助索引（emp_no）。下面通过语句看索引使用的几种情况：

• 全列匹配：

  • 顺序查询索引：

    
    图8
    

    从图中可以看出，查询条件的顺序和索引一致，全列匹配使用了主索引。

  • 乱序查询索引：

    
    图9
    

    从图中看出，不管查询条件的顺序如何，全列匹配都会使用索引，因为数据库本身会把sql语句进行优化来匹配索引。

• 部分列匹配（最左前缀匹配）：

  • 第一列查询条件：

    
    
    图10
    

    从图10中可以看出，如果按第一列进行匹配，后续的列也必须按照顺序排列，不然只会使用第一列来索引，第一张图片，用来两列做为索引；第二张图片只匹配第一列（两张图片key_len不同）。

  • 非第一列查询：

    
    
    图11
    

    从图11中可以看出，如果查询条件中不含有第一列，则不能使用索引。

• 优化示例：
  当我们使用emp_no和from_date来进行索引时，只会用到emp_no的最左匹配索引，索引语句如下所示：

  select * from titles where emp_no=10009 and from_date='1990-02-18';

但是这只用到了emp_no这个字段的索引，因为缺少中间的title字段，我们使用distinct，发现title只有固定几个值，因此，可以在sql中补全title来进行全列匹配索引。

图12

索引选择性

既然索引可以加快查询速度，是不是意味着只要查询语句需要，就可以建上索引？答案是否定的。因为索引虽然可以加快查询的速度，但索引本身会占用存储空间，并且数据库进行DML操作时会调整索引的架构，同时mysql也会消耗资源来维护索引，因此索引并不是越多越好。

一般有两种情况不建议添加索引：

• 表的记录少，很少的数据就没有必要建立索引，一般来说，超过2000条记录可以考虑建立索引。
• 索引的选择性较低，也不建议建立索引。索引的选择性是指不重复的索引值与表记录数的比值。（简单的理解就是：如果索引的列存在大量相同的值，那么它的索引是没有意义的）
  示例：比如employees.titles表中title列只有固定的几个值：
  图13
  如图13中所示，title列的索引选择性很低，因此没有必要建立一个单独的title列索引。

我们再看一个示例：employees.employees表中的索引如下图所示，从图中看出employees表中只有一个主键索引，如果我们需要按照名字（first_name，last_name）来查询数据，在数据量较大的情况下速度会很慢，因此我们需要建立名字查询的索引。

图14

首先看下按名字索引的选择性：

图15
从图15中可以看出，如果单纯使用first_name字段进行索引，重复率太高，索引的选择性非常低，因此使用first_name和last_name的联合索引，但是这两个联合索引是不是最好的？答案是否定的，因为这两个字段是啥字符串型，如果使用联合索引，则索引的数据结构会变得比较庞大，占用大量的磁盘空间，导致频繁的磁盘I/O，反而影响数据库的性能。因此可以在索引上做下优化：
图16
当只取last_name前4位时（前缀索引），索引的选择性已然达到了0.9以上，因此是一个性能不错的索引，此外该索引的磁盘空间要比全列索引占用量小，综合性能会更好。前缀索引兼顾了速度与索引大小，但其缺点是不能用于order by和group by操作。

拓展：

• 为啥Mysql索引不使用红黑树？
• 为何Mysql索引倾向于B+树而不是B-树？

两个问题的答案都在于使用B+树做为索引，可以减少索引的磁盘I/O性能。从前面我们可知，索引是一个数据结构，存放在磁盘中，当需要使用索引时，从磁盘读取到内存中，然后在内存中进行索引查询数据。因此索引的查找过程要产生磁盘I/O消耗，相对于内存存取，I/O的速度要比内存低好几个数量级，所以一个索引的优劣性能可以通过索引文件的磁盘I/O消耗来衡量，如果磁盘I/O消耗越低，这就是一个越高效的索引。（所以B+优于红黑树和B-树的点就在于，B+树的数据结构有更小的磁盘I/O消耗）。下面详细介绍：

• 主存存取原理：

  • 主存读取：将地址信号放在地址总线上传给主存，主存读取信号，然后到指定主存位置读取数据，再传输到数据总线上，供其他部件读取
  • 主存写入：将要写入的数据放入数据总线中，写入的地址放入地址总线上，然后主存读取两个总线内容，把数据放入相应地址上。

• 磁盘存取原理：

  • 磁盘主要由大小相同且同轴的盘片组成，磁盘可以转动，磁盘的一头有一个固定的磁头，用于读取磁盘的数据，磁头可以只能沿盘片半径方向运动。盘片上一个个同心圆叫做磁道，磁盘分成若干个扇区，如果要读取某一扇区的内容，需要先将磁头移动到相应的磁道上，这叫寻道时间；再将盘片旋转到相应的扇区，这叫旋转时间。通常情况下磁盘的读取主要是寻道时间。
  • 磁盘本身的速度相比于主存，cpu而言是非常慢的，为了提交效率，就需要尽量减少磁盘的I/O次数，因此磁盘在读取一个扇区后，不会直接停止，而是向后多读取一些内容，这就是磁盘预读。磁盘预读的理论依据是局部性原理，当程序用到一个数据时，它周围的数据也将会被使用到。磁盘预读的长度一般为页的整数倍（页的相关知识请参考Linux内存管理相关知识），主存和磁盘以页为交换单位。

• B+树的索引：

  • 在Mysql索引的设计中，当索引每次新建一个节点时，就会创建一个页，因此一个节点就存放在一个页上，磁盘的一次I/O和主存交换一个页（不考虑预读），也就是一次可以读取一个节点，如果使用红黑树，可以发现红黑树是二叉树，它的高度要远远高于B+/B-树，因此每次读取一个节点进行查找，需要大量的磁盘I/O操作才能查询到数据，因为树的查询性能和树的高度线性相关，因此B+/B-树要优于红黑树。当考虑预读的话，红黑树是二叉树，兄弟节点只有一个；而B+/B-树的兄弟节点有多个，可以充分发挥磁盘预读的功能。
    图17
  • 由于B+树把数据放在叶子节点上，因此B+树在非叶子节点的一个节点上可以存放更多的键值；而B-树把数据和键值放在一起，则一个节点放置的键值相对较少，也就是一个页中存放较少的键值，因此使用B+树会达到更少的磁盘I/O次数，因此性能更好。

B+树磁盘索引过程：

图18

B+树更适合操作系统文件和数据库文件的索引。