数据库|面试官（MySQL 为什么用 B+ 树实现索引）索引|B+|Tree|mysql

MySQL 为什么用 B+ 树实现索引

索引概述
常见的索引模型
- 哈希表
- 有序数组
- 二叉查找树
- - 二叉查找树的查找操作
  - 二叉查找树的缺陷
  - 为什么索引不用二叉树实现
InnoDB 的索引模型
- B 树
- - B 树存在的问题
- B+ 树
- B 树和 B+ 树的区别
总结

索引对大家来说肯定不会陌生，不管是日常的开发还是面试中，都少不了索引的身影。
我们都会使用索引，但是我们对于索引的原理却是一知半解。本文就带大家深入学习一下 MySQL 的索引模型。
索引概述关于索引的定义，百度百科给出的解释是：

在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。

简单来说，索引是关系数据库中对某一列或多个列的值进行预排序的数据结构。通过使用索引，可以让数据库系统不必扫描整个表，而是直接定位到符合条件的记录，这样就大大加快了查询速度。
常见的索引模型通过前面，我们了解到，索引的本质是一种排好序的数据结构。其作用是为了提高数据查询的效率。
可以用于提高读写效率的数据结构很多，这里先介绍三种常见也比较简单的数据结构，它们分别是：哈希表、有序数组和二叉搜索树。
下面主要从使用的角度，简单分析一下三种模型的区别。
哈希表哈希表（又称散列表），是一种以键-值（key-value）存储数据的结构，我们只要输入待查找的键即 key，就可以找到其对应的值即 value。
哈希的底层是通过数组来保存值的，通过一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。
也就是说，通过映射函数（f(key)）将每一个关键码值都映射到哈希表中一个位置，通过关键码值来访问数据，以加快查找的速度（即O(n)）。
这个映射函数叫做散列函数，存放记录的数组叫做散列表。
不可避免的，多个 key 值经过哈希函数的换算，会出现同一个值得情况。即 f(key1)= f(key2) 且 key1 ≠ key2，对于这种情况称为哈希冲突，也叫哈希碰撞。
处理这种情况的一种方法是，拉出一个链表也叫拉链法。
假设，现在有一个维护着身份证信息和姓名的表，需要根据身份证号查找对应的名字，这时对应的哈希索引的示意图如下所示：

文章图片

图中，User2 和 User4 根据身份证号算出来的值都是 N，但没关系，后面还跟了一个链表。
这时候查 ID_card_n2 对应的名字是什么，处理步骤如下：

首先，将 ID_card_n2 通过哈希函数算出 N；
然后，按顺序遍历，找到 User2。

需要注意的是，图中 ID_card_n 的值并不是递增的，这样做的好处是增加新的 User 时速度会很快，只需要往后追加。
但缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的。
如果现在要找身份证号在[ID_card_X, ID_card_Y]这个区间的所有用户，就必须全部扫描一遍了。
所以，哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其它一些 NoSQL 引擎。
有序数组而有序数组在等值查询和范围查询场景中的性能都非常优秀。
还是上面这个根据身份证号查名字的例子，如果我们使用有序数组来实现的话，示意图如下所示：

文章图片

这里假设身份证号没有重复，这个数组就是按照身份证号递增的顺序保存的。
这时候如果要查 ID_card_n2 对应的名字，用二分法就可以快速得到，这个时间复杂度是 O(log(N))。
对于一个有序数组，对范围查找也十分友好，只需要找到起始元素即可。如果在知道元素下标的情况下，更新操作也非常快，对于删除操作，如果我们不考虑空洞的话（如果直接将对应下标处的元素置为 null，这样这块连续内存块中相当于有个空洞），删除操作也很快。
这么一分析，数组对查询、删除、更新操作的效率非常高，选数组作为 MySQL 索引的数据结构看起来似乎不错。
然而我们忽略了还有「插入操作」，如果我们要往数组中间插入一个数据，就必须得挪动后面所有的记录，要插入的数据越靠前，那么我们需要复制的数据就越多，成本太高。
所以，有序数组索引只适用于静态存储引擎，比如保存的是 2021 年某个城市的所有人口信息，这类不会再修改的数据。
因此，从插入数据这一角度来看，数组不太适合作为 MySQL 索引的数据结构。
二叉查找树二叉查找树（Binary Search Tree），也称为二叉搜索树、有序二叉树（Ordered Binary Tree）或排序二叉树（Sorted Binary Tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值
若任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值
任意节点的左、右子树也分别为二叉查找树
没有键值相等的节点

