mysql为什么采用B+树索引

liyuguanguan

2024-04-27 帮助1人

在讨论mysql为什么采用B 树之前我们可以想一下为什么选用树数据结构,以及有什么数据结构。

数据结构的类型

线性数据结构
1. 数组
2. 链表
3. 哈希表(数组和链表的合并)
4. 栈
5. 队列

非线性数据结构
1. 树
2. 图
3. 跳表

索引的作用

如果要知道索引适合什么数据结构，那我们索引需要来解决什么样的问题（痛点）和需要发挥着什么样的作用，其次再看用什么样的数据结构。

我们都知道mysql的数据是放在磁盘里面的，可以保证数据不丢失，但同时也会造成相比于内存查询慢的问题(具体为什么查询慢，自行查询)。

换个角度想既然内存比磁盘快,那么把一部分数据存储到内存中不是可以增加查询速度吗？是的，mysql确实也是这么做的，会从硬盘中查询出来的数据放到内存中，这样就不会直接查询磁盘了，但是我们不要忘记了，即使是放到内存中的数据也是从磁盘中拿到的，不管怎么样都少不了跟磁盘I/O。磁盘I/O次数越多，效率则越低，这也就是索引要解决的问题,尽量减少磁盘I/O次数。

索引的选择

哈希表

说到减少磁盘I/O,在查询的时候我们会立刻想到哈希表,理想情况下时间复杂度O(1),mysql也支持hash的索引,但是范围查询哈希表支持的不是很好，一旦范围查询时间复杂度就变成0(n)了。

跳表

既然哈希表不适合范围查询，那么跳表呢。首先跳表是什么呢，要理解跳表就首先要知道链表是什么。

链表就是有序的一组数据，如果要查询一个数据最坏的情况一下时间复杂度是O(n)

为了解决链表查询时间复杂度的问题，就诞生了跳表,跳表实际就是一个有序的链表索引

如果我们查找一个4的数据,先从索引层查找,查找到索引3的下一个索引是5，所以4是在索引3里面的，之后遍历链表即可。看起来很完美，也支持范围查询。但是随着数据量增加跳表的索引会增加很多，索引增加也就代表着I/O次数增加,所以跳表并不能解决I/O问题

首先我们先来看一下树的结构是什么样子的

暂时无法在飞书文档外展示此内容

从图上可知,树的结构跟跳表是类似的,每棵树的根节点相当于跳表的索引，所以树的查找也是很快的。

那么都有是树呢

二叉树

二叉树的定义:

二叉树（Binary Tree）是另外一种树型结构，它的特点是每个节点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分。

与树的递归定义类似，二叉树的递归定义如下：二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称为根的左子树和右子树的子树所组成的非空树。

由以上定义可以看出，二叉树中每个结点的孩子数只能是0、1或2个，并且每个孩子都有左右之分。位于左边的孩子称为左孩子，位于右边的孩子称为右孩子；以左孩子为根的子树称为左子树，以右孩子为根的子树称为右子树。（上图就是二叉树）

而二叉树还有2个特殊的存在 满二叉树、完全二叉树

满二叉树的定义:满二叉树的定义是一棵二叉树的所有非叶子节点都存在左右子节点，并且所有子节点在同一层级。

完全二叉树定义:完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一个一个地对应时称之为完全二叉树( 堆排序就是用完全二叉树实现的,大顶堆适合正序,小顶推适合倒叙)

区别:其实满二叉树是完全二叉树的特例，因为满二叉树已经满了，而完全并不代表满。所以形态你也应该想象出来了吧，满指的是出了叶子节点外每个节点都有两个孩子，而完全的含义则是最后一层没有满，并没有满。

二叉查找树

二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。它是怎么做到这些的呢？

这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

(二叉查找树)

以上图为例查找5的过程是

插入过程:

但是有一种极端情况下二叉查找树会退化成链表，如下图,查找4的时间复杂度就会变成了O(n),而且二叉查找树的高度也不能确定，如果很高I/O问题也没有解决。

平衡二叉树(AVL)

