MySQL InnoDB索引与算法介绍

一、索引介绍

数据库是用来存储数据的工具，存进去，是为了更方便地取出来，而且越快越好，这样对性能的要求就非常高了。在计算机上运行一个任务，一般有三部分涉及性能，分别是内存大小，CPU及磁盘的速度，而索引是一种存储方式，与它相关的最重要部分就是磁盘，所以磁盘性能的高低，直接影响了在数据库中查找数据的效率。另外，磁盘的性能与读写顺序有关，对于普通的机械硬盘，顺序读写会比随机读写快很多，所以再加快数据库中数据的读写速度时，需要尽可能地避免随机读写，也就是说尽可能地读取连续的数据，这样性能自然就会好一些。在数据库设计中会尽可能地从各个方面都能以顺序读写的方式来操作磁盘介质。

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的一种数据存储结构；提取句子主干，就可以得到索引的本质：索引是数据结构。

我们知道，数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据是有序的，而二叉树查找只能应用于二叉查找树上。但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织）。所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

看一个例子：

上图展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在O(log2n)O(log2n)的复杂度内获取到相应数据。

虽然这是一个货真价实的索引，但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的，原因会在下文介绍。

二、索引的优点

索引用来快速地寻找那些具有特定值的记录，如果没有索引，执行查询时MySQL必须从第一个记录开始扫描整个表的所有记录，直至找到符合要求的记录。表里面的记录数量越多，这个操作的代价就越高。如果作为搜索条件的列上已经创建了索引，MySQL无需扫描任何记录即可迅速得到目标记录所在的位置。如果表有1000个记录，通过索引查找记录至少要比顺序扫描记录快100倍。

索引在MySQL中也叫做“键（key）”，是存储引擎用于快速找到记录的一种数据结构。索引是独立与表之外的一种数据结构，当表数据变化时，随之索引也会改变。索引对于良好的性能非常关键。尤其是当表中的数据量越来越大时，索引对性能的影响愈发重要。在数据量较小且负载较低时，不恰当的索引对性能的影响可能还不明显，但当数据量逐渐增大时，性能则会急剧下降。

索引可以让服务器快速地定位到表的指定位置，索引目前来说应该是对查询性能优化最有效的手段了，索引能够轻易将查询性能提高几个数量级，“最优”的索引有时比一个“好的”索引性能要好两个数量级。

在MySQL中，存储引擎用类似的方法使用索引，其先在索引中找到对应值，然后根据匹配的索引记录找到对应的数据行。假如要运行下面的查询：

如果info表中有100万条数据，要执行上面的查找，如果没有索引则必须遍历整个表，直到ID等于50000的这一行被找到为止。如果在ID列上建有索引，则MySQL不需要任何扫描，直接在索引里面找50000，就可以得知这一行的位置。也就是说，MySQL先在索引上按值进行查找，然后返回所有包含值的数据行。

索引是在存储引擎中实现的，因此，每种存储引擎的索引都不一定完全相同，并且每种存储引擎也不一定支持所有索引类型。

据此特性，总结下来索引有如下优点：

1. 索引大大减少了服务器需要扫描的数据量，加快查询速度，这也是索引的主要原因。

2. 索引可以帮助服务器避免排序和临时表。

3. 索引可以将随机I/O变成顺序I/O。

4. 唯一索引可以保证数据库表中每一行数据的唯一性。

三、InnoDB索引概述

索引有很多种类型，可以为不同的场景提供更好的性能。在MySQL中，索引是在存储引擎层而不是服务器层实现的。所以并没有统一的索标准：不同存储引擎的索引工作方式并不一样，也不是所有的存储引擎都支持所有类型的索引。即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。

InnoDB存储引擎支持以下几种常见的索引：

• B+树索引
• 哈希索引
• 全文索引
• 空间索引

首先，InnoDB存储引擎支持的哈希索引是自适应的，InnoDB存储引擎会根据表的使用情况自动为表生成哈希索引，不能人为干预是否在一张表中生成哈希索引。

