树形查找

真题练习：可在站内题库按“B 树”知识点筛选。

在选择题中会考查，重点掌握两点：1. m 阶 B 树的特性。2. B 树和 B+ 树的不同点和适用场景。

基于 BST 的查找

在二叉查找树以及它的改进版本 AVL 树、红黑树中，查找操作都遵循相同的基本原则：利用 二叉树的有序性 来快速定位目标元素。

复习以下，二叉查找树具备以下特点：

左子树中所有节点的值小于根节点的值。
右子树中所有节点的值大于根节点的值。
这种「左小右大」的有序性，使得查找可以逐层缩小范围。

所以在基于二叉查找树进行查找时，过程如下：

从 根节点 开始。
如果查询的值等于当前节点的值，返回 当前节点。
如果查询的值小于当前节点的值，向 左子树 查询。
如果查询的值大于当前节点的值，向 右子树 查询。
如果到达 空节点，则查询失败，返回 NULL。

查找过程可以通过以下图示进行理解：

BST 查找时间复杂度分析

查找操作的时间复杂度，取决于树的高度（Height）：

树的高度越小，查找路径越短，效率越高。
树的高度越大（越“瘦长”），查找路径越长，效率越低。

树类型	平均情况时间复杂度	最坏情况时间复杂度	说明
BST	$O(\log_2 n)$	$O(n)$	如果树接近平衡，高度约为 $\log_2 n$ ；但若不断插入有序数据，可能退化为链表。
AVL	$O(\log_2 n)$	$O(\log_2 n)$	通过严格的平衡条件保证树高始终在 $\log_2 n$ 量级。
红黑树	$O(\log_2 n)$	$O(\log_2 n)$	平衡条件比 AVL 宽松，但仍能保证树高不超过 $2\log_2(n+1)$ 。

B 树

B 树，也叫做多路平衡查找树。是一种自平衡的树形数据结构，它广泛应用于数据库和文件系统中，用于高效地存储和检索大量有序数据。

特性

B 树具备以下两个主要特点：

多路搜索树：B 树是一种多路搜索树，意味着每个节点可以拥有多个子节点，而不仅仅是两个（如二叉搜索树）。
- 阶（Order）：B 树的阶定义了每个节点可以拥有的 最大子节点数。
平衡性：B 树通过保持所有叶子节点在同一层，确保了树的平衡，从而保证了搜索效率。

一颗 m 阶 B 树，满足如下特性：

树中每个结点最多有 $m$ 棵子树，最多有 $m-1$ 个 关键字。
若 根节点 不是 叶子结点，至少有两个子树。
除了 根节点 外的所有 非叶结点 最少有 $\lceil m/2\rceil$ 棵子树，即最少有 $\lceil m/2\rceil-1$ 个 关键字。

注意

对于 3 阶 B 树，阶数 $m=3$ ，最小键数为

\left\lceil\frac{m}{2}\right\rceil-1=2-1=1.

3 阶 B 树的非根节点（包括 叶子节点 和内部节点）最少有 1 个关键字。

对于 5 阶 B 树，阶数 $m=5$ ，最小键数为

\left\lceil\frac{m}{2}\right\rceil-1=3-1=2.

5 阶 B 树的非根节点（包括 叶子节点 和内部节点）最少有 2 个关键字。

B 树结点结构如下：

其中

$n$ 为结点中 关键字 的个数；
$K_i\ (i=1,2,\ldots,n)$ 为结点中存储的 关键字，且满足 $K_1<K_2<\cdots<K_n$ ；
$P_i\ (i=0,1,\ldots,n)$ 为指向子树根结点的指针，且指针 $P_{i-1}$ 所指子树中所有关键字均小于 $K_i$ ， $P_i$ 所指子树中所有关键字均大于 $K_i$ 。

以上图中的 5 阶 B 树 为例，说明 B 树的性质：

结点中的 孩子个数 等于结点中 关键字 的个数加 1。
除根节点外所有 非叶子结点 最少有 $\lceil m/2\rceil=\lceil5/2\rceil=3$ 棵子树（2 个 关键字），最多有 5 棵子树（4 个 关键字）。
结点中 关键字 从左到右递增有序，关键字左侧指针所指子树的所有关键字均小于该关键字，右侧指针所指子树的所有关键字均大于该关键字。

提示

关于 B 树的查找、插入、删除操作，可以借助 B 树交互演示来帮助自己理解。

查找

B 树查找与普通二叉查找树相似，但在每个节点上，需要进行多次比较。

从 根节点 开始：
- 检查当前节点的键列表，键按升序排列。
- 比较目标键 $k$ 与节点中的键 $k_i$ ：
  - 如果 $k=k_i$ ，找到目标键，返回对应的值（若存储 KV 对）。
  - 如果 $k<k_1$ （第一个键），选择最左子节点。
  - 如果 $k_i<k<k_{i+1}$ ，选择 $k_i$ 和 $k_{i+1}$ 之间的子节点。
  - 如果 $k>k_n$ （最后一个键），选择最右子节点。
