【数据结构】考研408 | B树探秘：从查找操作到树高性能分析

导读

大家好，很高兴又和大家见面啦！！！ 在上一篇内容中我们初步认识了 多路查找树、多路平衡查找树 以及 B树； 在 多路平衡查找树 这个大家族中，B树 就是其最经典的代表，因此我们不仅要认识 B树 ，我们还有了解该数据结构的一系列基本操作。 对于一个数据结构而言，在其基本操作：增、删、改、查中，最核心的操作就是 查找；而对于 树形结构 而言，其查找操作与 树的高度 挂钩； 因此在今天的内容中，我们将会详细介绍 B树 的查找操作以及不同情况下 B树 的高度，下面就让我们直接进入今天的内容；

一、查找

B树 的查找与 BST 很相似，只是每个结点都是多个关键字的有序表，在每个结点上所作的不是两路分支决定，而是根据该结点的子树所做的多路分支决定。

1.1 查找思想

B树 的查找思想并不复杂，具体步骤如下：

• 从根结点开始查找目标关键字或关键字所在范围：
  • 若当前关键字大于目标关键字，则继续查找当前关键字的左侧指针指向的子树
  • 若当前关键字小于目标关键字：
    • 当前关键字的右侧还存在关键字，则继续顺序查找
    • 当前关键字的右侧不存在关键字，则继续查找当前关键字的右侧指针指向的子树
  • 若当前关键字等于目标关键字，则查找成功
• 找到目标关键字所在子树后，继续按照上述步骤继续查找：
  • 若找到了目标关键字，则查找成功
  • 若当前子树为空树，则说明查找失败

这里我个人的看法是，该查找过程可以视为是一棵复合的 BST 的查找过程，这里我解释一下什么是复合，下面我以一棵 3阶B树 为例进行说明：

flowchart LR
	subgraph BT[3阶B树]
		direction TB
		root[n, p0, key1, p1, key2, p2]
		sub1[子树1]
		sub2[子树2]
		sub3[子树3]
		root ---> sub1
		root ---> sub2
		root ---> sub3
	end
	subgraph BST1
		direction TB
		root1[key1]
		sub_1[子树1]
		sub_2[子树2]
		root1--->|p0|sub_1
		root1--->|p1|sub_2
	end
	subgraph BST2
		direction TB
		root2[key2]
		sub_3[子树2]
		sub_4[子树3]
		root2--->|p1|sub_3
		root2--->|p2|sub_4
	end
	BST1 --->|+|BST2 --->|复合成|BT

在结点中的顺序查找过程可以我们可以视为 查找目标所在的 BST ：

• 当前关键字 key_i 对应的是 BST 的根结点 root
• 当前关键字的左侧指针 p_{i -1} 对应的是 BST 的左子树指针 lchild
• 当前关键字的右侧指针 p_i 对应的是 BST 的右子树指针 rchild

当我们确定了目标所在的 BST 后，我们再根据 BST 的查找规则继续查找 目标关键字：

• 当前关键字 等于 目标关键字，则查找成功
• 当前关键字 小于 目标关键字，则视情况进行查找：
  • 当前关键字右侧仍存在关键字，则继续向右顺序查找
  • 当前关键字右侧不存在关键字，则查找以当前关键字为根的 BST 的右子树指针
• 当前关键字 大于 目标关键字，则查找以当前关键字为根的 BST 的左子树指针

这里可能大家会好奇，为什么小于时，是直接查找子树？而大于时，则需要看具体的情况？ 这是因为在结点内的查找我们采用的是从左到右的顺序查找，而结点内的元素是按从左到右升序排列，即 key_0 < key_1 < \cdots < key_{m - 1}key 比当前关键字 key_i 小时，说明目标关键字大于当前关键字左侧的所有关键字，但是小于当前关键字，即 key_0 < \cdots < key_{i - 1} < \textcolor{red}{key} < key_ikey_i 为根结点的 BST 的左子树（p_{i - 1} 指向的子树）即可；

PS: 这部分提到的 BST 指的是 m阶B树 中一棵近似的 BST ，而不是 m阶B树 中真正存在一棵 BST； 这里大家一定要清楚，不要弄混了

B树 的查找包含两个基本操作：

• 在 B树 中找结点
• 在结点中找关键字

B树 常存储在磁盘上，因此前一查找操作实在磁盘上进行，后一查找操作则是在内存中进行，即 B树 的查找操作是先在磁盘上找到目标结点后，再将结点信息读入内存，最后在内存中通过顺序查找或者折半查找找到目标关键字。 因此，在磁盘上进行查找的次数即目标结点在B树上的层次数，决定了 B树 的查找效率。

1.2 查找过程

下面我们以一棵 5阶B树 为例，简单的说明一下具体的查找过程：