目前来说，我们所了解的大多数数据库，其索引都是通过B树或类B树实现的。其中，InnoDB就是使用B+树来实现其索引的，所以某种程度上，B+树和索引可以等同起来。B+树索引就是InnoDB传统意义上的索引，这是目前关系型数据库系统中查找最为常用和最为有效的索引。B+树索引的构造类似于二叉树，根据键值（Key value）快速找到数据。注意B+树中的B不是代表二叉（binary），而是代表平衡（balance），因为B+树是从最早的平衡二叉树演化而来，但是B+树又不是一个二叉树。

另外B+树索引并不能找到一个给定键值的具体行，只能找到的是被查找数据行所在的数据页。然后数据库通过把页读入到内存，再在内存中进行查找，最后得到要查找到数据。

四、数据结构与算法

在MySQL中当谈论起索引时，如果没有特别指明类型，那多半说的是B+树索引。它使用B+树数据结构来存储组织数据。在介绍B+树索引之前先介绍与之密切相关的一些算法与数据结构，这样有助于你更好的理解B+树索引的工作方式。

二分查找法

二分查找法也称为折半查找法，用来查找一组有序的记录数组中的某一记录，其基本思想是：将记录按有序化（递增或递减）排列，在查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。

上面是专业术语，说的简单点。不知道你还记得猜数游戏吗？我想好一个一百以内的数，每次我只能用你猜的数‘大于’或‘小于’我想的数来回答你猜的答案。”请问你最多花几次你就一定能猜中我心里想的数？比如我心里想的数是“4”，那么最多花7次就能猜中答案了。

解题过程如下：

1）你先说50，排除了1半，如我说大于就在1-49之间，如小于在51-99之间。

2）这里我想的是“4”，我会说小于。低了你接着说25，又排除了一半，变为1-24或26-49。

3）这里我还是说小于，你接着说13，又排除了一半，变为1-12或14-24。

4）这里我还是说小于，你接着说7，又排除一半，变为1-6或8-14。

5）这里我还是说小于，你接着说3，又排除一半，变为1-2或4-6。

6）这里我说大于，你接着说5，就变为4或6了。

7）最后你也就知道答案了，那就是4。

猜一百以内的数最多不会超过7次，如果你心里想的是5的话，那么六次也就猜出来了。如果按照顺序查找，则需要4次就可以查出来，看着比二分查找法的效率还快一些，如果你心里想的是98呢？那么结果就大不同了！

二分查找法的应用极其广泛（前提数据必须是顺序存放），而且它的思想易于理解。在InnoDB中对于某一条具体记录的查询是通过对Page Directory进行二分查找得到的，而每页Page Directory中的槽是按照主键的顺序存放的。

二叉查找树和平衡二叉树

在介绍B+树之前，需要先了解一下二叉查找树（又叫：二叉搜索树或二叉排序树）。B+树是通过二叉查找树，再由平衡二叉树，B-树（就是B树）演化而来。在任何一本有关数据结构的树中都可以找到二叉查找树的章节，二叉查找树是一种经典的数据结构。

设x为二叉查找树中的一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。下图显示了一棵二叉查找树。

图中数字代表每个节点的键值。在二叉查找树中，左子树的键值总是小于根的键值，右子树的键值总是大于根的键值。因此可以通过中序遍历得到键值的排序输出，上图中的二叉查找树经过中序遍历后输出：2、3、5、6、7、8。

对上图中这棵二叉树进行查找，如查找键值为5的记录，先找到根，其键值是6，6大于5，因此查找6的左子树，找到3；而5大于3，再找到其右子树；一共找了3次。如果按2、3、5、6、7、8的顺序来找同样需要3次。用同样的方法再查找键值为8的这个记录，这次用了3次查找，而顺序查找需要6次。如果你计算一下，二叉查找树的平均查找速度比顺序查找肯定要快很多，并且顺序查找随着数据量的增大，查找数据速度可想而知。

二叉查找树可以任意构造，同样是2、3、5、6、7、8这六个数字，也可以按照下图的方式建立二叉树查找树。

