索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息，可以将数据库索引和书的目录进行类比，通过书的目录我们可以快速查找到章节位置，如果没有目录就只能一页页翻书查找了，

索引资料结构

可以用于提升查询效率的索引结构很多，常见的有B树索引、哈希索引和B+树索引，接下来我们会对这些索引一一进行介绍，并说明InnoDB为什么采用B+树作为索引，

磁盘IO

档案是存盘在硬盘上面的，当下硬盘的读取速度十分有限，所以在进行查询定位某个资料的时候，应该尽可能地减少磁盘I/O次数，

磁盘预读

由于存盘介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分之一，因此为了提高效率，要尽量减少磁盘I/O，为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的资料放入存储器，这样做的理论依据是计算机科学中著名的区域性原理：当一个资料被用到时，其附近的资料也通常会马上被使用，程序运行期间所需要的资料通常比较集中，

区域性原理：CPU访问存盘器时，无论是存取指令还是存取资料，所访问的存盘单元都趋于聚集在一个较小的连续区域中，

预读的长度一般为页（page）的整倍数，页是计算机管理存盘器的逻辑块，硬件及作业系统往往将主存和磁盘存盘区分割为连续的大小相等的块，每个存盘块称为一页（在许多作业系统中，页的大小通常为4k），主存和磁盘以页为单位交换资料，当程序要读取的资料不在主存中时，会触发一个缺页例外，此时系统会向磁盘发出读盘信号，磁盘会找到资料的起始位置并向后连续读取一页或几页载入存储器中，然后例外回传，程序继续运行，

合理利用磁盘预读

一般来说，索引本身也很大，不可能全部存盘在存储器中，因此索引往往以索引档案的形式存盘的磁盘上，这样的话，索引查找程序中就要产生磁盘I/O消耗，相对于存储器存取，I/O存取的消耗要高几个数量级，所以评价一个资料结构作为索引的优劣最重要的指标就是在查找程序中磁盘I/O操作次数，换句话说，索引的结构组织要尽量减少查找程序中磁盘I/O的存取次数，

如果我们能合理使用磁盘预读的特性，使每次磁盘IO读到的页中的资料都是有用的，就可以大大提升资料的查询效率，

B树索引

B树可以看作是对二叉查找树的一种扩展，B树允许每个节点有M-1个子节点，B树有以下特点：

1. 根节点至少有两个子节点；
2. 每个节点包含M-1条资料，节点中的资料安装索引递增顺序排序；
3. 节点中有最多有M个指标指向下一层节点，这些指标位于节点的多个资料之间，下一层节点的所有资料值大于指标左侧的资料，小于指标右侧的资料；
4. 每个节点至少包含M/2条资料；

接下来我们用下表示例的用户资料来构建B树，如表所示，用户资料包含姓名、性别、年龄三个栏位，我们把用户年龄作为数据库主键(假设年龄具有唯一性)，那么构建出来的B树的结构如下图所示，

|||||||||||
|--|--|--|--|--|--|--|--|--|--|--|
|姓名|陈尔|张散|李思|王舞|赵流|孙期|周跋|吴酒|郑史|
|性别|男|男|女|女|男|男|男|女|男|
|年龄|5|10|20|28|35|56|25|80|90|

![B树索引]

相比较与常见的二叉树，B树的一个节点中存放了更多的资料，这样做可以有效的减少一次资料查找程序中的磁盘IO次数：

• 二叉树每个节点只存放一个资料，节点之间用指标关联，节点之间的空间是离散的，所以每个节点都对应一次磁盘IO，查找一次资料的IO次数为O($log_2$N)；
• B树的节点可以存放M-1个资料，如果这M-1个资料刚好可以放到一个页中，那么B树查找一次资料的IO次数为O($log_M$N)；

哈希索引

哈希索引基于哈希表实作，只有精确匹配索引所有列的查询才有效，哈希表是一种以键-值(Key-Value)存盘资料的结构，用户可以在O(1)时间复杂度内按照Key查找到对应的Value，

哈希表通常是一个阵列，资料在阵列中的位置可以按照索引的值安装哈希算法进行计算，如果两个资料的索引值计算出来的位置相同，那么通常可以采用链地址法解决冲突（其它解决地址冲突的方法还有开放定制法，链地址法，公共溢位区法，再散列法等），

如下表资料所示，我们依旧按照用户的年龄为用户资料建立索引(假设用户年龄不会相同)，我们采用的哈希算法为 addr=age%10，我们可以建立长度为10的阵列作为哈希表，按照哈希函式一一把用户放入哈希表，按照用户年龄查找用户时，可以直接计算出用户所在的位置，从而得到用户信息，最终得到的哈希表以及查询流程如下图所示，

哈希索引有以下优点：

1. 占用的额外空间小，为资料新建一个哈希索引需要的额外空间为O(N)，和索引栏位长度无关；
2. 查询速度极快，哈希函式合理的情况下，程序可以在O(1)的磁盘IO次数内查找到资料；

哈希索引有以下缺点：

1. 无法进行范围查询，哈希程序中已经丢失了索引的顺序性；
2. 无法对资料进行排序查找，比如查找年龄最大的用户；
3. 无法使用部分索引查找，比如前缀查询等；
4. 哈希函式不合理的情况下，会导致哈希冲突问题，造成查询效率变低；

