MySQL InnoDB存储引擎索引：数据结构与算法原理和优化概述

大家早上好！今天我为大家讲解的是MySQL InnoDB存储引擎索引的数据结构与算法原理和优化概述，大致分为这个部分分别给大家进行介绍。

首先我们来看一下MySQL整体的架构，MySQL大致可以分为四层，第一层，主要不同客户端的连接，第二层，主要是处理客户端的连接，第三层，处理客户端的SQL语句，第四层，存储引擎执行SQL语句。

如果我们使用JDBC执行一条插入的SQL语句，整个流程是如何执行的呢？首先，JDBC属于第一层，通过第二层的连接处理连接到MySQL服务器，接下来，看缓存中是否有已经执行过的相同语句，如果没有通过解析器对SQL语句进行解析，然后再通过优化器对SQL语句进行优化，最终调用第四层的存储引擎的接口，执行插入语句，将数据存储到文件系统。MySQL 的存储引擎采用了插件的形式，每个存储引擎都面向一种特定的数据库应用环境。今天我介绍的就是最关键的第四层存储引擎层中最常用的InnoDB存储引擎的数据结构与算法原理。

在计算机中，为了方便数据的的查找和定位，任何事物通常都会被描述成一对由键值构成的二元组。比如在一个小范围内，我们每一个人的名字都可以成为认定我们每一个人的键。但是范围稍微大一点，就会出现重名的情况，于是我们会给每一个人一个特定的身份号，比如大学里的学号。任何事物的键都很小，能比较，而描述他们的值可以很大。比如对于大学里的每一个学生，他的全部档案构成这个对象的值。

树状结构有很多巧妙之处，比如二分（或者N分）的直接结果就是一层层地将世界上的事物分门别类，每一类都可以看成一个集合。在层层分类之后，同一集合内部的各个元素之间、不同集合之间的关系也就一目了然了。不过对于很多问题，如果真的能够直接采用N分（对应的也就是N叉树），会比进行好几次二分更加有效率，比如建立单词字典这件事，看起来直接采用26叉树更好，逻辑上更清晰。因此，在一些特定的场合，我们是直接采用N叉树。当然，不受限制的N叉树实现起来非常麻烦，而且一旦查找在某个节点分叉太多时，效率会非常低，因为查找的效率从对数复杂度变成线性复杂度。针对这种情况，两位计算机科学家提出了一种受限制的N叉树——B树。根据这两位科学家在论文中的定义，m阶B树是满足以下特性的树：

1.每个节点最多有m个子节点。 

2.每个内部节点至少有⌈m/2个⌉子节点。 

3.每个非叶节点至少有两个子节点。 

4.所有的叶子都出现在同一层面上，不携带任何信息。 

5.具有k个子节点的非叶节点包含k−1个键。 

每个内部节点的键充当分隔值，分隔子树。例如，如果一个内部节点有3个子节点(或子树)，那么它必须有2个键:a1和a2。最左边子树的所有值都小于a1，中间子树的所有值都在a1和a2之间，最右边子树的所有值都大于a2。

在计算机中，使用的比较多的是B树的的一个变种B+树，B+树和B树基本相同，除了两个改进之处：

1.所有的非叶节点只保留键，它们的作用是确定子节点中关键值的区间。所有的内容（连同它们的键）都必须保留在叶子节点里。

2.用一个指针将所有的叶节点从头到尾穿起来。

B+树相比B树有两个优点。一个是结构比较干净，因为中间的节点只有关键值和指向下一级节点的指针，而不再保存每一个事物的内容。另一个则是通过叶节点之间的指针，将所有的数值排序好，这样便于一次访问一大批数据。

在计算机进行数据处理最常用的软件数据库系统中，通常用B+树，而不用二叉树或者N叉树存储信息。那么前者相比后两者有什么优点呢？简单来说就是能平衡好运行时间和存储效率之间的关系。我们来看这样一个问题：如何利用树状结构存储一个字典？

如果使用二叉树，可以用五次二分为26个字母表建立起一棵二叉树，然后进过五次查找找到第一个字母，再类似的往下一个字母一个字母的查，这个方法的问题是由于有些字母出现的频率很高，而有些字母出现的频率较低，因此这课二叉树极为不平衡，查起字典来效率很低。

如果使用26叉树，每个节点都要预留26个子节点的位置，这样层数会很少，查字典的效率很高，但是由于很多字母的组合不会出现，因此这棵树中绝大部分预留的位置都被浪费了。

使用B+树，则可以解决刚才讲到的问题。

