为什么选择使用 B+ 树作为 MySQL 数据库索引？

之前MySQL数据库索引为什么选择使用B+树，相信很多朋友对于数据结构中的树还有些模糊，所以我们将由浅入深一步步探索树的发展过程，并介绍B树以及为什么选择使用B+树作为MySQL数据库索引！

学过数据结构的人一般都熟悉最基本的树，所以我们就从二叉搜索树开始，这和我们的主题比较相似。

1。二叉搜索树

（1）二叉树简介：

二叉搜索树又称有序二叉搜索树，满足二叉搜索树的一般性质。这意味着空树具有以下属性：

1。如果没有左子树节点为空，则左子树的值小于根节点的值；

2。没有节点真子树为空，则真子树所有值的值都大于根节点的值；

3。任意节点的左右子树也是二叉搜索树；

4。不存在具有相同键值的节点；

上图是一个普通的二叉搜索树，可以按照遍历方法从小到大按照顺序：2、3、5、6、7、8进行排序列出。

搜索上面的二叉树。例如，如果要查找键值为 5 的记录，请先查找根。它的键值为6，并且6大于5。所以如果你搜索6的左子树，你会找到3；如果5大于3，则找到正确的子树；我一共找到了3次。如果对同一个请求按照2、3、5、6、7、8的顺序搜索3次。同理，找到键值为8的记录。这次需要3次搜索，而顺序搜索需要6x 。计算平均搜索次数：顺序搜索平均搜索次数为(1+2+3+4+5+6)/6 = 3.3次，二叉搜索树平均搜索次数为(3+3 +3+2+2+1)/6=2.3倍。二叉搜索树的平均搜索速度比顺序搜索快。

(2) 局限性和应用

二叉搜索树由n个节点随机组成。因此，在某些情况下，二叉搜索树会退化为具有 n 个节点的线性链。如下图：

大家看上图。如果我们选择的根节点是最小或最大的数，那么二叉搜索树就完全退化为线性结构。上图中平均搜索次数为(1+2+3+4+5+5)/6=3.16次，与顺序搜索类似。显然，这棵二叉树的查询效率是很低的，所以如果你想创建一个性能最高的二叉搜索树，就需要这棵二叉树保持平衡（这里的平衡可以从一个显着的属性看出，即这棵树比上一棵高）损失的高度肯定更大，这在同一个节点的情况下是不平衡的），这就引出了一个新的定义——平衡AVL二叉树。

2. AVL 树

(1)简介

AVL 树是一种具有平衡条件的二叉搜索树。一般用平衡系数差来判断是否平衡以及是否通过旋转达到平衡。左右子树树 高度不超过1。与红黑树相比，它是严格平衡的二叉树。必须满足平衡条件（所有节点左右子树高度差不超过1）。无论我们执行插入还是删除操作，如果不满足上述条件，我们就需要保持旋转平衡，而旋转是非常耗时的。由此可知，AVL树适合插入和删除，时间相对较少，但会搜索很多情况。

上面是一个普通的平衡二叉树。从图中我们可以看出，任意节点左右子树的平衡因子之差都不会大于1。

(2) 约束

因为维持这种高度平衡的成本为大于从中获得的效率增益，实际应用并不多。更多的地方都是当地人出没，而不是整体上非常严格。平衡红黑树。当然，如果应用场景不需要频繁的插入和删除，而只是有较高的搜索要求，那么AVL还是比红黑树更好。 ？一个存储位代表节点的颜色，可以是红色或黑色。通过限制任何根到叶路径上每个节点的着色方式，红黑树可确保没有路径的长度是其他路径的两倍。是一棵弱平衡二叉树（因为是平衡的，所以可以推断对于同一节点来说AVL树的高度低于红黑树）。与严格的AVL树相比，它的转数会减少。因此，当查找、插入、删除操作较多时，我们使用红黑树。

(2) 特点

1.每个节点要么是红色，要么是黑色；
2.根节点为黑色；
3、每个叶子节点（叶子节点是树尾的NULL指针或者NULL节点）全黑；
4. 如果一个节点是红色的，那么它的两个儿子是黑色的；
5.对于任何节点，每个指向叶子点树的NULL指针每条路径都包含相同数量的黑色节点；
6. 每条路径包含相同的黑色节点；

(3) 应用

1.在STL C++中广泛使用，map和set都是使用红黑树实现的；
2.著名的Linux进程调度器Completely Fair Scheduler使用红黑树来管理进程控制块。进程的虚拟内存区域存储在红黑树中，虚拟地址All的每个区域对应红黑树中的一个节点。左指针指向连续的虚拟地址存储区域，右指针指向连续的高地址虚拟地址空间；
3、IO复用epoll的实现采用红黑树组织管理sockfd，支持快速增删改查；
4. Nginx 中使用红黑树来管理定时器。由于红黑树排列，可以快速获取当前距离最小的定时器；
5、TreeMap的Java实现；

4。 B/B+树

说到上面三棵树：二叉查找树、AVL和红黑树，似乎我们还没有弄清楚为什么MySQL使用B+树作为索引实现，别着急，咱们首先讨论一下，什么是B树。

(1)简介

我们MySQL中的数据一般都位于磁盘上。读取数据时肯定会有磁盘访问操作。一个圆盘中有两个机械运动部件，即圆盘。该部件旋转并且磁臂移动。磁盘旋转是我们市场上所说的每分钟转数，而磁盘移动是磁盘旋转到指定位置然后移动磁臂开始读写数据。接下来是在磁盘上定位块的过程，定位是磁盘访问中相当耗时的部分。机械机芯比电子机芯需要更长的时间。当大规模数据存储在磁盘上时，定位显然是一个非常耗时的过程，但是我们可以通过B树进行优化，以提高从磁盘读取时的定位效率。