flowchart TB
a[22]
b[5, 11]
c[36, 45]
a--->b
a--->c
d[1, 3]
e[6, 8, 9]
f[13, 15]
b--->d
d--->d1[NULL]
d--->d2[NULL]
d--->d3[NULL]
b--->e
e--->e1[NULL]
e--->e2[NULL]
e--->e3[NULL]
b--->f
f--->f1[NULL]
f--->f2[NULL]
f--->f3[NULL]
g[30, 35]
h[40, 42]
i[47, 48, 50, 56]
c--->g
g--->g1[NULL]
g--->g2[NULL]
g--->g3[NULL]
c--->h
h--->h1[NULL]
h--->h2[NULL]
h--->h3[NULL]
c--->i
i--->i1[NULL]
i--->i2[NULL]
i--->i3[NULL]
i--->i4[NULL]
i--->i5[NULL]

这里我们以查找关键字 10 与 关键字 48 为例，分别说明查找失败与查找成功两个场景； 其具体的查找过程可以分为两步：

• 从磁盘中读取当前结点到内存中

在开始对 B树 进行查找时，磁盘中会有一个指针指向树中的各个结点，而计算机在查找该结点时，不能直接在磁盘中进行查找，而是通过将磁盘中的指针指向的当前结点读取到内存后，再对内存中的结点进行查找操作；

• 在内存中查找关键字

当完成了第一步从磁盘读取结点数据到内存后，正在的查找操作就会在内存中执行。 由于 B树 中各结点中的数据是一个升序顺序表，因此在内存中查找目标关键字是否存在与当前结点中时，可以采用的查找操作既可以是 顺序查找 也可以是 折半查找 ；

• 返回查找结果

在查找的过程中，会先判断当前读取的结点是否为 空叶结点：

• 为 空叶结点 ，则查找失败
• 为 非空叶结点 ，继续执行具体的查找方案

不管是用 顺序查找 还是 折半查找 ，最终都只会存在3种结果：

• 当前关键字 等于 目标关键字：key_i == \textcolor{red}{key} ，查找成功
• 当前关键字 小于 目标关键字：key_i < \textcolor{red}{key}p_i 指向的子树
• 当前关键字 大于 目标关键字：key_i > \textcolor{red}{key}p_{i - 1} 指向的子树

这里我们需要注意，内存中的查找结果一定是当前结点的最终查找结果：

• 完成了关键字的查找——查找成功或者查找失败
• 确定了关键字的具体范围

下面我们就以查找关键字 10 和关键字 48 为例进行说明；

1.2.1 查找失败

当我们在查找关键字 10 时，其具体过程如下所示：

• 首先我们会从磁盘中读取根结点到内存中：

flowchart TB
	subgraph BT[磁盘]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->|p0|b
		a--->|p1|c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->|p0|d

		b--->|p1|e

		b--->|p2|f

		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->|p0|g

		c--->|p1|h

		c--->|p2|i

	end
	subgraph Node[内存]
		n[22]
	end
	BT--->Node
classDef R color: black, fill: red, stroke: red, stroke-width: 2px
class a R

通过内存中的 顺序/折半查找 最终确定了关键字的范围：10 < 22p0 指针指向的子树：

• 读取 p_0 指向的子树根结点到内存中

flowchart TB
	subgraph BT[磁盘]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->|p0|b
		a--->|p1|c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->|p0|d

		b--->|p1|e

		b--->|p2|f

		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->|p0|g

		c--->|p1|h

		c--->|p2|i

	end
	subgraph Node[内存]
		n[5, 11]
	end
	BT--->Node
classDef R color: black, fill: red, stroke: red, stroke-width: 2px
class b R

通过内存中的 顺序/折半查找 最终确定了关键字的范围：5 < 10 < 11p_1 指针指向的子树：

• 读取 p_1 指向的子树根结点到内存中

flowchart TB
	subgraph BT[磁盘]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->|p0|b
		a--->|p1|c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->|p0|d

		b--->|p1|e
		e--->|p0|e1[NULL]
		e--->|p1|e2[NULL]
		e--->|p2|e3[NULL]
		b--->|p2|f

		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->|p0|g

		c--->|p1|h

		c--->|p2|i

	end
	subgraph Node[内存]
		n[6, 8, 9]
	end
	BT--->Node
classDef R color: black, fill: red, stroke: red, stroke-width: 2px
class e R

通过内存中的 顺序/折半查找 最终确定了关键字的范围：9 < 10p_2 指针指向的子树：

• 读取 p_2 指向的子树根结点到内存中

flowchart TB
	subgraph BT[磁盘]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->|p0|b
		a--->|p1|c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->|p0|d

		b--->|p1|e
		e--->|p0|e1[NULL]
		e--->|p1|e2[NULL]
		e--->|p2|e3[NULL]
		b--->|p2|f

		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->|p0|g

		c--->|p1|h

		c--->|p2|i

	end
	subgraph Node[内存]
		n[NULL]
	end
	BT--->Node
