什么是B-树、B树、B+树、B*树？

怼烎@ 2023-01-12 10:28 184阅读 0赞

## 引言 ##

公众号原文链接：[文件系统的灵魂数据结构 B树][B] [什么是B-树、B树、B+树、B\*树？][B-_B_B_B] 希望点进去的小伙伴关注一下我的公众号哟，文末有二维码，谢谢！

正如标题所言，本文介绍经常使我们混淆的B-树、B树、B+树和B\*树。

首先，B-tree树即B树。B即Balanced平衡，因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，这是个非常不好的直译，很容易让人产生误解，人们可能会以为B-树和B树是两种树。

## 1、B树 ##

### **1.1、B树产生的背景** ###

不管是二叉树、二叉查找树还是平衡二叉树，它们都有诸多限制，比如：

*  每个结点只能存储一个元素。
 *  结点的度至多为2，即使是平衡二叉树，在存储百万、千万级别的数据量时，也会导致树的深度特别大，而深度大就会影响查找效率。

这里提一下平衡二叉树的缺点：

*  由于平衡二叉树需要左旋和右旋来调整树的结构，因此在频繁插入和删除的场景下，每插入或删除一个结点，都极有可能导致树的不平衡，性能也会大打折扣。红黑树（后面会介绍）就是来解决这个问题的。

前面讲的几种数据结构，都是纯内存操作，但是当数据量特别大（如数据库中千万级别的数据表、磁盘中的上万个文件等），内存都存不下了怎么办？在这种情况下，需要用外存（硬盘）来存储，而对数据的处理则需要不断地从硬盘调入调出。

此时，时间复杂度的计算就会发生变化，因为还要额外考虑对硬盘的访问次数和单次访问时间等。

为了降低对硬盘的访问次数，需要设计新的数据结构。前面讲的几种树，结点都只能存一个元素，因此，当元素非常多的时候，要么结点的度非常大，要么树的深度非常大，这两种情况都会导致对硬盘的访问次数偏大。如果每个结点能存多个元素，那么树的总结点数就会大大减少，对磁盘的访问次数也会相应的大大减少。

由于有如上限制，为此引入了多路查找树的概念。

多路查找树：结点的度可以大于2，并且每一个结点可以存储多个元素。由于是查找树，所以结点之间存在某种特定的排序关系。

### **1.2、B树的基本概念** ###

B树是一种平衡的多路查找树。

其实B树和多路查找树是一个意思，网上很多资料也是这样认为的，但是也可以认为多路查找树和B树不是一个意思，因为多路查找树不一定是平衡的。

B树的阶：所有结点中的最大孩子数。其实跟树的度一个意思。

一个m阶B树的属性：

*  如果根结点不是叶子结点，则其至少有两颗子树。
 *  \[m/2\]<=k<=m，\[m/2\]为向上取整，比如9阶B树，5<=k<=9。每一个非根分支结点都有k个孩子和k-1个元素；叶子结点有k-1个元素。
 *  所有叶子结点在同一层（平衡）。
 *  所有分支结点有下列信息数据：(n,A0,K1,A1,K2,A2,...,Kn,An)，n是结点存储的元素个数，Ai表示子树，Ki表示元素，而从A0到An的值是从小到大排序的，这跟二叉查找树的性质一样。

下面来演示一下如何在B树上查找元素，如下图，是一颗B树。

![图片][bd237fe2992c5d8f9a2a9495e341d6f4.png]

1.  如果要查找元素7，首先从硬盘上读取根节点（第一次读磁盘）
2.  即读到了3,5,8三个元素，发现7并不在其中，但由于5<7<8，因此找到了A2，然后根据A2再读取一次硬盘（第二次读磁盘）
3.  此时读到了2,6,7三个元素，找到了元素7

两次磁盘读取就查找了我们想要的元素，非常高效，B树就是这样一种为内外存数据交互为设计的数据结构。

## **2、B+树** ##

尽管B树有很多好处，但是它还是有缺点的：

*  当进行范围查找时，存在回旋查找的问题
 *  排序的时候，需要进行一次中序遍历（order by）

