B-树特点以及插入、删除数据过程

🕗 发布于 2024-11-15 09:59 b树 数据结构

B树（B-Tree）是一种自平衡的多路查找树，它广泛应用于数据库索引和文件系统中，尤其适用于外部存储设备（如磁盘）。B树的设计使得它能够高效地存储大量数据并支持高效的插入、删除和查询操作。以下是B树的主要特点，详细解释其结构和行为：

特点

1. 多路平衡树

B树是一个多路平衡查找树，不同于传统的二叉树。它的每个节点可以有多个子节点，而不仅限于两个。具体来说，B树的阶数（degree）决定了每个节点的子节点的数量上限。

阶数（m）：B树的阶数m是一个重要的参数，表示每个节点最多可以有m个子节点，最多可以存储m-1个键值；父节点最少2个子节点，1一个元素；非父节点最少可以有[m/2]个子节点，[m/2]-1个元素。 注意[m/2]向上取整。
节点结构：每个节点包含多个元素和指向子节点的指针。例如，阶数为m的B树中，一个节点最多包含m-1个键值和m个子节点指针。节点的元素按升序排列，子节点指针在元素之间。
键值：每个节点保存若干个数据项（键），这些键在节点内按升序排列。
指针：每个节点有若干个指针，指向其子节点。一个包含k个键的节点，会有k+1个指针。

2. 平衡性

B树保证了树的平衡性——所有叶子节点都在同一层。这意味着树的高度保持平衡，不会出现偏向某一边的情况，因此，B树能够提供对数时间的查找、插入和删除操作。

高度平衡：从根到任意叶子节点的路径长度相同。这是B树在性能上优于一般二叉树的一个重要特性。因为高度较小，B树的查找效率很高。

3. 有序性

B树的节点内存储的数据是有序的，并且节点之间也保持严格的顺序关系。具体地：

节点内的键值是按升序排列的。
对于节点的每个子节点指针，指向的子树中的键值均满足：
子节点左边的键值小于当前节点的键值。
子节点右边的键值大于当前节点的键值。
这种有序性使得B树能够高效地进行范围查询和逐个访问数据。

4. 每个节点最多存储多个键

B树的每个节点可以存储多个键，这意味着B树的每个节点能够包含大量的数据。这一特点使得B树可以在减少树的高度的同时，增加单次磁盘I/O操作的数据量，从而提高查询效率。

节点的最大容量：在阶数为m的B树中，每个节点最多包含m-1个键。节点的最小容量（也就是每个节点最少存储的键数）为⌈m / 2⌉ - 1个键。
例如，阶数为3的B树（m=3），每个节点最多存储2个键（即m-1），每个节点至少存储1个键（即⌈m / 2⌉ - 1）。

插入数据

B树的插入操作详解

B树的插入操作用于将一个新的元素插入到树中的适当位置，并确保B树的平衡性。在插入过程中，B树保持自平衡的特性，确保所有叶子节点都在同一层，并且每个节点的键数量不超过规定的最大值，同时不低于最小值。如果插入操作导致节点超出了容量，就会触发节点分裂操作。

插入操作步骤

B树插入操作可以分为几个主要步骤：

查找插入位置
首先，进行标准的查找操作，找到待插入元素应插入的位置。插入位置是在叶子节点中，B树通过比较每个节点内的键值确定插入位置。如果目标键值已存在，则不进行插入（具体行为取决于实现方式，有的实现会更新已有元素）。
在叶子节点插入元素
一旦找到了适当的插入位置（即叶子节点），并且该叶子节点有足够的空间（即未达到节点的最大容量），我们直接将新的元素插入到该叶子节点中。
检查是否需要分裂
如果插入的元素使叶子节点的元素数目超过最大容量（即达到m个键值），则需要进行节点分裂操作。分裂过程的关键是：
- 将该节点的中间元素移到父节点。
- 将节点分裂成两个子节点，一个包含左半部分的键，另一个包含右半部分的键。
递归分裂父节点（如有需要）
分裂操作会将中间元素推送到父节点。如果父节点也满了（即包含了m-1个键值），则需要递归地对父节点进行分裂，直到找到一个可以容纳新元素的节点。如果根节点也被分裂，则树的高度会增加。
根节点分裂
如果根节点发生分裂，树的高度会增加，新的根节点会创建出来，并包含分裂后的两个子节点和一个键值。这样，树的高度增加了一层。