知识点：任意非空二叉查找树，左子节点值 < 根节点值；根节点值 < 右子节点值

文章图片

二叉查找树的查找操作
在二叉查找树中查找 N ：

首先从根节点开始，将根节点设置为当前节点，
若当前节点为空，则查找失败，
若 N 与当前节点值相等，返回当前节点，
若 N 大于当前节点值，则从当前节点的右子节点开始查找，否则从当前节点的左子节点开始查找，
直到返回目标节点或者查找失败。

对于二叉搜索树而言，它的查找操作的时间复杂度就是树的高度，最理想的情况下，也就是满二叉树的情况下，查找的时间复杂度为 O(logn)。

满二叉树：除最后一层无任何子节点外，每一层上的所有节点都有两个子节点的二叉树。

还是上面的例子，如果我们用二叉搜索树来实现的话，示意图如下所示：
如下图，要查 ID_card_n2 的话，按照图中的搜索顺序就是按照 UserA -> UserC -> UserF -> User2 这个路径得到，这个时间复杂度是 O(log(N))。

文章图片

二叉查找树的缺陷
当我们在不停地动态地往树中插入数据、删除数据时，在极端情况下，二叉搜索树可能退化成链表，它的查找时间复杂度就变成了 O(n)，性能不够稳定。如下图：

文章图片

为了维持O(log(N)) 的查询复杂度，就需要保持这棵树是平衡二叉树（AVL 树）。

平衡树是在二叉查找树的基础上，增加了一条限制，左右两个子树的高度差不能超过 1，左右两边相对平衡，因此称之为平衡树。

【数据库|面试官（MySQL 为什么用 B+ 树实现索引）】但是平衡二叉树在数据动态地删除、插入地过程中，为了维护平衡，避免树退化成链表，因此需要在删除或者插入数据后进行额外的旋转操作，会损耗一定的性能。
但整体来讲，它的查找、删除、插入、更新的复杂度均为O(log(N)) 。它的中序遍历，数据是有序的，因此也适合范围查找。但是它的缺点是，为了维护平衡，它的旋转操作过于复杂。
在平衡二叉树的基础上又出现了红黑树。
简单来说，红黑树是一种近似平衡（不完全平衡），节点非黑即红的树，它的树高最高不会超过 2log(n+1)，因此查找的时间复杂度为 O(logn)，无论是增删改查，它的性能都十分稳定。
工程上，很多地方都使用的是红黑树这种数据结构，例如 Java 中的 HashMap等。
为什么索引不用二叉树实现
无论二叉搜索树，还是 AVL 树，亦或是红黑树，它们都是二叉树的一种。
特点都是每个节点最多只有两个子节点，如果存储大量数据的话，那么树的高度会非常高。
二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树，其原因是，磁盘 IO。
MySQL 数据库的索引是存储在磁盘的。当数据量比较大的时候，索引的大小可能有几个 G，甚至更多。
当我们利用索引查询的时候，肯定不能全部加载到磁盘中的。能做的只有逐一加载磁盘页，这里的磁盘页对应的就是树的节点。如下图：

文章图片

如果树太高，每遍历一层节点时，就需要从磁盘读取一次数据，也就是发生一次 IO，如果数据在树高为 20 的地方，那查找一次数据就得发生 20 次 IO，如果树再高呢，这对应用程序简直就是灾难性的，耗时太长了。
因此二叉树在 MySQL 这种需要存储大量数据的场景下，是不适合当做索引的数据结构的，因为树太高，操作数据时会发生多次磁盘 IO，性能太差。
为了让一个查询尽量少地读取磁盘，就必须让查询过程访问尽量少的数据块。
树可以有二叉，也可以有多叉。多叉树就是每个节点有多个子节点，子节点之间的大小保证从左到右递增。
那么我们就不应该使用二叉树，而是要使用「N叉」树，这里「N叉」树中的 N 取决于数据块的大小。
N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。
在 MySQL 中，索引是在存储引擎层实现的（事务也是引擎层面实现的），所以并没有统一的索引标准，即不同存储引擎的索引的工作方式并不一样。
而即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。
由于 InnoDB 存储引擎在 MySQL 数据库中使用最为广泛，所以下面就以 InnoDB 为例，分析一下其中的索引模型。
InnoDB 的索引模型在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。
InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的。每一个索引在 InnoDB 里面对应一颗 B+ 树。
分析 B+ 树之前，我们先了解一下 B 树。
B 树 B 树（B-tree），有翻译成「B减树」的，其实是错误的，中间的横线不是减号。可能因为 B+树所以会导致这样的误解，实际上并没有「B减树」这个概念。
B 树是一种多路平衡查找树，它的每一个节点最多包含 k 个孩子，k 就是 B树的阶。k的大小取决于磁盘页的大小。

