InnoDB存储引擎为什么选择B+树构建索引

╰半夏微凉° 2023-02-19 15:26 60阅读 0赞

索引是对数据库表中一个或多个列的值进行排序的数据结构，以协助快速查询、更新数据库表中数据。在MySQL中，索引是在存储引擎层实现的，所以并没有统一的索引标准，即不同存储引擎的索引的工作方式并不一样。而即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。索引加速了数据访问，因为存储引擎不会再去扫描整张表得到需要的数据；相反，它从根节点开始，根节点保存了子节点的指针，存储引擎会根据指针快速寻找数据。

索引在 MySQL 数据库中分三类：

*  B+树索引
 *  Hash索引
 *  全文索引

我们在工作开发中最常接触到的是InnoDB存储引擎中的B+树索引。在InnoDB中，每一张表其实就是多个B+树，即一个主键索引树和多个非主键索引树。 执行查询的效率：使用主键索引 > 使用非主键索引 > 不使用索引。如果不使用索引进行查询，则从主键索引B+树的叶子节点进行遍历。

要了解 B+树索引，就不得不提二叉查找树、B树这两种数据结构。B+树就是由它们演化来的。

## 二叉查找树 ##

对一张表建立二叉查找树索引的示意图如下：

![20200621201333886.png][]

二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。顶端的节点我们称为根节点，没有子节点的节点我们称之为叶节点。查找的时间复杂度是 O(logN)。如上图，利用二叉查找树最多只需要3次即可找到匹配的数据。如果在表中一条条的查找的话，最多需要6次才能找到。虽然利用二叉查找树查找性能很高，但它不足以支持按照区间快速查找数据。

为了让二叉查找树支持按照区间来查找数据，我们可以对它进行这样的改造：树中的节点并不存储数据本身，而是只是作为索引。除此之外，我们把每个叶子节点串在一条链表上，链表中的数据是从小到大有序的。经过改造之后的二叉树如下图所示。

![20200621201916951.png][]

改造之后，如果我们要寻找某个区间的数据。我们只需要拿区间的起始值，在树中进行查找，当查找到某个叶子节点之后，我们再顺着链表往后遍历，直到链表中的结点数据值大于区间的终止值为止。所有遍历到的数据，就是符合区间值的所有数据。

如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是一个磁盘块。二叉查找树每个节点只存储一个键值和数据的。说明每个磁盘块仅仅存储一个键值和数据！但是，我们要为几千万、上亿的数据构建索引，如果将索引存储在内存中，尽管内存访问的速度非常快，查询的效率非常高，但是，占用的内存会非常多。比如，我们给1亿个数据构建二叉查找树索引，那索引中会包含大约1亿个节点，每个节点假设占用16个字节，那就需要大约1GB的内存空间。给一张表建立索引，我们需要1GB的内存空间。如果我们要给10张表建立索引，那对内存的需求是无法满足的。如何解决这个索引占用太多内存的问题呢？

可以借助时间换空间的思路，把索引存储在硬盘中，而非内存中。我们都知道，硬盘是一个非常慢速的存储设备。通常内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的。读取同样大小的数据，从磁盘中读取花费的时间，是从内存中读取所花费时间的上万倍，甚至几十万倍。这种将索引存储在硬盘中的方案，尽管减少了内存消耗，但是在数据查找的过程中，需要读取磁盘中的索引，因此数据查询效率就相应降低很多。

二叉查找树经过改造之后，支持区间查找的功能就实现了。不过，为了节省内存，如果把树存储在硬盘中，那么每个节点的读取（或者访问），都对应一次磁盘IO操作。树的高度就等于每次查询数据时磁盘IO操作的次数。我们前面讲到，比起内存读写操作，磁盘IO操作非常耗时，所以我们优化的重点就是尽量减少磁盘IO操作，也就是，尽量降低树的高度。那如何降低树的高度呢？

## B树 ##

如果我们把索引构建成m叉树，高度是不是比二叉树要小呢？如图所示，给16个数据构建二叉树索引，树的高度是4，查找一个数据，就需要4个磁盘IO操作（如果根节点存储在内存中，其他节点存储在磁盘中），如果对16 个数据构建五叉树索引，那高度只有2，查找一个数据，对应只需要2次磁盘操作。如果m叉树中的m是100，那对一亿个数据构建索引，树的高度也只是3，最多只要3次磁盘IO就能获取到数据。磁盘IO变少了，查找数据的效率也就提高了。

![2020062120250468.png][] ![20200621202515125.png][]

为了解决二叉查找树的一个节点只能存储一个键值和数据的弊端，我们应该寻找一种单个节点可以存储多个键值和数据的搜索树，B树就是这样一种平衡的多路查找树，下图即是一棵B树：

![20200621203200873.png][]

上图中的p节点为指向子节点的指针，二叉查找树其实也有，只是图里省略了。上图中的每个节点称为页，页就是我们上面说的磁盘块，在MySQL中数据读取的基本单位都是页，所以我们这里叫做页更符合MySQL中索引的底层数据结构。

从上图可以看出，B树相对于二叉查找树，每个节点存储了更多的键值（key）和数据（data），并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的B树是3阶B树，高度也会很低。基于这个特性，B树查找数据读取磁盘的次数将会很少，数据的查找效率也会比二叉查找树高很多。

B树为什么要设计成多路？为了进一步降低树的高度，路数越多树的高度越低，如果设计成无限多路就退化成有序数组了。