插入操作的详细步骤与图示

以阶数为3的B树为例，假设一个B树的阶数m=3，即每个节点最多可以存储2个元素，最多有3个子节点。初始树如下所示：

        [10]
       /    \
   [5]       [15]

假设我们要插入元素7。

查找插入位置：
从根节点[10]开始，7小于10，因此进入左子树[5]。由于7大于5，插入位置就是[5]节点中。
插入元素到叶子节点：
将元素7插入到叶子节点[5]中，得到：
```
[5, 7]
```
检查是否需要分裂：
节点[5, 7]包含2个元素，未超过最大容量，因此无需分裂。

插入后的树仍然是平衡的，没有改变结构：

        [10]
       /    \
   [5, 7]    [15]

插入导致节点分裂的情况

假设我们现在要插入元素3，并继续使用阶数m=3的B树。当前树结构为：

        [10]
       /    \
   [5, 7]    [15]

查找插入位置：
从根节点[10]开始，3小于10，进入左子树[5, 7]。由于3小于5，插入位置就是[5, 7]节点的左边。
插入元素到叶子节点：
将元素3插入到叶子节点[5, 7]，得到：
```
[3, 5, 7]
```
检查是否需要分裂：
节点[3, 5, 7]已经包含3个元素，超过了该节点的最大容量（2个元素）。因此，节点需要分裂。
节点分裂：
- 将节点[3, 5, 7]分裂为两个节点：
  - 左边节点[3]
  - 右边节点[7]
- 将中间元素5上移到父节点[10]。

分裂后的树结构如下：

        [5, 10]
       /    |    \
   [3]    [5]    [7, 15]

插入操作完成，树的结构发生了改变，原先的叶子节点被分裂，父节点也增加了一个元素。

递归分裂操作

在一些情况下，插入操作可能导致父节点也满了，进而需要递归分裂。假设我们现在有一个阶数为m=3的B树，当前结构如下：

            [20]
           /    \
     [10, 15]    [25, 30]

我们要插入元素17。

查找插入位置：
从根节点[20]开始，17小于20，进入左子树[10, 15]。由于17大于15，插入位置是[10, 15]节点的右边。
插入元素到叶子节点：
将元素17插入到叶子节点[10, 15]中，得到：
```
[10, 15, 17]
```
检查是否需要分裂：
节点[10, 15, 17]包含3个元素，超过了节点的最大容量（2个元素），因此需要分裂。
节点分裂：
- 将节点[10, 15, 17]分裂为两个节点：
  - 左边节点[10, 15]
  - 右边节点[17]
- 将中间元素15上移到父节点[20]。

此时，父节点[20]变为[15, 20]，树结构变为：

            [15, 20]
           /    |    \
     [10]    [15]    [17, 25, 30]

注意，这里[20]的父节点分裂后增加了新的元素。

总结

B树的插入操作包含以下几个核心步骤：

查找插入位置：通过树的层级结构，从根节点到叶子节点进行查找，确定插入位置。
插入元素：如果目标叶子节点有空间，直接插入元素。
节点分裂：如果插入导致节点超出最大容量，将节点分裂并将中间元素推送到父节点。
递归分裂：如果父节点也满了，递归地进行分裂，直到找到可以容纳元素的父节点，或者根节点发生分裂，增加树的高度。

在这里插入图片描述

插入操作保证了B树的平衡性，使得查询、插入和删除操作始终保持对数时间复杂度O(log n)。

删除数据

B树的删除操作详解

B树的删除操作不仅需要删除目标元素，还要保证树的平衡性。删除操作可能会导致节点的元素数量低于最小容量，这时需要通过借用或合并操作来恢复树的平衡。

B树的删除操作可以分为以下几个步骤：