classDef R color: black, fill: red, stroke: red, stroke-width: 2px
class e3 R

由于当前结点为 空叶结点 ，这就表示树中不存在关键字 10 ，因此本次查找失败；

1.2.2 查找成功

当我们在查找关键字 48 时，其具体过程如下所示：

• 首先我们会从磁盘中读取根结点到内存中：

flowchart TB
	subgraph BT[磁盘]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->|p0|b
		a--->|p1|c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->|p0|d

		b--->|p1|e

		b--->|p2|f

		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->|p0|g

		c--->|p1|h

		c--->|p2|i

	end
	subgraph Node[内存]
		n[22]
	end
	BT--->Node
classDef R color: black, fill: red, stroke: red, stroke-width: 2px
class a R

通过内存中的 顺序/折半查找 最终确定了关键字的范围：22 < 48p1 指针指向的子树：

• 读取 p_1 指向的子树根结点到内存中

flowchart TB
	subgraph BT[磁盘]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->|p0|b
		a--->|p1|c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->|p0|d

		b--->|p1|e

		b--->|p2|f

		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->|p0|g

		c--->|p1|h

		c--->|p2|i

	end
	subgraph Node[内存]
		n[36, 45]
	end
	BT--->Node
classDef R color: black, fill: red, stroke: red, stroke-width: 2px
class c R

通过内存中的 顺序/折半查找 最终确定了关键字的范围：45 < 48p_2 指针指向的子树：

• 读取 p_2 指向的子树根结点到内存中

flowchart TB
	subgraph BT[磁盘]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->|p0|b
		a--->|p1|c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->|p0|d

		b--->|p1|e

		b--->|p2|f

		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->|p0|g

		c--->|p1|h

		c--->|p2|i

	end
	subgraph Node[内存]
		n[47, 48, 50, 56]
	end
	BT--->Node
classDef R color: black, fill: red, stroke: red, stroke-width: 2px
class i R

通过内存中的 顺序/折半查找 最终在该结点中找到了关键字 48 ，因此查找成功；

二、树高

从查找的过程我们不难发现，B树 的整个查找过程与磁盘的存取次数息息相关； 在查找中，从磁盘中读取 B树 的结点次数，与结点所在层次相同：

• 关键字 22 所在结点位于树的第一层，从磁盘中读取该结点时，读取的总次数为 1 次
• 关键字 48 所在结点位于树的第三层，从磁盘中读取该结点时，读取的总次数为 3 次

换句话说，当我们要查找的关键字所在的结点层次越高，对应的 B树 的高度也就越高，相应的，查找操作中所进行的磁盘存取次数也就越多； 这么看来，对 B树 进行查找操作时，所需的磁盘存取次数与 B树 的高度成正比； 因此，当一棵 B树 的高度越低时，其查找的效率也就越高。接下来，我们就来一起分析一下 B树 在不同情况下的高度。

PS: 这里我们探讨的 B树 的高度是 不包括空叶结点 的高度； 当然，在某些情况下，B树 的高度指的是 包含空叶结点 的高度； 因此 B树 的具体高度还是得看具体的情况；

若 n \geq 1 ，则对任意一棵包含 n 个关键字、高度 h 、阶数 m 的 B树，在关键字总数一定的情况下，其高度 h 与关键字的个数 n 以及阶数 m 之间的关系如下：

1. 每个结点中的关键字个数达到最多，此时容纳相同数量关键字的 B树 的高度达到最小。

这是因为，对于 m阶B树 而言，每个结点中均可容纳 m - 1 个关键字，因此每个结点均有 m 棵子树。当每个结点的关键字数量最多时，说明此时的 B树 可以视为一棵 满树，那么各层的关键字个数为：

• 第一层：有 1 个结点，每个结点中有 m - 1 个关键字，共有 1 * (m - 1) 个关键字
• 第二层：有 m 个结点，每个结点中有 m - 1 个关键字，共有 m * (m - 1) 个关键字
• 第三层：有 m^2 个结点，每个结点中有 m - 1 个关键字，共有 m^2 * (m - 1) 个关键字
• \cdots
• 第 h 层：有 m^{h - 1} 个结点，每个结点中有 m - 1 个关键字，共有 m^{h - 1} * (m - 1) 个关键字

现在我们就能算得关键字的总个数 n 应该满足：

