数据结构（三）、B树，B+树，B*树

逃离我推掉我的手 2023-03-06 03:23 28阅读 0赞

动态查找树主要有：二叉查找树，平衡二叉树，红黑树，B-tree/B+-tree/B\*-tree。前三个都是典型的二叉树结构，查找的时间复杂度*O*(log2*N*)和树的深度相关，随着树的深度降低会提高查找效率。而在现实情况中大部分数据存储在磁盘中，对于数据量比较大的情况下，对导致二叉树结构的深度也随之变大造成磁盘IO读写频繁导致查询效率低下，因此大部分关系型数据库都使用本篇要介绍的B+Tree结构，要理解B+树，需要先理解B树，本篇也会一起介绍B\*树。

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

[数据结构（一）、二叉树（BT），二叉查找树（BST），平衡二叉树（AVL树）][BT_BST_AVL]

[数据结构（二）、红黑树（RBT）][RBT]

**目录**

B树

简介

概念

查询流程

插入流程

删除流程

更新操作

B+树

简介

概念

查询流程

插入流程

删除流程

B\*树

简介

总结对比

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

# B树 #

## 简介 ##

上面提到，对于数据库来说，数据几乎都是存储在磁盘内，磁盘查找存取的次数由树的深度决定，因此，只要我们通过某种较好的树结构尽量减少树的深度，是不是就能有效减少磁盘查找存取的次数呢？于是就出现了一个新的查找树结构：多路查找树。增加树的度来减少树的深度。

正如平衡二叉树之于二叉查找树，自然就想到**平衡多路查找树**结构之于多路查找树，也就是本篇所要阐述的第一个主题**B-Tree（B树）结构**，B树的各种操作能让B树保持较低的深度，从而达到有效避免磁盘过于频繁的查找存取操作，达到有效提高查找效率的目的。

**B树（B-tree，B-树）**，和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），与红黑树相比，B树可以比红黑树的深度小许多，因为B树的分支因子比较大，所以B树可以在O（logN）时间内，实现各种如插入（insert），删除（delete）等动态集合操作。数据库索引技术里大量使用者B树和B+树的数据结构。

**在线测试B-tree数据结构：**

[https://www.cs.usfca.edu/~galles/visualization/BTree.html][https_www.cs.usfca.edu_galles_visualization_BTree.html]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70][]

## **概念** ##

由上图可以看到，B树的节点，对应硬盘中的页(page)或磁盘块(block) ，每个节点中包含了**关键字**和**子节点指针**两部分信息。

> 一个节点对应一个页，磁盘预读是以页为单位的，因此访问一个节点就代表访问一次磁盘（读取一页），也就是代表一次I/O操作；

**m阶B-Tree满足以下条件**：

1.  树中每个节点最多含有m个子节点（m>=2）。
2.  每个内节点至少 \[ceil(m / 2)\] 个子节点。 **内节点**即非根节点非页子节点，也可以叫中间节点。
3.  **关键字**key的数量 \[ceil(m / 2)-1\]<= n <= m-1，关键字按递增排序。
4.  每个叶节点具有相同的深度，即树的高度h，而且不包含关键字信息。

**例** 下面这是个5阶的B树：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70 1][]

上图也可以称为最小度数为3的B树，(degree) ，简写t。  
  
t就是上面第二个条件中 \[ceil(m / 2)\] 的值，即t=\[ceil(m/2)\], 3=ceil(5/2) 。

1.  每个非根节点至少有t-1个关键字，非根内节点至少有t个子节点。 t称为度数(degree)，t>=2 。
2.  每个节点至多有2t-1关键字，每个内节点最多有2t个子节点。
3.  每个叶节点具有相同的深度，即树的高度h，而且不包含关键字信息。

**m阶**：每个节点至多有m个子树。表示一个树节点最多有多少个查找路径，m=m路,当m=2则是2叉树,m=3则是3叉。

**最小度数t**：(degree) ，简写t，*t=\[ceil(m/2)\]*。每一个节点能包含的关键字数量有一个上界和下界。这个下界就是最小度数t。

## 查询流程 ##

![20200804161836639.png][]

对于上面的3阶B树，如果想查找15的位置，会经过下面的流程：