B+树索引

InnoDB使用的索引的资料结构是B+树，数据库表定义中的每一个索引对应一颗B+树，默认的聚簇索引也是一颗B+树，B+树有以下特征：

1. 所有节点关键字是按递增次序排列，并遵循左小右大原则；
2. 非叶节点的子节点数在1到M之间(下图中M为3)，空树除外；
3. 非叶节点的索引数目大于等于ceil(M/2)个且小于等于M个；
4. 所有叶子节点均在同一层，叶子节点之间有从左到右的指标；
5. 资料存盘在叶子节点，非叶子节点只存盘索引；

接下来我们用几条示例的用户资料来构建B+树，如表所示，用户资料包含姓名、性别、年龄三个栏位，我们把用户年龄作为数据库主键(假设年龄具有唯一性)，那么构建出来的B+树的结构如下图所示，

B+树索引资料结构有以下列出的几种优势：

1. 查询性能稳定，查询一条资料需要的IO次数往往是树的高度次；
2. 范围查询效率高，安装索引范围查询时，可以先查找的第一个满足要求的资料，然后向后遍历，直到第一个不满足条件的资料为止，中间的资料都符合要求；
3. 查询效率高，往往一次资料查询只需要2~3次磁盘IO；
4. 叶子节点存盘所有资料，不需要去B+树之外找资料；

InnoDB为什么采用B+树

在InnoDB引擎中，我们为数据库创建的索引都是以B+树的形式存在，为什么InnoDB不采用哈希索引或者B树索引呢？主要是基于以下原因：

• 数据库查询经常会出现非等值查询，哈希索引在这种情况下无法作业；
• 相比于B树，B+树索引非叶子节点不存放资料，从而磁盘一次IO可以读取更多的索引资料，有效减少磁盘IO次数；
• 数据库查询经常会出现范围查询，B+树底层的叶子节点之间按照顺序排列，可以更有效的实作范围查询；

自增主键

通过上文我们知道，B+树需要维护索引的有序性，

1. 当用户向B+树插入资料，如果插入点对应的节点有空余位置，那么只需要挪动节点中的资料，并把需要插入的资料放入B+树即可；
2. 当用户向B+树插入资料，如果插入点对应的节点没有空余位置，那么就需要生成一个新的节点，并把一部分资料挪过去；这种情况不仅会影响插入效率，由于分裂出来的节点只有部分资料，所以会导致空间的利用率降低；
3. 当用户洗掉B+树中的资料时，如果节点或相邻节点的资料量很少，那么只需要直接洗掉资料，并按挪动节点中的其它资料即可；
4. 当用户洗掉B+树中的资料时，如果节点和相邻节点的资料量很少，那么在洗掉之后，可能需要把节点和相邻节点合并，从而提高空间利用率；

基于B+树需要维护索引有序性的特点，我们对索引栏位提出以下建议：

1. 对于资料插入比较多的场景，主键索引栏位最好是递增的，递增的主键每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂，
2. 主键索引的长度应当尽量小，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小，

在InnoDB中，我们应当尽量使用自增主键，自增主键有插入效率高、占用空间小等优势，

资料空洞与重建索引

资料空洞

当你对InnoDB进行修改操作时，例如洗掉一些行，这些行只是被标记为“已洗掉”，而不是真的从索引中物理洗掉了，因而空间也没有真的被释放回收，InnoDB的Purge执行绪会异步的来清理这些没用的索引键和行，但是依然没有把这些释放出来的空间还给作业系统重新使用，因而会导致页面中存在很多空洞，如果表结构中包含动态长度栏位，那么这些空洞甚至可能不能被InnoDB重新用来存新的行，因为空间空间长度不足，

资料空洞带来的问题：

1. 洗掉表中的资料后，表占用的空间不会变小，造成空间浪费；
2. 会降低资料查询的速度，因为空洞会占用页空间；

我们可以通过以下SQL来查看数据库中的空洞大小，执行陈述句如下所示，回传结果中的DATA_FREE表示表中空闲资料块的大小，

select data_length,data_free from information_schema.tables where table_schema='test' and table_name='test';

重建索引

当一张表的索引中的资料空洞过多时，会影响SQL陈述句的执行效率，此时我们就需要清理这些资料空洞，

清理资料空洞比较好的办法是重建索引，因为重建索引的程序中，会按照索引的大小排序后建立索引，建立出来的索引比较紧凑，

有什么办法可以重建索引呢？我们比较直观的想法肯定是先洗掉索引，再重建索引，然而不论是洗掉主键还是创建主键，都会将整个表重建，所以连着执行这两个陈述句的话，第一个陈述句就白做了，

alter table user_info drop primary key;
alter table user_info add primary key(id);

InnoDB中可以通过以下转换资料引擎的陈述句来重建表的所有索引，这是因为在转换资料引擎（即使没有真正转换）的程序中，会读取表中所有的资料，再重新写入，这个程序中，会释放空洞，需要注意的是，通过这种方法重建索引耗时比较长，

alter table test engine=innodb

本文最先发布至微信公众号，著作权所有，禁止转载！