平衡二叉树又称AVL树 。它可以是一颗空树，或者具有以下性质的 二叉排序树 ：它的左子树和右子树的高度之差(平衡因子)的绝对值不超过1且它的左子树和右子树都是一颗平衡二叉树。

自平衡二叉树就是为了解决二叉查找树极端情况下退化成链表的问题。

判断一棵平衡二叉树（AVL树）有如下必要条件：

条件一：必须是二叉搜索树。

条件二：每个节点的左子树和右子树的高度差至多为1。

以上树其实都有一个问题，就是随着数据量大都会造成树过高的问题。树越高I/O越多，所以都不符合要求,那么有没有一种树没有那么高呢，答案是有的 B树。

B树

由于二叉树只能有左右两个节点，数据量大的话，势必会造成树过高，那么能不能让一个树的节点不限于左右两个呢,这样的话节点增多就不会造成树的高度过高了。

暂时无法在飞书文档外展示此内容

B树的出现就解决了平衡二叉树的高度问题，同时B树的一个节点可以存储多个数据，而且可以有多个节点，每一个节点的包含的最多个子节点成为B树的阶

一颗三阶的B树

上图中每一个节点称为页，在 MySQL 中数据读取的基本单位是页，而页就是我们上面所说的磁盘块。磁盘块中的 p 节点是指向子节点的指针。指针在树结构中都有，在前面的二叉树中也都是有的。

那我们来看一下B树种查找99元素是怎么样的流程。

1.首先从根节点,发现99比35大，则通过P3指针找到磁盘块4

2.还是通过步骤1比较发现99比87大，则还是通过P3指针找到磁盘块11

3.通过磁盘块11找到99

从结果而知B树已经解决了磁盘I/O的问题，那么为什么mysql还采用B 树呢，别忘了我们上面举的例子正好是一个等于99的元素，如果是查找36-99呢?B树则采用了中序遍历(左根右)，为什么采用中序遍历呢，因为中序遍历是有序的下面举个例子来演示一下中序遍历。

暂时无法在飞书文档外展示此内容

根据左根右的原则,

第一次遍历的结果是 10 19 25

第二次遍历的结果是9 10 15 19 25

第三次遍历结果为 9 10 15 19 20 25 26

可以看出中序遍历是有序的。

B树的范围查找过程

所以B树不适合范围查找

B 树

B 树是基于B树的一种变形，有着比B树更高的查询性能

B 树相比于 B 树，做了这样的升级：B 树中的非叶子节点都不存储数据，而是只作为索引。由叶子节点存放整棵树的所有数据。

而叶子节点之间构成一个从小到大有序的链表互相指向相邻的叶子节点，也就是叶子节点之间形成了有序的双向链表。

一颗三阶的B 树(图不准，叶子结点应该是双向链表)

例如查询元素3

和B树相比，由于B 树的数据都在叶子结点,而B树只要匹配到元素即可，不论它是中间节点还是叶子节点，因此B树的查询性能并不稳定。

B 树的查询3到11之间的元素

总结:二叉树、二叉查找树、平衡二叉树等都会有随着数据量增多造成树变"高"的问题。

B树解决了树"高"的问题，但是对于范围查询会造成I/O次数多的问题，而B 树又能解决范围查询的问题。

参考:https://zhuanlan.zhihu.com/p/59788528

https://wylu.me/posts/acfcdb43/

https://cloud.tencent.com/developer/article/1691641

https://zhuanlan.zhihu.com/p/59788528

https://zhuanlan.zhihu.com/p/98021010

https://blog.csdn.net/lcl_xiaowugui/article/details/105926369

这篇好文章是转载于：学新通技术网

mysql为什么采用B+树索引

photoshop保存的图片太大微信发不了怎么办

《学习通》视频自动暂停处理方法

Android 11 保存文件到外部存储，并分享文件

word里面弄一个表格后上面的标题会跑到下面怎么办

photoshop扩展功能面板显示灰色怎么办

微信公众号没有声音提示怎么办

excel下划线不显示怎么办

excel打印预览压线压字怎么办

TikTok加速器哪个好免费的TK加速器推荐

怎样阻止微信小程序自动打开