B树的使用场景决定了它的设计。B树经常用做文件系统的索引，为什么文件系统的索引喜欢用B树而不是红黑树或有序数组呢？文件系统或数据库的索引都是在硬盘上的，如果数据量很大的话，索引树不一定能一次性加载到内存中，如果一棵树根本无法一次性加载进内存，该如何利用它作查找？此时B树多路的威力就体现出来了，可以每次只加载B树的一个节点，然后一步步往下找。如果整棵树的完整结构都在内存中，那么红黑树当然比B树效率高，但是当树大到不能完整加载进内存要涉及到磁盘IO时，B树就更优了。比起内存读写操作，磁盘IO操作非常耗时，所以我们优化的重点就是尽量减少磁盘IO操作，也就是，尽量降低树的高度。

## B+树 ##

了解了B树后再来了解下它的变形版：B+树，它比B树的查询性能更高。B+树由B树改良而来，属于改良版的多路平衡查找树。下图就是一棵B+树。

![2049f119228d4f05b644e9b67cad7bce.png][]

B+树是在B树基础上改造的，用作数据库的索引，它的数据都在叶子结点并且叶子结点之间还加了指针形成链表，为什么要这样设计？B+树的根节点和非叶子节点中都不会存储数据，只有叶子节点才存储数据。排除索引覆盖的场景，搜索到关键字不会直接返回，会到最后一层的叶子节点去拿数据。B+树的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表的结构。

B+树是由B树改进而来的，所以B树能解决的问题，B+树都能解决，那么B+树能解决哪些B树所不能解决的问题呢？

1.  扫库、扫表能力更强：如果我们要对表进行全表扫描，只需要遍历叶子节点就可以 了，不需要遍历整棵B+树
2.  B+树的磁盘读写能力相对于B树来说更强：根节点和非叶子节点不保存数据区， 所以一个节点可以保存更多的关键字，一次磁盘加载(IO操作)能获取到相对更多的关键字
3.  天然具备排序能力：叶子节点上有下一个数据区的指针，数据形成了链表
4.  效率稳定：B+树永远是在叶子节点拿到数据，所以IO次数是稳定的，而B树运气好的话根节点就能拿到数据，运气不好就要到叶子节点才能拿到数据，所花费的时间会有差异。

使用场景决定设计，B+树经常用作数据库的索引，数据库中的select操作并不是只返回一条数据而是多条。如果用B树的话，可能需要跨层访问，而B+树由于所有数据都在叶子结点，不用跨层，同时链表有序只要找到首尾，就可以定位到所有符合条件的数据。这就是B+树比B树更优的地方。

Hash更快，为什么数据库还用B+树作索引？与业务场景有关，如果只选一个数据，hash确实更快，但是select经常要选择多条，这时由于B+树索引有序并且又有链表相连，它的查询效率比hash更快。而且数据库的索引是存储在磁盘上的，数据量大的情况下无法一次性装入内存，B+树的多路设计可以允许索引数据分批加载到内存，树的高度也很低，提高查找效率。

## 索引实例 ##

每一个索引在InnoDB里面对应一棵B+树。

假设，我们有一个主键列为ID的表，表中有字段k，并且在k上建立普通索引。建立这张表并插入一些数据。

create table test(
    	id int primary key, 
    	k int not null, 
    	name varchar(16),
    	index (k)
    )engine=InnoDB;
    
    insert into test (id,k) values (100,1),(200,2),(300,3),(500,5),(600,6);

这张表的两棵索引B+树的示例示意图如下：

![20210330114441104.png][]

从图中不难看出，根据叶子节点的内容，索引类型分为主键索引和非主键索引。主键索引的叶子节点存的是整行数据的地址。在InnoDB里，主键索引也被称为聚簇索引（clustered index）。非主键索引的叶子节点内容是主键的值。在InnoDB里，非主键索引也被称为二级索引（secondary index）。那么基于主键索引和普通索引的查询有什么区别呢。

*  如果语句是 select \* from test where id=500，即主键查询方式，则只需要搜索id这棵B+树；
 *  如果语句是select \* from test where k=5，即普通索引查询方式，则需要先搜索k索引树，得到id的值为500，再到id索引树搜索一次。这个过程称为回表。

也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

## 索引维护 ##

B+树为了维护索引有序性，在插入新值的时候需要做必要的维护。以上面这个图为例，如果插入新的行id值为700，则只需要在R5的记录后面插入一个新记录。如果新插入的id值为400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。

![20210330133755925.png][]

而更糟的情况是，如果R5所在的数据页已经满了，根据B+树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约50%。

当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。

看到这里，终于理解了为什么建表规范里面要求建表语句里一定要有自增主键，就是为了避免页分裂。自增主键的插入数据模式，正符合了前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。如果使用带业务逻辑的字段做主键（例如身份证号），则往往不容易保证有序插入，这样写数据成本相对较高。

[20200621201333886.png]: https://img-blog.csdnimg.cn/20200621201333886.png
[20200621201916951.png]: https://img-blog.csdnimg.cn/20200621201916951.png
[2020062120250468.png]: https://img-blog.csdnimg.cn/2020062120250468.png
[20200621202515125.png]: https://img-blog.csdnimg.cn/20200621202515125.png
[20200621203200873.png]: https://img-blog.csdnimg.cn/20200621203200873.png
[2049f119228d4f05b644e9b67cad7bce.png]: https://img-blog.csdnimg.cn/2049f119228d4f05b644e9b67cad7bce.png
[20210330114441104.png]: https://img-blog.csdnimg.cn/20210330114441104.png
[20210330133755925.png]: https://img-blog.csdnimg.cn/20210330133755925.png