查找待删除元素：首先通过标准的查找操作找到要删除的元素。
删除元素：如果待删除的元素在叶子节点，直接删除；如果在内部节点，则需要借用或合并来处理。
借用或合并节点：删除元素后，某些节点可能会变得“不满”（即元素数少于最小容量），需要通过借用兄弟节点的元素或将当前节点与兄弟节点合并来维持B树的性质。

具体步骤和情况如下：

B树删除操作的基本步骤

1. 删除叶子节点的元素

如果待删除的元素位于叶子节点，并且该节点中元素的数量大于或等于B树规定的最小数量（即⌈m / 2⌉ - 1个键），可以直接删除该元素。
不需要进行合并或借用，树结构不会发生变化。

2. 删除内部节点的元素

如果待删除的元素位于非叶子节点，情况就更复杂，通常有以下几种处理方式：

替换删除元素：首先，找到待删除元素的前驱或后继元素（通常是该节点左子树的最大元素或右子树的最小元素），并将其替换待删除的元素。然后，删除该前驱或后继元素。这转化为一个在叶子节点删除元素的问题。
删除替代元素并调整：一旦替代元素被删除，我们可以继续执行删除操作，并根据需要调整树的结构。

3. 恢复树的平衡

删除元素后，如果某个节点的元素数小于最小数量（即节点的键数小于⌈m / 2⌉ - 1），则需要恢复树的平衡性。常见的恢复方法包括：

借用操作：从相邻的兄弟节点借用元素。如果兄弟节点有多余的元素，借用一个元素并将其父节点的元素下移。借用后的兄弟节点和当前节点会重新调整，保持平衡。
合并操作：如果相邻的兄弟节点没有多余的元素可借用，则需要将当前节点与兄弟节点合并，合并后的节点元素数会增加，父节点的元素数减少。如果父节点的元素数低于最小数量，则继续向上调整。

删除操作的各种情况

我们通过一个阶数为m = 3的B树来逐步讲解删除操作的不同情况。

示例B树结构

假设当前的B树结构如下（阶数为3，最多可以存储2个元素）：

              [30]
             /    \
     [10, 20]      [40, 50]
      /    \        /    \
  [5]      [15]  [35]   [45, 60]

假设我们需要删除元素20。

情况一：删除叶子节点的元素

查找位置：元素20位于叶子节点[10, 20]中。
删除：删除20后，节点变为[10]，此时该节点的元素数大于或等于最小容量（即1个元素，满足最小容量2个元素的一半），因此无需调整树结构。

              [30]
             /    \
     [10]          [40, 50]
      /    \        /    \
  [5]      [15]  [35]   [45, 60]

情况二：删除内部节点的元素，且使用替代

假设我们需要删除元素30，这个元素位于根节点。

查找替代元素：为了删除30，我们找到30的前驱元素，即其左子树的最大元素20，然后将20替换掉30。
删除替代元素：元素20已经被删除，原来的节点[10, 20]成为[10]。
由于没有发生分裂和合并，树的结构保持不变。

最终树结构变为：

              [20]
             /    \
     [10]          [40, 50]
      /    \        /    \
  [5]      [15]  [35]   [45, 60]

情况三：删除元素导致节点不满，借用兄弟节点的元素

假设我们删除元素15，它位于叶子节点[5, 15]。

查找元素并删除：删除元素15后，节点[5]剩余一个元素，已经少于最小容量（1个元素，最小容量应该是1个元素）。
借用兄弟节点：我们可以借用右兄弟节点[20]中的元素，将其右边的元素20移动到父节点30中，并将父节点的指针更新。这样，节点[5]会得到补充，变为[5, 10]。

树结构如下：

              [30]
             /    \
     [5, 10]       [40, 50]
      /    \        /    \
  [5]      [15]  [35]   [45, 60]

情况四：删除元素导致节点不满，合并操作

假设我们删除元素5，元素5位于[5, 10]。

查找位置并删除：删除5后，节点[10]只剩下1个元素，低于最小容量，需要恢复平衡。
合并操作：由于右兄弟[15]有元素，可以进行合并。我们将[10]和[15]合并为一个节点[10, 15]。
更新父节点：父节点[30]中，10和15会更新为30，但是由于节点合并没有变化，所以树的结构将被调整。