为什么B类树可以优化？我们可以根据B类树的特点，构建多级B类树，然后在尽可能多的节点上存储相关信息，保证层数尽可能少，以便我们查找信息快点。之后。磁盘 另外，I/O 操作较少，B 类树是平衡树。每个节点到叶子节点的高度是相同的，这也保证了每次查询都是稳定的。

总的来说，B/B+树是为磁盘或其他存储设备设计的平衡多路径搜索树（与二叉树相比，B树每个内部节点的分支更多），红黑相比较相同节点的树是B/B+树的高度比红黑树的高度小很多（下面B/B+树性能分析中提到）。 B/B+树上的操作时间通常由两部分组成：磁盘访问时间和CPU计算时间。 CPU的速度很快，所以B树的运行效率取决于磁盘访问次数和关键字总数是一样的。较低B树的高度越小，磁盘I/O花费的时间越少。

请注意，B 树就是 B 树 - 它只是一个符号。

(2) B 树的性质

1.定义任意非叶子节点至多有M个儿子且M>2；
2、根节点的子节点数量为[2, M]；
3、除根节点外的非叶子节点的后代数量为[M/2，M]；
4、每个节点至少存储M/2-1（向上取整），最多M -1个关键字； （至少2个关键字）
5.非叶子节点的关键字数量=子节点的指针数量-1；
6.非叶子节点的关键字：K[1], K[2], …, K[M-1]；且 K[i] 7.非叶子节点的指针：P[1]，P[2]，…，P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其他P[i]指向属于子树的关键字来自 (K[i-1], K[i]);
8.所有叶子节点都在同一级别；

这只是一个简单的 B 树。在实践B中，树的节点中有很多关键字。比如上图中，节点35、35代表key（索引），小黑块代表key指向的内容在内存中的实际存储位置，是一个指针。

5。 B+树

（一）简介

B+树是应文件系统的需要而生成的一种变形的B树（文件目录有一级索引，只有最底层的叶子节点（文件）存储data）非叶子节点只存储索引，不存储实际数据。所有数据都存储在叶节点中。不是在寻找文件系统文件吗？

举个文件查找的例子：有3个文件夹a、b、c，a包含b，b包含c，文件yang.c，a，b，c是索引（存储在非叶子节点）， a、b、c仅能找到.c键，实际的yang.c数据存储在叶子节点中。

所有非叶子节点都可以被认为是索引部分！

(2) B+树的性质（以下是与B树不同的性质）

1.子树指向非叶子节点的指针与关键字的数量相同；
2.非叶子节点子树指针p[i]节点指向Key值属于[k[i],k[i+1]]的子树。 （B树是开区间，意思是B树不允许关键字重复，B+树允许重复）；
3.为所有叶子节点添加链接指针；
4.所有关键字都出现在叶子节点中（密集索引）。 （并且链表中的关键字恰好是有序的）；
5、非叶子节点相当于叶子节点的索引（稀疏索引），叶子节点相当于存储数据（关键字）的数据层；
6.更适合文件系统；

非叶子节点（例如5、28、65）只是一个键（索引），叶子节点（5、8、9）上存储的实际数据是实际数据或者指向实际数据。

(3) 应用

1. B树和B+树主要应用于文件系统和索引数据库如MySQL；

6。 B/B+ 树性能分析

n 个节点的平衡二叉树 高度为 H（即 logn），n 个节点的 B/B+ 树的高度为 logt((n+1)/2)+ 1；

如果要使用 B 树作为内存中查找表，它并不一定比平衡二叉树更好，尤其是当 m 很大时。由于B树搜索操作的CPU时间为O(mlogtn)=O(lgn(m/lgt))且m/lgt>1；所以当m很大时，O(mlogtn)比平衡二叉树的运行时间长。多得多。因此，使用内存B树时m必须较小。 （通常取最小值m=3。此时，B树中的每个内部节点可以有2或3个子节点。这种三阶B树称为2-3树）。

7。为什么 B+ 树比 B 树更适合为数据库建立索引？

1。 B+树磁盘读写成本更低：B+树内部节点没有指向特定关键字信息的指针，因此其内部节点比B树小。如果内部节点的关键字存储在同一个磁盘块中，磁盘块能容纳的关键字越多，一次读入内存时需要查找的关键字就越多，读写IO次数相对减少。 。

2、B+树查询性能更稳定：因为非端点并不是最终指向文件内容的节点，而只是节点叶子中关键字的索引。因此，任何关键字搜索都必须遵循从根节点到结束节点的路径。所有关键字查询的路径长度相同，导致所有数据的查询效率相同。

3。由于B+树数据存储在叶子节点，分支节点都是索引，所以扫描数据库很方便。叶子节点只需要扫描一次，但B树还存储分支节点。数据，如果我们想要查找特定的数据，我们需要进行中序遍历来按顺序扫描，因此B+树更适合区间查询，因此B+树通常用于数据库索引。

PS：我在知乎上看到有人这样说，我觉得很有道理：

他认为数据库索引使用B+树的主要原因是B树提高了IO性能，但没有解决传递时效率低的问题要素。 B+树应用正是为了解决这个问题而诞生的。 B+树只需要遍历叶子节点即可实现整棵树的遍历。另外，基于范围的查询在数据库中非常常见，而B树不支持此类操作或者效率太低。

参考文章：

1。 http://blog.csdn.net/whoamiyang/article/details/51926985
2. https://www.cnblogs.com/George1994/p/7008732.html
3.