树形查找

基于 BST 的查找

BST, AVL, 红黑树定义

使用 BST、AVL 或红黑树来存储数据，查询方式如下：

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

对于 BST，如果树是极度不平衡的（例如，成为链状结构），查询的最坏时间复杂度为 O(n)。

B 树

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

特性

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

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

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

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

B 树结点结构如下：

其中

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

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

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

查找

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

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

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

插入

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

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

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

删除

删除操作较为复杂，需要考虑多种情况。

1. 查找关键字：首先查找要删除的关键字 $k$ 。
   • 叶子节点中的关键字：如果关键字 $k$ 在叶子节点中，直接删除。
   • 内部节点中的关键字：
     • 如果 $k$ 的前驱关键字在叶子节点中，找到 $k$ 的前驱关键字，删除它，并在内部节点中用它替换 $k$ 。
     • 否则，使用类似的方法与 $k$ 的后继关键字。
     • 如果都不行，必须合并节点并递归地删除 $k$ 。
2. 合并节点：如果一个节点在删除后少于 $t-1$ 个关键字，那么它就太小了，需要进行合并或关键字借用操作：
   • 从兄弟节点借用一个关键字。
   • 如果无法借用，就和兄弟节点合并。
3. 递归删除：合并操作可能需要递归到树的上一层。
4. 更新根节点：如果根节点没有关键字，且只有一个子节点，那么那个子节点成为新的根节点。

B+树

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

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

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

特性

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

• 每个分支结点最多有 m 颗子树
• 结点的子树个数和关键字个数相同
• 所有的值都出现在叶子节点，内部节点只包含键不包含实际的数据。
• 叶子节点通过指针相互连接，这为范围查询提供了高效性。
• 由于内部节点不存储数据，因此每个内部节点可以存储更多的键，从而增加树的扇出，减少树的高度。

操作

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

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

B 和 B+ 树对比