递归向下：
- 根据比较结果，进入选定的 子节点。
- 重复步骤 1，直到到达 叶节点 或找到目标键。
处理结果：
- 在节点中找到键：返回对应的值（或指针）。
- 到达 叶节点 仍未找到：键不存在，返回空或失败标志。

注意：B 树允许键出现在内部节点，因此查找可能在内部节点结束，而无需到达 叶节点。

插入

B 树的插入过程如下所示：

查找关键字位置：
- 从 根结点 开始，比较键值与节点中的键，选择合适的 子节点 继续递归向下，直到找到合适的 叶节点（插入点）。
- B 树的所有插入操作 都在叶节点进行。
插入关键字：
- 将新键插入到 叶节点 的正确位置（保持键的有序性）。
- 如果插入后 叶节点 的键数量不超过最大限制（ m−1 ），插入完成，过程结束。
- 如果插入后键数量超过 m−1 （即节点溢出），需要进行分裂。
节点分裂：
- 假设节点有 m 个键（超限），将其分裂为两个新节点：
  - 取中间键（第 ⌈m/2⌉ 个键）作为分隔键。
  - 分隔键上移到 父节点。
  - 原节点分裂为两个新节点，分别包含中间键之前的键和之后的键。
- 每个新节点的键数量约为 ⌈m/2⌉−1 （满足 B 树的最小键数要求）。
- 子节点指针也相应分配到两个新节点。

更新 父节点
- 将中间键插入到 父节点 中（保持有序）。
- 如果 父节点 插入后也溢出，对 父节点 重复分裂操作（步骤 3）。
- 分裂 可能递归向上传播，直到某个节点不再溢出或创建新的 根节点。
  - 如果 根结点 分裂的话，则树的层数会增加一层。

下图展示了一个三阶 B 树的多次插入过程：

图示校正：三阶 B 树的同一结点内，关键字必须从小到大排列。因此图中插入 52 后的根结点应写成 [52, 78]，不是图中画出的 [78, 52]；后续分裂结果不受这个排版错误影响。旧图保留用于对照，下面的交互轨迹采用正确顺序。

执行轨迹

三阶 B 树连续插入时何时分裂

依次点击原图中的九个插入键，观察叶结点扩容、关键字上移与树高增加发生在哪一步。

078152281340433590685720838

插入 78空树形成只含关键字 [78] 的根结点。

删除

B 树的删除过程如下所示：

查找关键字：首先查找要删除的关键字 k 。
- 叶子节点中的关键字：
  - 如果键 k 在 叶子节点，且节点键数大于 ⌈m/2⌉−1 （最小键数），直接删除 k 。
  - 如果节点键数等于 ⌈m/2⌉−1 ，删除后会导致键数不足，需进行修复（步骤 2）。
- 内部节点中的关键字：
  - 找到 k 的前驱或后继键（通常是左子树的最大键或右子树的最小键，位于 叶子节点）。用前驱/后继键替换 k ，然后在 叶子节点 中删除该前驱/后继键。
  - 如果替换后 叶子节点 键数不足，需修复（步骤 2）。
节点键数不足的修复：当删除键后，节点键数少于 ⌈m/2⌉−1 ，需要调整以恢复 B 树性质：
- 借键：如果左/右兄弟节点有多余键，借一个
  - 从 父节点 取一个键到当前节点。
  - 从兄弟节点取一个键到 父节点，相应调整子树指针。
- 合并：如果兄弟节点也没有多余键：
  - 将当前节点与一个兄弟节点合并。
  - 从 父节点 取一个键作为合并节点的中间键。
  - 更新 父节点 的键和指针。
  - 如果 父节点 键数不足，递归对 父节点 应用修复。
递归处理
- 删除操作可能引发多层节点调整，需递归处理 父节点 的键数不足问题，直到满足 B 树性质或到达 根节点。

特殊情况：删除操作可能引发多层节点调整，需递归处理 父节点 的键数不足问题，直到满足 B 树性质或到达 根节点。

下面以 3 阶 B 树 为例说明一下删除的多种情况：

提示

B 树删除过程细节过多，这里建议还是和学习平衡二叉树时采用相同方法，通过实际例子建立直觉即可。

B+ 树

在实际应用中，B 树 和 B+ 树 通常存储的是键值对（Key-Value），例如在数据库索引或文件系统中，键用于定位记录，值可以是数据本身或指向数据的指针。在上文关于 B 树的说明中，为了突出算法逻辑，我们将 B 树中的元素表示为单个键，省略值的部分。

实际上存储有 KV 对 的 B 树 的结构如下图所示：

B+ 树是 B 树 的一种扩展。在 B+ 树 中，只有 叶子节点 存储数据，而内部节点只存储键。所有的数据记录都存储在 叶子节点 中，并且 叶子节点 通过指针连接形成一个有序链表，如下图所示：

特性

一颗 m 阶 B+ 树满足如下条件：