$$ \begin{align*} n &\leq (m - 1) * (1 + m + m^2 + \cdots + m^{h - 1} \ n &\leq (m - 1) * \frac{m ^h - 1}{m - 1} \ n &\leq m ^ h - 1 \ \log_m (n + 1) &\leq h \end{align*} $$

1. 每个结点中的关键字个数达到最少，此时容纳同样多关键字的 B树 的高度达到最大。

这是因为，根据 B树 的性质，每一层的结点个数以及关键字总数分别为：

• 第一层：有 1 个结点，且结点中至少有 1 个关键字，其关键字总数为 1
• 第二层：有 2 个结点，且结点中至少有 \lceil \frac{m}{2} \rceil - 1 个关键字，其关键字总数为 2 * (\lceil \frac{m}{2} \rceil - 1)
• 第三层：有 2 * (\lceil \frac{m}{2} \rceil) 个结点，且结点中至少有 \lceil \frac{m}{2} \rceil - 1 个关键字，其关键字总数为 2 * (\lceil \frac{m}{2} \rceil) * (\lceil \frac{m}{2} \rceil - 1)
• 第四层：有 2 * (\lceil \frac{m}{2} \rceil)^2 个结点，且结点中至少有 \lceil \frac{m}{2} \rceil - 1 个关键字，其关键字总数为 2 * (\lceil \frac{m}{2} \rceil)^2 * (\lceil \frac{m}{2} \rceil - 1)
• \cdots
• 第 h 层：有 2 * (\lceil \frac{m}{2} \rceil)^{h - 2} 个结点，且结点中至少有 \lceil \frac{m}{2} \rceil - 1 个关键字，其关键字总数为 2 * (\lceil \frac{m}{2} \rceil)^{h - 2} * (\lceil \frac{m}{2} \rceil - 1)

现在我们就能算得关键字的总个数应该满足：

$$ \begin{align*} n &\geq 1 + (1 + \lceil \frac{m}{2} \rceil + \lceil \frac{m}{2} \rceil^{2} + \cdots + \lceil \frac{m}{2} \rceil^{h - 2}) * 2 * (\lceil \frac{m}{2} \rceil - 1) \ n &\geq 1 + \frac{\lceil \frac{m}{2} \rceil^{h - 1} - 1}{\lceil \frac{m}{2} \rceil - 1} * 2 * (\lceil \frac{m}{2} \rceil - 1) \ n &\geq 2 * \lceil \frac{m}{2} \rceil ^ {h - 1} - 1 \ n + 1 &\geq 2 * \lceil \frac{m}{2} \rceil ^ {h - 1} \ \frac{n + 1}{2} &\geq \lceil \frac{m}{2} \rceil ^ {h - 1} \ \log_{\lceil \frac{m}{2} \rceil} \frac{n + 1}{2} &\geq h - 1 \ \log_{\lceil \frac{m}{2} \rceil} \frac{n + 1}{2} + 1 &\geq h \end{align*} $$

此时我们就得到了一棵关键字个数为 n 的 m阶B树 的高度 h 的具体范围：

结语

通过本文的探讨，我们系统性地剖析了 B树查找操作​ 的核心机制与性能特点。 B树 作为一种高效的 多路平衡查找树，其设计精髓在于通过多路分支和节点平衡，显著降低树高，从而优化大规模数据存储场景下的查询效率。 📌 核心知识点回顾

1. 查找操作的本质​

B树的查找是一个在 磁盘I/O​ 与 内存计算​ 之间交替的过程：

• 首先在磁盘上通过路径导航定位目标节点（次数等于节点所在层次）
• 再将节点读入内存进行关键字比较。
• 每个节点内的关键字有序排列，通过 顺序或二分查找 确定目标关键字或目标关键字所在子树：
  • 若在某节点找到目标关键字则立即返回成功；
  • 若到达叶子节点仍未找到则返回失败。

1. 树高与性能的数学关系​

B树 通过多路平衡设计确保树高被严格限制在对数范围内。对于包含 n 个关键字的 m阶B树，其高度 h 满足：

这一性质保证了即使数据量极大，查找时的磁盘I/O次数仍可控制在极低水平。 3. 节点内查找的决策逻辑​

节点内的查找可视为一个 动态的顺序比较过程。查找从节点的第一个关键字开始，将目标关键字与节点内的关键字依次进行有序比较，每次比较会立即导向一个明确的决策：

• 若等于当前关键字则成功返回；
• 若小于当前关键字则转入左侧子树；
• 若大于当前关键字则继续与下一个关键字比较。

此过程逐步缩小搜索范围，直至定位目标或确定路径。 🌟 下篇预告 在掌握了B树高效的查找逻辑后，我们将在下一篇文章中深入解析 B树的插入与删除操作，探讨其如何通过节点分裂、合并与关键字旋转等机制动态维持平衡结构。 互动与分享

• 点赞👍 - 您的认可是我持续创作的最大动力
• 收藏⭐ - 方便随时回顾这些重要的基础概念
• 转发↗️ - 分享给更多可能需要的朋友
• 评论💬 - 欢迎留下您的宝贵意见或想讨论的话题

感谢您的耐心阅读！ 关注博主，不错过更多技术干货。我们下一篇再见！