这棵二叉树查找树的平均查找速度和顺序查找差不多，显然跟上一棵二叉树查找树相比效率就低了。因此若想最大性能地构造一棵二叉查找树，需要这棵二叉查找树是平衡的，从而引入了新的定义–平衡二叉树，或称为AVL树。

平衡二叉树的定义如下：首先符合二叉查找树的定义，其次必须满足任何节点的两个字数的高度最大差为1.显然，上图不满足平衡二叉树的定义。平衡二叉树的查找性能是比较高的，但不是最高的，只是接近最高性能。最好的性能需要建立一棵最优二叉树，但是最优二叉树的建立和维护需要大量的操作，因此，用户一般只需要建立一棵平衡二叉树即可。

平衡二叉树的查询速度的确很快，但是维护一棵平衡二叉树的代价是非常大的。通常来说，需要1次或多次左旋和右旋来得到插入活更新后树的平衡性。如下图中需要多次旋转的平衡二叉树示例。

上图列举了向一棵平衡二叉树插入一个新的节点后，平衡二叉树需要做的旋转操作。除了插入操作，还有更新和删除操作，不过这和插入没有本质的区别，都是通过左旋或右旋来完成的。因此对一棵平衡树的维护是有一定开销的，不过平衡二叉树多用于内存结构对象中，因此维护的开销相对较小。然后对于MySQL这种依靠磁盘来完成数据的存储跟查询工作的，无法使用这种平衡二叉树。

随着数据库中数据的增加，索引本身大小随之增加，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级。可以想象一下一棵几百万节点的二叉树的深度是多少？如果将这么大深度的一颗二叉树放磁盘上，每读取一个节点，需要一次磁盘的I/O读取，整个查找的耗时显然是不能够接受的。那么如何减少查找过程中的I/O存取次数？

一种行之有效的解决方法是减少树的深度，将二叉树变为m叉树（多路搜索树），而B+Tree就是一种多路搜索树。

B+Tree

B+树和二叉树、平衡二叉树一样，都是经典的数据结构。B+树由B树（就是B-树）和索引顺序访问方法演化而来，但是在现实使用过程中几乎已经没有使用B树的情况了。其实也可以理解为B+树就是结合了平衡二叉树+二分查找法的精华。

B+树的定义在任何一本数据结构书中都能找到，其定义十分复杂，这里，精简地对B+树做个介绍：B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树，在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接。

其实理解B+Tree时，只需要理解其最重要的两个特征即可：

第一，所有的关键字（可以理解为数据）都存储在叶子节点（Leaf Page），非叶子节点（Index Page）并不存储真正的数据，所有记录节点都是按键值大小顺序存放在同一层叶子节点上。

第二，所有的叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。InnoDB B+Tree结构是在经典B+Tree的基础上进行了优化，增加了顺序访问指针，做这个优化的目的是为了提高区间访问的性能（下面详细说明）。

如下图，是一颗高度为2，每页可存放4条记录，扇区（fanout）为4，简化版的B+Tree。

所有记录都在叶子节点上，并且是顺序存放的，如果用户从最左边的叶子节点开始顺序遍历，可以得到所有键值的顺序排序：5、10、15、20、25、30、50、55、60、65、75、80、85、90。另外需要注意的是，B+树是无法根据某一个查找Key直接定位到value的。比如我们查找“30”这条记录，其只能通过B+树定位到“30”这条记录在这个页中，然后再通过二分查找法在这个页中来定位到具体的记录，只不过二分查找法的速度很快，基本忽略这个查询，但这个开销本身是存在的。另外，数据记录存储在页中，也同样有一定的组织方式来进行管理的，具体可以看InnoDB数据页相关文章。

那么怎么理解B+Tree这两个重要特征呢？MySQL将每个节点的大小设置为一个页的整数倍（原因下文会介绍），也就是在节点空间大小一定的情况下，每个节点可以存储更多的内结点，这样每个节点能索引的范围更大更精确。所有的叶子节点使用指针链接的好处是可以进行区间访问，比如上图中，如果查找大于20而小于30的记录，只需要找到节点20，就可以遍历指针依次找到25、30；只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。如果没有链接指针的话，就无法进行区间查找。这也是MySQL使用B+Tree作为索引存储结构的重要原因。

