本文共 2306 字，大约阅读时间需要 7 分钟。

引言

公众号原文链接：  希望点进去的小伙伴关注一下我的公众号哟，文末有二维码，谢谢！

正如标题所言，本文介绍经常使我们混淆的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树。

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树的阶与磁盘页的大小相匹配，目的是为了减少跨页访问）。

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

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

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

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

图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*树如下图所示。

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

我的二维码

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

转载地址：https://blog.csdn.net/xl_1803/article/details/113327698 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！