我们可以看到B+树无论是在一个节点内的键，还是在最底层所有叶节点中的键，都是排序好的，因此它的查找和二叉树同样有效，都是对数复杂度，具体的推导我待会会介绍。B+树相比于二叉树有一个明显的优点，就是很容易找出一个区间内所有的信息。比如我们要找以cba开头的所有单词，可以先找到cba开头的第一个单词，然后利用B+树中叶子节点的指针，顺序往后读取即可，直到找到以cba开头的最后一个单词时结束。

我们来看一下具体怎么对B+树进行插入删除的规则：

（如果节点都不满，直接插入；如果节点满，则需要拆分）

（当节点中的信息数大于填充因子，直接删除；当节点中的信息数小于填充因子，则需要合并）

动态图像演示：https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

那么对B+树操作的复杂度如何估算呢？

我们假定B+树中有N个数据，每个节点都有M个键，那么搜索时访问节点的数量是 ，节点内的搜索时间复杂度是 ，因为它们是排好序的，我们可以知道这两个数相乘使用对数的换底公式可以得到，因此它的查找和二分查找一样有效。更新的操作的复杂度和查找是一样的，对于插入操作，我们需要先找到插入的位置，然后再将该数据插入到该位置上，如果需要拆分合并，则需要对节点中的数据进行复制，如果上一级需要做同样的事情直到根节点，每次拆分合并的复杂度是O(M)，B+树的高度是，那么对于插入操作的时间复杂度我们可以知道是，删除操作同理因为合并，时间复杂度也是。 

那么B+树在InnoDB存储引擎中的实现方案是什么呢？

InnoDB中的索引可以分为聚集索引和辅助索引。聚集索引就是按照每张表的主键构造一棵B+树，同时叶子节点中存放的即为整张表的行记录数据。辅助索引叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签，辅助索引的书签就是相应行数据的聚集索引键。辅助索引的存在并不影响数据在聚集索引中的组织，因此每张表上可以有多个辅助索引。当通过辅助索引来寻找数据时，InnoDB存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。

那么我们如何利用B+树的特性对InnoDB进行索引优化呢？

下面我将为大家介绍两个概念。

第一个向大家介绍的是索引选择性，是指不重复的索引值与表记录数的比值，选择性的取值范围为(0, 1]，选择性越高的索引价值越大。

第二个是最左前缀匹配原则，MySQL会一直向右匹配直到遇到范围查询就停止匹配，我在这里建立一棵形如(a,b,c)联合索引的 B+树，其中的非叶子节点存储的是第一个关键字的索引 a，而叶子节点存储的是三个关键字的数据。这里可以看出 a 是有序的，而 b，c 都是无序的。但是当在 a 相同的时候，b 是有序的，b 相同的时候，c 又是有序的。以 select * from t where a=2 and b>0 and c =1; 为例，a，b可以用到联合索引，c不可以，因为当查询到 b 的值以后，c 是无序的。所以就不能根据联合索引来确定到底该取哪一行。

然后我们就可以知道建索引的几个原则，尽量选择区分度高的列作为索引，联合索引的最左匹配原则，还有就是索引列不能参与到运算，原因是B+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较。

从刚才的图片可以看到employees表只有一个索引<emp_no>，那么如果我们想按名字搜索一个人，就只能全表扫描了：

如果频繁按名字搜索员工，这样显然效率很低，因此我们可以考虑建索引。有两种选择，建<first_name>或<first_name, last_name>，看下两个索引的选择性：

<first_name>显然选择性太低，<first_name, last_name>选择性很好，但是first_name和last_name加起来长度为30，有没有兼顾长度和选择性的办法？可以考虑用first_name和last_name的前几个字符建立索引，例如<first_name, left(last_name, 3)>，看看其选择性： 

选择性还不错，但离0.9313还是有点距离，那么把last_name前缀加到4：

这时选择性已经很理想了，而这个索引的长度只有18，比<first_name, last_name>短了接近一半，我们把这个前缀索引建上后再执行一遍按名字查询，比较分析一下与建索引前的结果：

性能的提升非常显著的，查询速度提高了256倍。

最后来介绍一下InnoDB索引引擎的全文索引功能的实现，我们可能在网上看到过大多数的文章在说到MyISAM和InnoDB的区别的时候，都会说到InnoDB不支持全文索引，事实上在最常用的MySQL5.7这个版本中InnoDB已经支持全文索引，那它是如何实现的呢？我们看来看一下它的数据结构，它是使用文档列表中数据进行分词，得到词条，对词条进行编号，以词条创建索引。然后记录下包含该词条的所有文档编号。

参考文献：

[1]姜承尧 著；MySQL技术内幕-InnoDB存储引擎；机械工业出版社，2011

[2] MySQL5.7参考手册 - https://dev.mysql.com/doc/refman/5.7/en/