MySQL （9）MySQL 索引原理 B+树

梦里梦外; 2022-06-17 05:13 210阅读 0赞

# **B-树** #

在了解B+树之前，我们先来看看B-树。首先B-树并不读作B减树，那是横杠而不是减号。B-树就是B树。

通过二叉查找树我们知道，查找树的效率和树的高度有关。为了减少磁盘的IO，我们就需要把“瘦高”的二叉查找树变得“矮胖”，这就是B-树。

B-树是一种多路平衡查找树，它的每一个节点最多包含K个孩子，K被称为B树的阶。

下面来具体介绍一下B-树（Balance Tree），一个m阶的B树具有如下几个特征：

> 1.根结点至少有两个子女。  
> 2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m  
> 3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m  
> 4.所有的叶子结点都位于同一层。  
> 5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

我们先来看一个3阶B-树  
![这里写图片描述][70]  
其实B-树的比较次数并不比二叉查找树少，但是在节点内的比较是在内存中进行，这样就比磁盘IO的速度要快很多。所以只要树的高度足够低，IO次数少，就可以提高查找性能。

**B-树的插入**  
B-树的一大优势就是：自平衡 。我们以插入4来比较  
![这里写图片描述][70 1]  
节点3，5已经是两元素节点，无法再增加。父亲节点 2， 6 也是两元素节点，也无法再增加。根节点9是单元素节点，可以升级为两元素节点。于是拆分节点3，5与节点2，6，让根节点9升级为两元素节点4，9。节点6独立为根节点的第二个孩子。  
![这里写图片描述][70 2]

**B-树的删除**  
我们删除元素11  
![这里写图片描述][70 3]  
删除11后，节点12只有一个孩子，不符合B树规范。因此找出12,13,15三个节点的中位数13，取代节点12，而节点12自身下移成为第一个孩子。（这个过程称为左旋）  
![这里写图片描述][70 4]

B-树主要应用于文件系统和数据库索引，比如MongoDB。

--------------------

## **B+树** ##

首先，简单介绍一下B+树的一些特性，B+数是B 树的一个变种。  
在B+树中，key 的副本存储在内部节点，真正的 key 和 data 存储在叶子节点上 。也就是说，由于B+树所有的 data 域都在根节点，所以查询时间复杂度固定为 O(log n)。

一个m阶的B+树具有如下几个特征：

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

![这里写图片描述][70 5]

这些正是B+树的特征，每一个父节点的元素都出现在子节点中，是子节点最大或最小的元素。叶子节点包含了全部的元素信息，并且每一个叶子节点都带有指向下一个节点的指针，形成了一个有序链表。

**卫星数据**  
B+树还有一个特点，那就是“卫星数据”的位置

> 卫星数据：值的就是索引元素所指向的数据记录，比如数据库中的某一行

B-树中的卫星数据  
![这里写图片描述][70 6]  
中间节点和叶子节点都带有卫星数据

B+树中的卫星数据  
![这里写图片描述][70 7]  
只有叶子节点带有卫星数据。

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

因为B+树中间节点没有卫星数据，同样大小的磁盘页可以容纳更多的叶子节点。这就代表数据量相同的时候，B+树的结构比B-树更加“矮胖”，查询IO的次数也更少。

**B+树的范围查找**  
B-树的范围查找必须中序遍历才能查找到所有范围内的数据  
![这里写图片描述][70 8]  
B+树的范围查找只需要在链表上遍历就可以了，这也是B+树比B-树有优势的地方。  
![这里写图片描述][70 9]

**B+树的优势：**

> 1.单一节点存储更多的元素，使得查询的IO次数更少。  
> 2.所有查询都要查找到叶子节点，查询性能稳定。  
> 3.所有叶子节点形成有序链表，便于范围查询。

--------------------

![这里写图片描述][SouthEast]  
B+树有2个头指针，一个是树的根节点，一个是最小关键码的叶节点。

所以 B+树有两种搜索方法：

一种是按叶节点自己拉起的链表顺序搜索。

一种是从根节点开始搜索，和B树类似，不过如果非叶节点的关键码等于给定值，搜索并不停止，而是继续沿右指针，一直查到叶节点上的关键码。所以无论搜索是否成功，都将走完树的所有层。

B+ 树中，数据对象的插入和删除仅在叶节点上进行。

[70]: /images/20220617/1741f285e55349b3880723aec7852044.png
[70 1]: /images/20220617/4e5d995050414980bfb9d7048f1574fd.png
[70 2]: /images/20220617/d3ad4d662f9c465188111ca5dd6b048e.png
[70 3]: /images/20220617/3377a8eb8e3c4a4689cdbf405d38ce96.png
[70 4]: /images/20220617/a460264f3b024fe180277e433ecae0ea.png
[70 5]: /images/20220617/d35c1451ae024bee9df8e955aabe5dbf.png
[70 6]: /images/20220617/f181423318204e478243bd78b2db4073.png
[70 7]: /images/20220617/a965fff2dce34394bbcaa54892da9a28.png
[70 8]: /images/20220617/e1db29366818409297a43381de921418.png
[70 9]: /images/20220617/ce9e8caf99b547fd942e3877f3ddb0be.png
[SouthEast]: /images/20220617/0b13c8a6523b4af29e0535f6cc89fb55.png