其实这也是数据库索引不使用B树，而使用B+树的原因。

因为B树是存储在磁盘中的，如下图的B树，假设每个结点都存储在磁盘的不同页中（一般在设计的时候，会将B树的阶与磁盘页的大小相匹配，目的是为了减少跨页访问）。

![图片][d0a359f4d4831dbaad004f26b031f348.png]

那么进行一次中序遍历的访问流程是：

*  页面2->页面1->页面3->页面1->页面4->页面1->页面5

页面1被访问了多次，这就是回旋访问问题。如果一个文件系统使用B树来做存储结构的话，那性能肯定还是不高的。B+树正是应文件系统所需而出的一种B树的升级版。

一颗B+树的样子如下图所示。

![图片][cddebc761dd374d04df56cc8ee9d0ee7.png]

图1

一颗m阶的B+树与m阶的B树差异如下：

1.  非叶子结点的元素个数=孩子个数
2.  B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中）
3.  所有的非叶子结点相当于叶子结点的索引，而所有的叶子结点才是存储关键字的数据层
4.  所有叶子结点根据关键字从小到大排序，且通过指针顺序连接
5.  所有非叶子结点中的元素，都同时存在于子节点中(因此元素个数与孩子数要相同，相同与将k个元素分配给k个孩子)，在子节点中是最小（或最大）元素。

对于差异5，,什么时候表现为最小元素，什么时候表现为最大元素呢？

如图1所示，根结点中元素与孩子指针按从小到大排序应该是

*  5<P1<28<P2<65<P3

然后分别将5分配给P1、28分配给P2、65分配给P3，自然而然就表现为了最小元素，二层的分支结点以此类推。

若要表现为最大元素，则需要将指针放在最前面，即类似于这样的排序

*  P1<5<P2<28<P3<65

如果要在B+树上查询关键字，即使在分支结点上找到了该关键字，它也只是用来做索引的，最终还是要定位到包含该关键字的叶子结点中。

大家有没有注意到图1还有一个data指针，它指向了最小叶子结点。如果我们要遍历整颗B+树的话，直接从data指针开始搜索即可，而不需要从根结点开始查找。

## **3、B\*树** ##

B\*树是B+树的变体，在B+树的非根分支结点再增加指向兄弟的指针，将结点的最低利用率从1/2提高到2/3。

一颗B\*树如下图所示。

![图片][af2417fe540be05f40329a890ed2bea5.png]

本文就介绍到这里啦，感谢大家阅读！

## 我的二维码 ##

觉得写得不错的小伙伴，扫码关注一下我的公众号吧，谢谢呀！

![20210121085816775.jpg][]

[B]: https://mp.weixin.qq.com/s?__biz=MzI1NTc1MDU3Mw==&mid=2247484807&idx=1&sn=486872217a21ebe58f01e4b4a509b22b&chksm=ea307d45dd47f453debb19334b287f897f9c376fd01f51ecb690a64d595f20c7f6546a660484&token=1460364831&lang=zh_CN#rd
[B-_B_B_B]: https://mp.weixin.qq.com/s?__biz=MzI1NTc1MDU3Mw==&mid=2247484836&idx=1&sn=b4e4caad345c90a4e2f254c629b71423&chksm=ea307d66dd47f4709e7f97c2a5d2eb6672d6cfc65a088bbf830a47b08c80017d1314bb855cac&token=1460364831&lang=zh_CN#rd
[bd237fe2992c5d8f9a2a9495e341d6f4.png]: /images/20221119/af9807075aaa4d96bbb1874b481e5fa7.png
[d0a359f4d4831dbaad004f26b031f348.png]: /images/20221119/d48c9ed5c04b4dadadbf776f5f98480d.png
[cddebc761dd374d04df56cc8ee9d0ee7.png]: /images/20221119/190e429453454f3f98e1d7e5fc0bd292.png
[af2417fe540be05f40329a890ed2bea5.png]: /images/20221119/95015a035c27419f9094275ae64d2942.png
[20210121085816775.jpg]: /images/20221119/25dca4dafa9e400fafe5a678974cdc21.png