MYSQL索引为啥要用B+树储存数据呢

心已赠人 2023-10-13 12:23 12阅读 0赞

首先我们来分析一下需求

## MYSQL索引需要怎样的数据结构 ##

为了防止数据因为特(duan)殊(kai)情(dian)况(yuan)丢失,我们的数据肯定是要持久化的,也就是保存在硬件(磁盘)里面,而我们知道 磁盘相对于内存来讲 速度要慢了几万倍 甚至即使万倍 所以我们必须减少磁盘的I/O操作

再有呢 我们知道MYSQL是支持单个查询和范围查询的 所以这个数据结构也需要单个查询和范围查询

所以总结一下 MYSQL数据结构需要

1.I/O操作尽可能少

2.支持高效的单个查询和范围查询

## 遍历 ##

最暴力的方法肯定是遍历所有数据 很显然不行

## 二分查找 ##

索引储存都是有序的 所以我们想到了二分查找(二分法不懂可以百度下 都有) 从遍历的O(n)时间复杂度减小到了O(logn)

不过这种一维的方法的插入非常麻烦 我们一旦插入或者删除数据 就要把它之后的所有数据往后移动一位....

## 二分查找树 ##

为了解决插入费劲的问题 引入了二分查找**树**

![a92868e6a48e44efa8b35366b20b84e6.png][]

我们把每个二分的节点往上拉 变成了一个树状结构

![359b24c40bfa4e1299116149fac4924d.png][]

这个二分查找树的性质是 一个根节点总之比它的全部左节点大比他的全部右节点小

我们来看一下二分数组查找和二分数查找的对比 查7

二分数组 先取中间4 然后7>4 所以往右看 再去部分的中间 6 7>6 再往右看 找到了

二分查找树 4->6->7

他俩本质上是一样的

但是插入就不一样了

我们想插个3.5进去 二分数组的话 就得找到3和4之间的位置 然后把4567往后移动 然后再放进去

二分查找树 贼方便了就 直接大于3 小于4是吧 我直接给你挂3底下

太好了 这直接用二分查找树 无敌了

啊不行 假如我们还是用这个树举例 我再插入3.51 3.52 3.53 3.54 3.55.............(此处省略一万个数据)

3.5在挂在3底下 3.51挂在3.5下面 3.52挂在3.51底下............

它就会一直在3右边的分支垒上去 一直插的话 就退化成链表了

由于树是存储在磁盘中的，访问每个节点，都对应一次磁盘 I/O 操作（*假设一个节点的大小「小于」操作系统的最小读写单位块的大小*），也就是说**树的高度就等于每次查询数据时磁盘 IO 操作的次数**，所以树的高度越高，就会影响查询性能。

二叉查找树由于存在退化成链表的可能性，会使得查询操作的时间复杂度从 O(logn) 升为 O(n)。

而且会随着插入的元素越多，树的高度也变高，意味着需要磁盘 IO 操作的次数就越多，这样导致查询性能严重下降，再加上不能范围查询，所以不适合作为数据库的索引结构。

## 自平衡二叉树 ##

为了解决二叉查找树会在极端情况下退化成链表的问题，后面就有人提出**平衡二叉查找树（AVL 树）**。

主要是在二叉查找树的基础上增加了一些条件约束：**每个节点的左子树和右子树的高度差不能超过 1**。也就是说节点的左子树和右子树仍然为平衡二叉树，这样查询操作的时间复杂度就会一直维持在 O(logn) 。(通过左选右选操作维持左树右树平衡性 原理较复杂不在这里深究)

不过呢即使是平衡二叉查找树，也会随着插入的元素增多，而导致树的高度变高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。

但是我们也有一点改进的思路 二叉树高度比较高 那么三叉树就可以有效的降低高度 那多叉树还会远吗

### B 树 ###

为了解决降低树的高度的问题，后面就出来了 B 树，它不再限制一个节点就只能有 2 个子节点，而是允许 M 个子节点 (M>2)，从而降低树的高度。

B 树的每一个节点最多可以包括 M 个子节点，M 称为 B 树的阶，所以 B 树就是一个多叉树。

假设 M = 3，那么就是一棵 3 阶的 B 树，特点就是每个节点最多有 2 个（M-1个）数据和最多有 3 个（M个）子节点，超过这些要求的话，就会分裂节点,like this

![91731af63f87499994a2236f6fcd2148.gif][]

我们来看一下三阶B树

![a64ea3005f9e4ab7b2e0e1d714e7f370.gif][]

假设我们在上图一棵 3 阶的 B 树中要查找的索引值是 9 的记录那么步骤可以分为以下几步：