局部性原理与磁盘预读

MySQL为何将节点大小设置为页的整数倍，这就需要理解磁盘的存储原理。磁盘本身存取就比主存慢很多，在加上机械运动损耗（特别是普通的机械硬盘），磁盘的存取速度往往是主存的几百万分之一，为了尽量减少磁盘I/O，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存，预读的长度一般为页的整数倍。

这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用；程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

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

MySQL巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了读取一个节点只需一次I/O。假设B+Tree的高度为h，一次检索最多需要h-1I/O（根节点常驻内存），复杂度$O(h) = O(log_{M}N)$。实际应用场景中，M通常较大，常常超过100，因此树的高度一般都比较小，通常不超过2-4层。

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

总结一下B+树，B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接，也就可以利用二分查找法进行数据查找了，对于范围查询特别有优势。另外，B+Tree属于高扇区（fanout）性（大于100），简单说就是上层节点指向下层节点的指针数多，每一个指针可以称之为一个扇区。所以高扇区特性意味这棵树不会太高（一般2-4层最多），对应IO操作次数的减少。

五、B+Tree操作

最后简单了解下B+Tree节点的操作，在整体上对索引的维护有一个大概的了解，虽然索引可以大大提高查询效率，但维护索引仍要花费很大的代价，因此合理的创建索引也就尤为重要。

B+Tree的插入操作过程

B+树的插入必须保证插入后叶子节点中的记录依然排序，同时需要考虑插入到B+树的三种情况，每种情况都可能会导致不同的插入算法。如下表：

这里用一个例子来分析B+树的插入，例如，对于上图的那棵B+树，若用户插入28这个键值，发现当前Leaf Page和Index Page都没有满，直接进行插入即可。之后的下图：

接着再插入70这个键值，这时原先的Leaf Pge已经满了，但是Index Page还没有满。满足表中的第二种情况，这时插入Leaf Page后的情况为50、55、60、65、70，并根据中间的值60来拆分叶子节点，可得出下图：

（因为图片显示关系，没能在各个叶子节点加上双向链表指针，不过它是存在的）

最后插入键值95，这时符合表中讨论的第三种情况，即Leaf Page和Index Page都满了，这时需要做两次拆分，如下图：

可以看到，不管怎么变化，B+树总是会保持平衡。但是为了保持平衡对于新插入的键值可能需要做大量的拆分页（split）操作。因为B+树结构主要用于磁盘，页的拆分意味着磁盘的操作，索引应该在可能的情况下尽量减少页拆分的操作，因此，B+树同样提供了类似于平衡二叉树的旋转功能。旋转发生在Leaf Page已经满，但是其的左右兄弟节点没有满的情况下。这时B+树并不会急于去做拆分页的操作，而是将记录移到所在页的兄弟节点上。在通常情况下，左兄弟会被首先检查用来做旋转操作。

B+Tree的删除操作过程

B+树使用填充因子（fill factor）来控制树的删除变化。创建索引时，可以指定一个填充因子，以便在索引的每个叶级页上留出额外的间隙和保留一定百分比的空间，供将来表的数据存储容量进行扩充和减少页拆分的可能性。填充因子的值是从0到100的百分比数值，指定在创建索引后对数据页的填充比例。值为100时表示页将填满，所留出的存储空间量最小。只有当不会对数据进行更改时（例如，在只读表中）才会使用此设置。值越小则数据页上的空闲空间越大，这样可以减少在索引增长过程中对数据页进行拆分的需要，但需要更多的存储空间。当表中数据会发生更改时，这种设置更为适当。

填充因子越大，意味着一个索引页包含的索引记录越多，空闲空间越小。一般来说查询的效率越高，因为这样查询的时候，可以减少读取索引页的工作量和减少内存使用。但这样导致的结果是数据变动导致的索引维护的工作量增加，因为索引页的空闲空间小，如果不能在本页内完成索引调整，就会引起调整其他索引页。