节点的容量限制
- 每个 非叶子节点（分支节点）最多有 m 棵子树。
- 除 根节点 外，每个 非叶子节点 至少有 $\lceil m/2\rceil$ 棵子树。
关键字与子树的关系
- 按 408 常用定义，在一个 非叶子节点 中，如果有 $k$ 棵子树，那么它有 $k$ 个关键字；每个关键字通常是对应子树中最大关键字（也有实现采用最小关键字）的副本。
- 关键字起到索引与分隔值域的作用，子树对应这些分隔区间。
数据存储位置
- 所有 数据记录（或指向数据的指针）都存储在 叶子节点 中。
- 非叶子节点 只存储关键字，用于索引和导航，不直接存放数据。
叶子节点的顺序结构
- 所有 叶子节点 之间通过链表指针相连。
- 这种顺序结构可以支持高效的范围查询和顺序遍历。

操作

B+ 树的操作考察不多，了解与 B 树相应操作的不同之处即可：

查找：
- B 树：所有节点（包括内部节点）存储 KV 对，查找可能在内部节点结束。
- B+ 树：只有 叶节点 存储 KV 对，查找必须到达 叶节点。
插入：
- B 树：所有节点存储 KV 对，分裂时中间键值对整体上移。
- B+ 树：只有 叶节点 存储 KV 对，分裂时中间键复制到 父节点（仅键，不带值），叶节点保留所有键。
删除：
- B 树：内部节点存储 KV 对，删除内部节点键需用后继/前驱替换，可能复杂。
- B+ 树：删除只发生在 叶节点，内部节点键仅需调整（复制 叶节点 键），操作更简单。

B 树和 B+ 树对比

特性	B 树	B+ 树
数据存储位置	关键字和数据存在于内部结点和叶结点	所有数据都存储在叶结点，内部结点只保存索引关键字和子结点指针
叶结点结构	叶结点与内部结点类似，保存关键字和数据	所有叶结点通过指针链接成有序链表
分支因子	由于同时保存数据和关键字，通常较小	内部结点只保存关键字和指针，通常更大
稳定性	关键字位置可能随分裂、合并而变动	数据记录始终位于叶结点，位置相对稳定
应用场景	适用于需要在内部结点直接命中的场景	更常见于大型数据库系统和文件系统
查找效率	在内部结点找到关键字后即可结束	必须到达叶结点，但通常树高更低，且范围查询更高效

画 B 树题时的核对顺序

先固定题目采用的“(m) 阶”定义，再同时检查每个结点的孩子数、关键字数、关键字递增顺序和所有叶子层数。对非根结点，孩子数范围为 $\lceil m/2\rceil$ 到 (m)，关键字数随之为 $\lceil m/2\rceil-1$ 到 (m-1)；根结点是例外，非叶根至少有两棵子树。插入出现溢出时，是中间分隔键上移；删除不足时，先看能否向相邻兄弟借键，再考虑与兄弟及父分隔键合并。

比较 B 树和 B+ 树时，尤其不能把“内部结点是否存放实际记录”“查找是否一定走到叶结点”“叶子是否有链表”三件事混在一起。遇到不同教材的 B+ 树关键字复制规则，优先遵循题设图和定义，不用另一套约定反推孩子范围。

多路查找树的范围查询与调整核对

B 树的高度随记录数按对数增长，原因是除根外的每个非叶结点至少保有 $\lceil m/2\rceil$ 个孩子，所有叶结点又必须在同一层。实际高度还取决于结点是否接近满载：孩子数越多、一次磁盘访问可比较的关键字越多，树越矮。题目若给出“阶”的定义，应优先据此写出孩子数与关键字数的上下界；不同教材对 B+ 树内部关键字个数的约定可能不同，不能只凭记忆互换。

范围查询体现 B+ 树的优势。查找下界键时，先沿内部索引走到对应叶结点，再顺着叶结点的有序链表持续读取，直到超过上界即可；不需要每取一条记录就重新从根查找。B 树的叶结点通常没有这样的顺序链表，且记录可能分散在内部结点与叶结点，连续扫描的局部性较弱。内部索引中的分隔键是叶结点真实键的复制或边界摘要，不应把“内部出现同值”误认为同一条数据记录被存了两次。

删除时的借键方向也要保持整体有序。若向左兄弟借，通常把父结点分隔键下移到当前结点的最前面，再把左兄弟最大的键上移替换父分隔键；若向右兄弟借，则把父分隔键追加到当前结点末尾，再把右兄弟最小的键上移。两种情况都要同步移动相邻子树指针。若兄弟没有多余键，合并时要把父分隔键放在两组键之间；父结点随后可能不足并继续向上修复，根结点成为空根时才会使树高下降一层。

画图或验算操作后，按这个顺序检查最稳妥：每个结点内关键字递增；每个指针覆盖正确的值域；非根结点满足最小、最大容量；所有叶结点同层；最后再检查 B+ 树叶链是否仍按关键字升序完整相连。只检查结点里“看起来有几个键”而忽略值域与叶层，容易漏掉本质错误。