1.  在根节点先判断9<15<33，于是根据根节点中间的指针找到13节点（根据二分法，左小右大）；
2.  然后在13节点判断13<15，于是找到15节点在13节点右边的指针指向的节点内；
3.  在15,16节点内判断15=15，于是找到15的位置，返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；

## 插入流程 ##

**规则：**

**节点分裂规则**：对于一个m路查找树，关键字数量必须小于等于m-1，当关键字数大于m-1时就会进行节点拆分；

**排序规则**：满足节点本身比左边节点大，比右边节点小的排序规则;

> 进行拆分时，中间的元素提取升级到父节点， 左边的元素单独构成一个节点， 右边的元素单独构成一个节点；

**例**：定义一个5阶B树，依次插入3,9,13,32,22,27,70,29：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70 2][]

## 删除流程 ##

**规则：**

**节点合并规则**：对于一个m路查找树，关键字数必须大于等于ceil(m/2)-1，当关键字数量小于该值时就会进行节点合并；

**排序规则**：满足节点本身比左边节点大，比右边节点小的排序规则;

> 关键字数量小于 ceil(m/2)-1 时先从子节点取，子节点没有符合条件时就向父节点取，取中间值往父节点放；

**例**：从5阶B树中删除27：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70 3][]

## 更新操作 ##

B树的更新操作通常有两种：

1.  直接对数据进行更新；
2.  分解为删除加插入操作；

# B+树 #

## 简介 ##

从上面的B树中，我们可以看到 相比于二叉平衡树，B树由于每个节点存储更多的关键字，可以将树的深度降低，在查询单条数据是非常快的。但在范围查询场景下，B树每次都要从根节点查询一遍，这是很慢的，因此出现了B树的变种，B+树。相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。

**在线测试B-tree数据结构：**

[https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html][https_www.cs.usfca.edu_galles_visualization_BPlusTree.html]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70 4][]

## 概念 ##

**规则**

1.  B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
2.  B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
3.  B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针；
4.  非叶子节点的子节点数等于关键字数；

> 非叶子节点相当于是叶子节点的索引（稀疏索引），叶子节点相当于是存储（关键字）数据的数据层；
> 
> 所有关键字都出现在叶子节点的链表中（稠密索引），且链表中的关键字恰好是有序的；

**特点**

1.  **B+树的层级更少**：相较于B树，B+树每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
2.  **B+树查询速度更稳定**：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
3.  **B+树天然具备排序功能**：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
4.  **B+树全节点遍历更快**：B+树遍历整棵树只需要遍历所有的叶子节点即可，而且由于数据顺序排列并且相连，所以便于区间查找和搜索，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

## 查询流程 ##

与B-树也基本相同，区别是B+树只有达到叶子节点才命中（B-树可以在非叶子节点命中），其性能也等价于在关键字全集做一次二分查找；

![20200804182939634.png][]

对于上面的5阶B+树，如果想查找122,133,144的位置，会从根节点\[111\]-->\[133,155\] 然后判断，122<133，于是在\[133,155\]节点的第一个孩子里找到122,133<=133<=155，133<=144<=155，于是在\[133,155\]节点的第二个孩子里找到133和144。

## 插入流程 ##

与B树一样，往B+树内插入数据时候会根据下面的规则触发分裂规则。

**B+树的分裂规则**：

*  当一个节点满(关键字数量等于阶数)时，分配一个新的节点，并将原节点中1/2的数据复制到新节点，最后在父节点中增加新节点的指针；（将当前节点，分为左右两个叶子节点，左叶子节点包含前M/2个记录，右叶子节点包含剩余记录，并且将第M/2+1个记录的关键字上移到父节点。当前节点指针指向父节点。）
 *  B+树的分裂只影响原节点和父节点，而不会影响兄弟节点，所以它不需要指向兄弟的指针。

**例**：定义一个5阶B+数，依次往里插入11,22,33,44,36,40,38：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70 5][]

## 删除流程 ##

**B+树删除算法**