所以一般的选择是，数据基本不变化的（例如OLAP的场景，数据只用来分析的），将填充因子设置到足够大,数据经常变化的（例如OLTP的场景），将填充因子设置为足够小。

B+树的删除操作同样必须保证删除后叶子节点中的记录依然排序，同插入一样，B+树的删除操作同样需要考虑以下表的三种情况，与插入不同的是，删除根据填充因子的变化来衡量。

六、计算不同高度的B+树能存储的数据量

在MySQL数据库中，表为索引组织表，也就是说B+树的叶子节点存储着一条以主键为key的完整记录，而非叶子节点（也可以称之为索引节点）存储的是（key, point指针），point是固定的6个字节大小，加上key大小及页头页尾大小，大概非叶子节点存储一个扇区信息为14字节。

索引页的大小默认为16K，当有什么的索引插入叶点时，该叶点至少会保留1/16的空闲空间，用于将来该叶点的索引更新或是插入。对于顺序写入的索引（无论是递增或是递减，顺序的就行），索引叶点可以达到15/16满。如果是随机的索引写入行为，叶点只会达到1/2到15/16满。当叶点填充在1/2以下满，或是被删除到1/2下满时，Innodb会缩短索引树，试图释放该叶点，该叶点可以被继续写入数据。

下面根据树的高度，从低到高分别计算能够存储的数量量（以主键索引来说）。下面提前给出了一些叶子节点一条记录的大小和非叶子节点存储一个扇区信息的大小。

树高度为：1

页大小为：16K

叶子节点记录大小：200字节

计算可存储记录：16 * 1024 / 200 = 81，这个值表示一个页可以存储的记录条数。

树高度为：2

页大小为：16K

叶子节点记录大小：200字节

非叶子节点记录大小：14字节

计算可存储记录：16 * 1024 / 14 = 1170，这个值表示一级非叶子节点（根页面）可以存储多少个页，也就是扇区数，一个扇区指向一个页。也就是说高度为2的B+树，大概可以存储 1170 * 81 = 94770 条记录。

树高度为：3

页大小为：16K

叶子节点记录大小：200字节

非叶子节点记录大小：14字节

计算可存储记录：16 * 1024 / 14 * 1170 = 1368900，这个值表示二级非叶子节点可以存储多少个页，也就是扇区数，一个扇区指向一个页。也就是说高度为3的B+树，大概可以存储 1368900 * 81 = 110880900条记录。

树高度为：4

页大小为：16K

叶子节点记录大小：200字节

非叶子节点记录大小：14字节

计算可存储记录：16 * 1024 / 14 * 1368900 = 1602004114，这个值表示三级非叶子节点可以存储多少个页，也就是扇区数，一个扇区指向一个页。也就是说高度为4的B+树，大概可以存储 1602004114 * 81 = 129762333234条记录。

总结来说，一个高度为4的B+树索引，可以存储千亿级别的数据量，所以一般情况下B+树的高度最高也就是2-4层。通过这个计算方式，也可以说明为什么B+树的扇区越高，其树也就越矮。B+树的高效也就体现在这里，从千万级别的表中查找数据，速度也是会非常快。

另外，我们上面的计算方式忽略了很多细节，只是为了求出一个大概值。比如高度为2的树，计算方式应该是 1170 * 81 + 81，因为叶子节点总是会比索引节点多一个页面。还有，我们算出的这都是理论值，在实际使用中，如果经常有删除操作，被删除的这个空间没那么快会被应用到，也有可能永远不会被应用到，这就是表空间碎片；并且InnoDB默认大概只使用一个页面的15K左右，其余的可能会用到，也可能不会用到。根据线上经验，通常来说，一个页70%空间会被使用到；所以可以拿上面的值乘以70%可能才是真正的存储量。

<参考>

MySQL索引背后的数据结构及算法原理

喜欢 (3)赏

[资助本站您就扫码 谢谢]

分享 (0)