阶数表示此树的节点最多有多少个孩子节点（子树），一般用字母 M 表示阶数。

一棵 m阶的 B 树的特性如下：

如果根节点不是叶子节点，那么它至少有两个子节点；
每一个中间节点（非叶子节点，非根节点）最多有 m 个子节点；
每一个中间节点最少有ceil(m/2)个子节点；
有 k 个子节点的非叶子节点拥有 k ? 1 个元素，其中 m/2 <= k <= m；
所有的叶子节点都在同一层；
每个节点中的元素从小到大排列，节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域分划。

文章图片

如上图所示：

这是一棵 3 阶的 B树。
根节点有两个孩子 (2 6) 和 12；
我们来看 (2 6)节点，该节点有两个元素 2 和 6，有三个孩子：1、（3 5）、8；其中 1 小于元素 2，8 大于 3、5。

B 树把树的节点关键字增多后，树的层级比原来二叉树的层级少了，这样就可以减少数据查找的次数，也就是减少了 IO 次数，提高了查询性能。
B 树存在的问题
B 树相比二叉树虽好，但还是存在以下问题：

每个节点中既要存索引信息，又要存其对应的数据，如果数据很大，那么当树的体量很大时，每次读到内存中的树的信息就会不太够。
B 树遍历整个树的过程和二叉树本质上是一样的，B 树相对二叉树虽然提高了磁盘 IO 性能，但并没有解决遍历元素效率低下的问题。

针对以上两个问题，B+ 树诞生了。
B+ 树 B+ 树和 B 树类似，但多了几条规则。
一棵 m 阶的 B+树具有如下几个特征：

有 k 个子树的中间节点包含有 k 个元素（B树中是 k-1 个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
所有的叶子节点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。
所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

文章图片

解释一下：
首先，每一个父节点的元素都出现在子节点中，是子节点最大（最小的元素）。
比如 8 和 15：

文章图片

根节点中最大的元素，同时也是整树最大的元素，以后无论插入多少数据，始终要保证最大元素在根节点中。
至于叶子节点，由于父节点的元素都出现在子节点，因此所有叶子节点包含了全量的元素信息。并且每一个叶子节点，都带有指向下一个节点的指针，形成了一个有序链表。
B 树和 B+ 树的区别 1、卫星数据的位置不同：卫星数据指的是索引元素指向的记录。比如数据库中的某一行。在B 树中，无论是中间节点还是叶子节点都带有卫星数据。

文章图片

而在 B+ 树中，只有叶子节点带有卫星数据，其余中间节点仅仅是索引，没有任何数据关联。
这样，整个树的每个节点所占的内存空间就变小了，读到内存中的索引信息就会更多一些，相当于减少了磁盘 IO 次数。

文章图片

需要补充的是，在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。

2、B+ 树的范围查询更加方便：由 B 树的性质可以得到，所有叶子节点都会在同一层，B+树会以一个链表的形式将所有叶子节点的信息全部串联起来。
B+ 树叶子节点两两相连可大大增加区间访问性，可使用在范围查询等，而 B 树每个节点 key 和 data 在一起，则无法区间查找。
总结本文我们分析了几个常见的索引模型：

哈希表：适用于等值查询，缺点是区间查询效率慢；
有序数组：数组对查询（等值查询、区间查询）、删除、更新操作的效率非常高，但是对于插入操作效率低下，原因是涉及元素后移；
二叉搜索树：极端情况下，二叉搜索树可能退化成链表，性能不够稳定。

我们又分析了 B 树和 B+ 树的区别，以及为什么要用 B+ 树作为 MySQL 索引的数据结构。
主要是因为 B+ 树中只有叶子节点才会存放索引值和数据，非叶子节点只会存放索引值。
因此对于非叶子节点，一个节点中，B+ 树存放的索引值数量会远远大于 B 树（因为一个节点的空间是有限的，B 树要存放索引+数据，而 B+ 树只需要存放索引）。这样就导致了每个节点中，B+ 树能向下分出更多的叉，子节点数更多。
那么在要存储同样大小的数据文件的场景下，用 B+ 树存储，最终树的高度会远远小于用 B 树存储的高度。
所以使用 B+ 树作为 MySQL 索引的数据结构，将来在读取数据时，发生的磁盘 IO 次数会更少，性能更优，因此最终 MySQL 索引的数据结构使用的是 B+ 树。