1.  找到目标关键字所在的叶节点位置，进行删除，若删除后，当前节点关键字数量大于等于ceil(M/2)−1，结束，否则进行步骤2；
2.  若兄弟节点的关键字有富余(大于ceil(M/2)−1)，向兄弟借一个记录，同时用借到的key替换父节点中对应的关键字，结束。否则进行步骤3；
3.  若兄弟节点没有富余,则当前节点和兄弟节点合并成一个新的节点，删除父节点的关键字，新节点指向父节点相应的位置。进行步骤4；
4.  若索引节点的关键字个数大于等于ceil(M/2)−1，则结束，否则进行步骤5；
5.  若兄弟节点有富余，父节点key下移，兄弟节点key上移，删除结束。进行步骤第6步；
6.  当前节点和兄弟节点及父节点下移key合并成一个新的节点。将当前节点指向父节点，重复第4步；

**例**：从5阶B+树种删除44,77：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70 6][]

# B\*树 #

## 简介 ##

B\*树是B+树的变种，相对于B+树他们的不同之处如下：

（1）首先是关键字个数限制问题，B+树初始化的关键字初始化个数是**cei(m/2)**，b\*树的初始化个数为（**cei(2/3\*m)**）

（2）B+树节点满时就会分裂，而B\*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70 7][]

**B\*树的分裂**：

*  当一个节点满时，如果它的下一个兄弟节点未满，那么将一部分数据移到兄弟节点中，再在原节点插入关键字，最后修改父节点中兄弟节点的关键字（因为兄弟节点的关键字范围改变了）；
 *  如果兄弟也满了，则在原节点与兄弟节点之间增加新节点，并各复制1/3的数据到新节点，最后在父节点增加新节点的指针。

> B\*树分配新节点的概率比B+树要低，空间使用率2/3 相比于B+树1/2 更高。

# 总结对比 #

**B树**：多路搜索树，每个节点存储M/2到M个关键字，非叶子节点存储指向关键字范围的子节点；所有关键字在整颗树中出现，且只出现一次，非叶子节点可以命中；

**B+树**：在B树基础上，为叶子节点增加链表指针，所有关键字都在叶子节点中出现，非叶子节点作为叶子节点的索引；B+树总是到叶子节点才命中；

**B\*树**：在B+树基础上，为非叶子节点也增加链表指针，将节点的最低利用率从1/2提高到2/3；

> B+树虽然优点很多，但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

**为什么B+树比B树更适合实际应用中操作系统的文件索引和数据库索引？**

1.  **B+tree的磁盘读写代价更低**  
    B+tree的内部节点并没有指向关键字具体信息的指针。因此其内部节点相对B树更小。如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
    
    例：假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个节点最多8个关键字)的内部节点需要2个盘快。而B+ 树内部节点只需要1个盘快。当需要把内部节点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
2.  **B+tree的查询效率更加稳定**  
    由于非叶子节点并不是最终指向文件内容的节点，而只是叶子节点中关键字的索引。所以任何关键字的查找必须走一条从根节点到叶子节点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
3.  B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。**B+树只要遍历叶子节点就可以实现整棵树的遍历**。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。

希望本文对你有帮助，请点个赞鼓励一下作者吧~ 谢谢！

[BT_BST_AVL]: https://blog.csdn.net/wsdc0521/article/details/107676999
[RBT]: https://blog.csdn.net/wsdc0521/article/details/107677009
[https_www.cs.usfca.edu_galles_visualization_BTree.html]: https://www.cs.usfca.edu/~galles/visualization/BTree.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70]: /images/20230208/abea5d4760c14919af083c014e0c2661.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70 1]: /images/20230208/ff5f526c2ef946e18908663a9013fd12.png
[20200804161836639.png]: /images/20230208/318ffa54c29f4ec2936189415b742d71.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70 2]: /images/20230208/5c985a104c794c3e9c76a785c194645a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70 3]: /images/20230208/0997f2a5d9084ef0b1420696f7532d25.png
[https_www.cs.usfca.edu_galles_visualization_BPlusTree.html]: https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70 4]: /images/20230208/ebf14655984d4959b0b51ebfaf417dda.png
[20200804182939634.png]: /images/20230208/6f6cc1defcc64d37b95fbff3b8774ec8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70 5]: /images/20230208/7e5c148a762b422fb98b064f9fcf5ca6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70 6]: /images/20230208/7ec90876c12c449bbce2d91cf4cb66cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70 7]: /images/20230208/6662b5768e364d86aed94a23a549d0ef.png