1.  与根节点的索引(4，8）进行比较，9 大于 8，那么往右边的子节点走；
2.  然后该子节点的索引为（10，12），因为 9 小于 10，所以会往该节点的左边子节点走；
3.  走到索引为9的节点，然后我们找到了索引值 9 的节点。

可以看到，一棵 3 阶的 B 树在查询叶子节点中的数据时，由于树的高度是 3 ，所以在查询过程中会发生 3 次磁盘 I/O 操作。

而如果同样的节点数量在平衡二叉树的场景下，树的高度就会很高，意味着磁盘 I/O 操作会更多。所以，B 树在数据查询中比平衡二叉树效率要高。

但是 B 树的每个节点都包含数据（索引+记录），而用户的记录数据的大小很有可能远远超过了索引数据，这就需要花费更多的磁盘 I/O 操作次数来读到「有用的索引数据」。

而且，在我们查询位于底层的某个节点（比如 A 记录）过程中，「非 A 记录节点」里的记录数据会从磁盘加载到内存，但是这些记录数据是没用的，我们只是想读取这些节点的索引数据来做比较查询，而「非 A 记录节点」里的记录数据对我们是没用的，这样不仅增多磁盘 I/O 操作次数，也占用内存资源。

另外，如果使用 B 树来做范围查询的话，需要使用中序遍历，这会涉及多个节点的磁盘 I/O 问题，从而导致整体速度下降

## B+树 ##

这一眼就知道这是B树的升级强化版 那么它是怎么进行升级的呢

![830d72d3ac71424182df08e5bcc1f382.png][]

B+ 树与 B 树差异的点，主要是以下这几点：

*  叶子节点（最底部的节点）才会存放实际数据（索引+记录），非叶子节点只会存放索引；
 *  所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；
 *  非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大（或最小）。
 *  非叶子节点中有多少个子节点，就有多少个索引；

可以看到每个父节点就会把叶节点分成几份方便查询 这样分下去其实还是保留了一部分最开始的二分思想的

哎你说人这脑瓜子咋长的呢 我看人家的解析理解都费劲 咋创造出来的呢

#### 单点查询 ####

B 树进行单个索引查询时，最快可以在 O(1) 的时间代价内就查到，而从平均时间代价来看，会比 B+ 树稍快一些。

但是 B 树的查询波动会比较大，因为每个节点即存索引又存记录，所以有时候访问到了非叶子节点就可以找到索引，而有时需要访问到叶子节点才能找到索引。

**B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O次数会更少**。

#### 插入和删除效率 ####

B+ 树有大量的冗余节点，这样使得删除一个节点的时候，可以直接从叶子节点中删除，甚至可以不动非叶子节点，这样删除非常快，

但是B树删除一个节点却非常麻烦,删掉一个节点可能导致整个树形的变化

因此B+的删除 插入效率较高

#### 范围查询 ####

B 树和 B+ 树等值查询原理基本一致，先从根节点查找，然后对比目标数据的范围，最后递归的进入子节点查找。

因为 **B+ 树所有叶子节点间还有一个链表进行连接，这种设计对范围查找非常有帮助**，比如说我们想知道 12 月 1 日和 12 月 12 日之间的订单，这个时候可以先查找到 12 月 1 日所在的叶子节点，然后利用链表向右遍历，直到找到 12 月12 日的节点，这样就不需要从根节点查询了，进一步节省查询需要的时间。

而 B 树没有将所有叶子节点用链表串联起来的结构，因此只能通过树的遍历来完成范围查询，这会涉及多个节点的磁盘 I/O 操作，范围查询效率不如 B+ 树。

因此，存在大量范围检索的场景，适合使用 B+树，比如数据库。而对于大量的单个索引查询的场景，可以考虑 B 树，比如 nosql 的MongoDB

##  ##

[a92868e6a48e44efa8b35366b20b84e6.png]: https://img-blog.csdnimg.cn/a92868e6a48e44efa8b35366b20b84e6.png
[359b24c40bfa4e1299116149fac4924d.png]: https://img-blog.csdnimg.cn/359b24c40bfa4e1299116149fac4924d.png
[91731af63f87499994a2236f6fcd2148.gif]: https://img-blog.csdnimg.cn/91731af63f87499994a2236f6fcd2148.gif
[a64ea3005f9e4ab7b2e0e1d714e7f370.gif]: https://img-blog.csdnimg.cn/a64ea3005f9e4ab7b2e0e1d714e7f370.gif
[830d72d3ac71424182df08e5bcc1f382.png]: https://img-blog.csdnimg.cn/830d72d3ac71424182df08e5bcc1f382.png