B 树插入

2025年3月17日 | 阅读18分钟

以下教程将讨论如何将一个键插入 B 树。此外，我们将看到在 C、C++、Java 和 Python 等不同编程语言中将键插入 B 树的一些工作示例。

但在我们开始之前，让我们简要回顾一下 B 树数据结构及其属性。

什么是 B 树？

B 树是一种自平衡二叉搜索树数据结构，它以排序形式存储和维护数据，其中根节点的左子节点值小于根节点，右子节点值大于根节点。B 树数据结构允许程序员以高效的方式搜索数据，并以对数时间处理不同的操作。它还允许节点具有两个以上的子节点。B 树的每个节点都存储键值以及指向包含该键的磁盘文件块的数据指针。B 树通常用于实现多级索引。

现在让我们来理解 B 树的一些重要属性。

B 树的属性

以下是 B 树的一些重要属性

每个节点最多有 m 个子节点，其中 m 是 B 树的阶数。
具有 K 个子节点的节点包含 K-1 个键。
除根节点外，每个非叶节点必须至少有 [m/2] 个子节点。
如果根节点不是叶节点，则至少必须有两个子节点。
与其它树不同，B 树的高度沿根节点向上增加，插入发生在叶节点。
B 树所有操作的时间复杂度为 O(log?n)，其中 'n' 是 B 树中存在的数据元素的数量。

以下是一个 4 阶 B 树的示例

图 1： 4 阶 B 树

现在让我们学习插入在 B 树中是如何工作的。

B 树中的插入操作

在 B 树中插入数据元素包含两个主要事件

搜索要插入元素的适当节点。
如果需要，拆分节点。

插入操作始终遵循自底向上（Bottom-Up）的方法。

让我们在下面理解这些事件

步骤 1：如果树为空，则分配一个根节点，然后插入键。

步骤 2：然后更新节点中允许的键数。

步骤 3：然后搜索要插入元素的适当节点。

步骤 4：如果节点已满，我们将按照下面显示的步骤进行。

步骤 4.1：按升序插入数据元素。

步骤 4.2：一旦数据元素超过其限制，我们将以中值拆分节点。

步骤 4.3：然后我们将中值键向上推，使左边的键成为左子节点，右边的键成为右子节点。

步骤 5：如果节点未满，我们将按照下面的步骤进行。

步骤 5.1：我们将按升序插入节点。

让我们通过下面的图示来理解上述步骤。

假设以下是需要插入 B 树的一些数据元素：7、8、9、10、11、16、21 和 18。

1. 由于树中节点的最高度为 3；因此，每个节点的最大键数将是 3 - 1 = 2。

2. 我们将从将数据元素 7 插入空树开始。

图 2.1：插入 7

3. 我们将把下一个数据元素，即 8，插入到树中。由于 8 大于 7，它将被插入到同一节点中 7 的右侧。

图 2.2：插入 8

4. 类似地，我们将另一个数据元素 9 插入到树中，在 8 的右侧。然而，由于每个节点最多只能有 2 个键，该节点将分裂，将中值键 8 向上推，使 7 成为左子节点的键，9 成为右子节点的键。

图 2.3：插入 9

5. 我们将把下一个数据元素，即 10，插入到树中。由于 10 大于 9，它将被插入到包含 9 作为键的节点右侧。

图 2.4：插入 10

6. 我们现在将另一个数据元素 11 插入到树中。由于 11 大于 10，它应该插入到 10 的右侧。然而，正如我们所知，每个节点最多不能超过 2 个键；因此，10 作为中值，将被推到根节点右侧的 8 旁边，将 9 和 11 分裂成两个单独的节点。

图 2.5：插入 11

7. 我们现在将数据元素 16 插入到树中。由于 16 大于 11，它将被插入到包含 11 作为键的节点右侧。

图 2.6：插入 16

8. 我们将插入到树中的下一个数据元素是 21。元素 21 应该插入到 16 的右侧；然而，这将超出每个节点的最大键数限制。因此，将发生分裂，将中值键 16 向上推，并将左侧和右侧的键分裂成单独的节点。但这将再次违反每个节点的最大键数限制；因此，将再次以中值键 10 向上推到根节点，并使 8 和 11 成为其子节点。

图 2.7：插入 21

9. 最后，我们将数据元素 18 插入到树中。由于 18 大于 16 但小于 21，它将被插入到包含 21 的节点中的左键。

图 2.8：插入 18

10. 因此，结果的 B 树将如下所示

图 2.9：结果的 B 树

将元素插入 B 树的算法

现在我们将理解我们将用于将数据元素插入 B 树的算法。

伪代码

// pseudocode to insert an element into a B Tree

Bree_Insertion(T, k)
r root[T]
if n[r] = 2 * t - 1
    s = Allocate_Node()
    root[T] = s
    leaf[s] = FALSE
    n[s] <- 0
    c1[s] <- r
    Btree_Split_Child(s, 1, r)
    Btree_Insert_Non_Full(s, k)
else Btree_Insert_Non_Full(r, k)
Btree_Insert_Non_Full(x, k)
i = n[x]
if leaf[x]
    while i >= 1 and k < key_i[x]
        key_i+1[x] = key_i[x]
        i = i - 1
    key_i+1[x] = k
    n[x] = n[x] + 1
else while i >= 1 and k < key_i[x]
        i = i - 1
    i = i + 1
    if n[c_i[x]] == 2 * t - 1
        Btree_Split_Child(x, i, c_i[x])
        if k > key_i[x]
            i = i + 1
    Btree_Insert_Non_Full(c_i[x], k)
Btree_Split_Child(x, i)
Btree_Split_Child(x, i, y)
z = Allocate_Node()
leaf[z] = leaf[y]
n[z] = t - 1
for j = 1 to t - 1
    key_j[z] = key_j + t[y]
if not leaf [y]
    for j = 1 to t
        c_j[z] = c_j + t[y]
n[y] = t - 1
for j = n[x] + 1 to i + 1
    c_j+1[x] = c_j[x]
c_i+1[x] = z
for j = n[x] to i
    key_j+1[x] = key_j[x]
key_i[x] = key_t[y]
n[x] = n[x] + 1

现在让我们看看上面伪代码在不同编程语言中的实现。

B 树插入操作示例

在下一节中，我们将看到基于上述算法在 C、C++、Java 和 Python 等不同编程语言中实现的 B 树插入操作。

C 语言中插入 B 树元素的程序

现在让我们考虑以下程序代码，说明如何在 C 语言中将数据元素插入 B 树。

程序代码

// insertion of a key in a B Tree in C Language

// including required header files
#include <stdio.h>
#include <stdlib.h>

// defining required macros
#define MAX 3
#define MIN 2

// defining the structure of the node
struct btree_node {
  int data_item[MAX + 1], counter;
  struct btree_node *the_link[MAX + 1];
};

struct btree_node *root_node;

// creating a Node
struct btree_node *create_node(int data_item, struct btree_node *child_node) {
  struct btree_node *new_node;
  new_node = (struct btree_node *)malloc(sizeof(struct btree_node));
  new_node -> data_item[1] = data_item;
  new_node -> counter = 1;
  new_node -> the_link[0] = root_node;
  new_node -> the_link[1] = child_node;
  return new_node;
}

// insert
void insert_value(int data_item, int position, struct btree_node *the_node,
          struct btree_node *child_node) {
  int j = the_node -> counter;
  while (j > position) {
    the_node -> data_item[j + 1] = the_node -> data_item[j];
    the_node -> the_link[j + 1] = the_node -> the_link[j];
    j--;
  }
  the_node -> data_item[j + 1] = data_item;
  the_node -> the_link[j + 1] = child_node;
  the_node -> counter++;
}

// splitting the node
void splitNode(int data_item, int *p_value, int position, struct btree_node *the_node,
         struct btree_node *child_node, struct btree_node **new_node) {
  int median_key, j;

  if (position > MIN)
    median_key = MIN + 1;
  else
    median_key = MIN;

  *new_node = (struct btree_node *)malloc(sizeof(struct btree_node));
  j = median_key + 1;
  while (j <= MAX) {
    (*new_node)->data_item[j - median_key] = the_node -> data_item[j];
    (*new_node)->the_link[j - median_key] = the_node -> the_link[j];
    j++;
  }
  the_node -> counter = median_key;
  (*new_node) -> counter = MAX - median_key;

  if (position <= MIN) {
    insert_value(data_item, position, the_node, child_node);
  } else {
    insert_value(data_item, position - median_key, *new_node, child_node);
  }
  *p_value = the_node -> data_item[the_node->counter];
  (*new_node) -> the_link[0] = the_node -> the_link[the_node->counter];
  the_node -> counter--;
}

// setting the value of node
int set_node_value(int data_item, int *p_value,
           struct btree_node *the_node, struct btree_node **child_node) {
  int position;
  if (!the_node) {
    *p_value = data_item;
    *child_node = NULL;
    return 1;
  }

  if (data_item < the_node -> data_item[1]) {
    position = 0;
  } else {
    for (position = the_node -> counter;
       (data_item < the_node -> data_item[position] && position > 1); position--)
      ;
    if (data_item == the_node -> data_item[position]) {
      printf("Duplicates are not allowed\n");
      return 0;
    }
  }
  if (set_node_value(data_item, p_value, the_node->the_link[position], child_node)) {
    if (the_node->counter < MAX) {
      insert_value(*p_value, position, the_node, *child_node);
    } else {
      splitNode(*p_value, p_value, position, the_node, *child_node, child_node);
      return 1;
    }
  }
  return 0;
}

// insertion operation
void insertion_operation(int data_item) {
  int the_flag, i;
  struct btree_node *child_node;

  the_flag = set_node_value(data_item, &i, root_node, &child_node);
  if (the_flag)
    root_node = create_node(i, child_node);
}

// copying the successor
void copy_successor(struct btree_node *my_node, int position) {
  struct btree_node *dummy_node;
  dummy_node = my_node -> the_link[position];

  for (; dummy_node -> the_link[0] != NULL;)
    dummy_node = dummy_node -> the_link[0];
  my_node -> data_item[position] = dummy_node -> data_item[1];
}

// performing the rightshift
void right_shift(struct btree_node *my_node, int position) {
  struct btree_node *x = my_node -> the_link[position];
  int j = x -> counter;

  while (j > 0) {
    x -> data_item[j + 1] = x -> data_item[j];
    x -> the_link[j + 1] = x -> the_link[j];
  }
  x -> data_item[1] = my_node->data_item[position];
  x -> the_link[1] = x->the_link[0];
  x -> counter++;

  x = my_node -> the_link[position - 1];
  my_node -> data_item[position] = x -> data_item[x -> counter];
  my_node -> the_link[position] = x -> the_link[x -> counter];
  x -> counter--;
  return;
}

// performing the leftshift
void left_shift(struct btree_node *my_node, int position) {
  int j = 1;
  struct btree_node *x = my_node -> the_link[position - 1];

  x -> counter++;
  x -> data_item[x -> counter] = my_node -> data_item[position];
  x -> the_link[x -> counter] = my_node -> the_link[position] -> the_link[0];

  x = my_node -> the_link[position];
  my_node -> data_item[position] = x -> data_item[1];
  x -> the_link[0] = x -> the_link[1];
  x -> counter--;

  while (j <= x -> counter) {
    x -> data_item[j] = x -> data_item[j + 1];
    x -> the_link[j] = x -> the_link[j + 1];
    j++;
  }
  return;
}

// merging the nodes
void merge_nodes(struct btree_node *my_node, int position) {
  int j = 1;
  struct btree_node *x1 = my_node -> the_link[position], *x2 = my_node -> the_link[position - 1];

  x2 -> counter++;
  x2 -> data_item[x2 -> counter] = my_node -> data_item[position];
  x2 -> the_link[x2 -> counter] = my_node -> the_link[0];

  while (j <= x1 -> counter) {
    x2 -> counter++;
    x2 -> data_item[x2 -> counter] = x1 -> data_item[j];
    x2 -> the_link[x2 -> counter] = x1 -> the_link[j];
    j++;
  }

  j = position;
  while (j < my_node -> counter) {
    my_node -> data_item[j] = my_node -> data_item[j + 1];
    my_node -> the_link[j] = my_node -> the_link[j + 1];
    j++;
  }
  my_node -> counter--;
  free(x1);
}

// adjusting the node
void adjustNode(struct btree_node *my_node, int position) {
  if (!position) {
    if (my_node -> the_link[1] -> counter > MIN) {
      left_shift(my_node, 1);
    } else {
      merge_nodes(my_node, 1);
    }
  } else {
    if (my_node -> counter != position) {
      if (my_node -> the_link[position - 1] -> counter > MIN) {
        right_shift(my_node, position);
      } else {
        if (my_node -> the_link[position + 1] -> counter > MIN) {
          left_shift(my_node, position + 1);
        } else {
          merge_nodes(my_node, position);
        }
      }
    } else {
      if (my_node -> the_link[position - 1] -> counter > MIN)
        right_shift(my_node, position);
      else
        merge_nodes(my_node, position);
    }
  }
}

// Traversing the tree
void tree_traversal(struct btree_node *my_node) {
  int i;
  if (my_node) {
    for (i = 0; i < my_node -> counter; i++) {
      tree_traversal(my_node -> the_link[i]);
      printf("%d ", my_node -> data_item[i + 1]);
    }
    tree_traversal(my_node -> the_link[i]);
  }
}

// main function
int main() {
  int data_item, ch;

  insertion_operation(4);
  insertion_operation(6);
  insertion_operation(2);
  insertion_operation(8);
  insertion_operation(10);
  insertion_operation(9);
  insertion_operation(1);
  insertion_operation(3);
  insertion_operation(12);
  insertion_operation(11);
  insertion_operation(13);

  printf("The B Tree is : ");
  tree_traversal(root_node);
}

输出

The B Tree is : 1 2 3 4 6 8 9 10 11 12 13

说明

在上面的代码片段中，我们包含了 stdio.h 和 stdlib.h 头文件，并定义了一些宏，如 MAX 和 MIN。然后我们使用 struct 关键字定义了 B 树节点的结构并创建了节点。然后我们定义了不同的函数来向节点插入值、拆分节点、设置节点的值、在 B 树中插入元素、复制后继节点、执行右移和左移、合并节点、调整节点和遍历树。然后我们定义了 main 函数来执行程序，我们在其中通过调用 insertion_operation() 函数插入了不同的元素。最后，我们调用了 tree_traversal() 函数来打印节点中的元素。

C++ 语言中插入 B 树元素的程序

现在让我们考虑以下程序代码，说明如何在 C++ 语言中将数据元素插入 B 树。

程序代码

// insertion of a key in a B Tree in C++ Language

// including the header file
#include <iostream>

// using the standard namespace
using namespace std;

// defining a class to create the structure of the BTreeNode
class BTreeNode {
  int *keys;
  int minDegree;
  BTreeNode **C;
  int n;
  bool leafNode;

   public:
    BTreeNode(int _t, bool _leafNode);

  void insert_non_full(int k);
  void split_child(int i, BTreeNode *y);
  void tree_traversal();

  friend class B_Tree;
};

// defining the class to create the B Tree
class B_Tree {
  BTreeNode *rootNode;
  int minDegree;

   public:
    B_Tree(int _t) {
     rootNode = NULL;
     minDegree = _t;
    }

  void tree_traversal() {
    if (rootNode != NULL)
      rootNode->tree_traversal();
  }

  void insertValue(int k);
};

// creating the node
BTreeNode :: BTreeNode(int tOne, bool leafOne) {
  minDegree = tOne;
  leafNode = leafOne;

  keys = new int[2 * minDegree - 1];
  C = new BTreeNode *[2 * minDegree];

  n = 0;
}

// Traversal of the nodes
void BTreeNode :: tree_traversal() {
  int i;
  for (i = 0; i < n; i++) {
    if (leafNode == false)
      C[i] -> tree_traversal();
    cout << " " << keys[i];
  }

  if (leafNode == false)
    C[i] -> tree_traversal();
}

// Insertion of the node
void B_Tree :: insertValue(int k) {
  if (rootNode == NULL) {
    rootNode = new BTreeNode(minDegree, true);
    rootNode -> keys[0] = k;
    rootNode -> n = 1;
  } else {
    if (rootNode -> n == 2 * minDegree - 1) {
      BTreeNode *s = new BTreeNode(minDegree, false);

      s -> C[0] = rootNode;

      s -> split_child(0, rootNode);

      int i = 0;
      if (s -> keys[0] < k)
        i++;
      s -> C[i] -> insert_non_full(k);

      rootNode = s;
    } else
      rootNode -> insert_non_full(k);
  }
}

// non full condition of Insertion
void BTreeNode :: insert_non_full(int k) {
  int i = n - 1;

  if (leafNode == true) {
    while (i >= 0 && keys[i] > k) {
      keys[i + 1] = keys[i];
      i--;
    }

    keys[i + 1] = k;
    n = n + 1;
  } else {
    while (i >= 0 && keys[i] > k)
      i--;

    if (C[i + 1] -> n == 2 * minDegree - 1) {
      split_child(i + 1, C[i + 1]);

      if (keys[i + 1] < k)
        i++;
    }
    C[i + 1] -> insert_non_full(k);
  }
}

// splitting the child node
void BTreeNode::split_child(int i, BTreeNode *y) {
  BTreeNode *z = new BTreeNode(y -> minDegree, y -> leafNode);
  z -> n = minDegree - 1;

  for (int j = 0; j < minDegree - 1; j++)
    z -> keys[j] = y -> keys[j + minDegree];

  if (y -> leafNode == false) {
    for (int j = 0; j < minDegree; j++)
      z -> C[j] = y -> C[j + minDegree];
  }

  y -> n = minDegree - 1;
  for (int j = n; j >= i + 1; j--)
    C[j + 1] = C[j];

  C[i + 1] = z;

  for (int j = n - 1; j >= i; j--)
    keys[j + 1] = keys[j];

  keys[i] = y -> keys[minDegree - 1];
  n = n + 1;
}

// main function
int main() {
  B_Tree tree(3);
  tree.insertValue(4);
  tree.insertValue(6);
  tree.insertValue(2);
  tree.insertValue(8);
  tree.insertValue(10);
  tree.insertValue(9);
  tree.insertValue(1);
  tree.insertValue(3);
  tree.insertValue(12);
  tree.insertValue(11);
  tree.insertValue(13);

  cout << "The B Tree is :";
  tree.tree_traversal();
}

输出

The B Tree is : 1 2 3 4 6 8 9 10 11 12 13

说明

在上面的代码片段中，我们包含了 iostream 头文件并使用了标准命名空间。然后我们定义了一个类来创建 B 树节点的结构。然后我们定义了另一个类来创建 B 树。然后我们创建了节点并定义了不同的函数来遍历树、在其上插入键、处理非满条件以及拆分子节点。最后，我们定义了 main 函数并调用 insertValue() 函数插入了不同的键到 B 树，并调用 tree_traversal() 函数打印结果树。

Java 语言中插入 B 树元素的程序

现在让我们考虑以下程序代码，说明如何在 Java 语言中将数据元素插入 B 树。

程序代码

// insertion of a key in a B Tree in Java Language

// defining the class to create B Tree
public class B_Tree {

    private int minDegree;
  
    // creation of node
    public class TheNode {
      int node;
      int keyValue[] = new int[2 * minDegree - 1];
      TheNode childNode[] = new TheNode[2 * minDegree];
      boolean leafNode = true;
  
      public int FindNode(int key) {
        for (int i = 0; i < this.node; i++) {
          if (this.keyValue[i] == key) {
            return i;
          }
        }
        return -1;
      };
    }
  
    // creation of the B minDegree 
    public B_Tree(int t) {
      minDegree = t;
      rootNode = new TheNode();
      rootNode.node = 0;
      rootNode.leafNode = true;
    }
  
    private TheNode rootNode;
  
    // splitting the node
    private void splitNode(TheNode x_node, int position, TheNode y_node) {
      TheNode z_node = new TheNode();
      z_node.leafNode = y_node.leafNode;
      z_node.node = minDegree - 1;
      for (int j = 0; j < minDegree - 1; j++) {
        z_node.keyValue[j] = y_node.keyValue[j + minDegree];
      }
      if (!y_node.leafNode) {
        for (int j = 0; j < minDegree; j++) {
          z_node.childNode[j] = y_node.childNode[j + minDegree];
        }
      }
      y_node.node = minDegree - 1;
      for (int j = x_node.node; j >= position + 1; j--) {
        x_node.childNode[j + 1] = x_node.childNode[j];
      }
      x_node.childNode[position + 1] = z_node;
  
      for (int j = x_node.node - 1; j >= position; j--) {
        x_node.keyValue[j + 1] = x_node.keyValue[j];
      }
      x_node.keyValue[position] = y_node.keyValue[minDegree - 1];
      x_node.node = x_node.node + 1;
    }
  
    // inserting key in the node
    public void insertValue(final int keyValue) {
      TheNode r = rootNode;
      if (r.node == 2 * minDegree - 1) {
        TheNode s = new TheNode();
        rootNode = s;
        s.leafNode = false;
        s.node = 0;
        s.childNode[0] = r;
        splitNode(s, 0, r);
        _insertValue(s, keyValue);
      } else {
        _insertValue(r, keyValue);
      }
    }
  
    // inserting the node
    final private void _insertValue(TheNode x_node, int key) {
  
      if (x_node.leafNode) {
        int i = 0;
        for (i = x_node.node - 1; i >= 0 && key < x_node.keyValue[i]; i--) {
          x_node.keyValue[i + 1] = x_node.keyValue[i];
        }
        x_node.keyValue[i + 1] = key;
        x_node.node = x_node.node + 1;
      } else {
        int i = 0;
        for (i = x_node.node - 1; i >= 0 && key < x_node.keyValue[i]; i--) {
        }
        ;
        i++;
        TheNode tmp = x_node.childNode[i];
        if (tmp.node == 2 * minDegree - 1) {
          splitNode(x_node, i, tmp);
          if (key > x_node.keyValue[i]) {
            i++;
          }
        }
        _insertValue(x_node.childNode[i], key);
      }
    }
  
    public void displayTree() {
      displayTree(rootNode);
    }
  
    // displayTreeing the tree
    private void displayTree(TheNode x_node) {
      assert (x_node == null);
      for (int i = 0; i < x_node.node; i++) {
        System.out.print(x_node.keyValue[i] + " ");
      }
      if (!x_node.leafNode) {
        for (int i = 0; i < x_node.node + 1; i++) {
          displayTree(x_node.childNode[i]);
        }
      }
    }
  
    // main function
    public static void main(String[] args) {
      B_Tree b = new B_Tree(3);
      b.insertValue(4);
      b.insertValue(6);
      b.insertValue(2);
      b.insertValue(8);
      b.insertValue(10);
      b.insertValue(9);
      b.insertValue(1);
      b.insertValue(3);
      b.insertValue(12);
      b.insertValue(11);
      b.insertValue(13);
  
      System.out.print("The B Tree is : ");
      b.displayTree();
    }
  }

输出

The B Tree is : 1 2 3 4 6 8 9 10 11 12 13

说明

在上面的代码片段中，我们定义了公共类来创建 B 树。在此类中，我们定义了另一个类来创建节点的结构。然后我们创建了 B 树并定义了不同的函数来拆分节点、在节点中插入键以及显示树。我们定义了 main 函数，我们在其中调用了 insertValue() 函数来在节点中插入键。最后，我们还调用了 displayTree() 函数来显示结果的 B 树。

Python 语言中插入 B 树元素的程序

现在让我们考虑以下程序代码，说明如何在 Python 语言中将数据元素插入 B 树。

程序代码

# insertion of a key in a B Tree in Python Language

# defining a class to create the structure of the B Tree node
class BTreeNode:
    def __init__(self, minDegree, leafNode):
        self.keys = [None] * (2 * minDegree - 1) # An array of keys
        self.minDegree = minDegree # Minimum degree (defines the range for number of keys)
        self.ChildPointers = [None] * (2 * minDegree) # An array of child pointers
        self.numOfKeys = 0 # Current number of keys
        self.leafNode = leafNode # Is true when node is leaf Otherwise false

    # defining a utility function to insert a
    # new key in the subtree rooted with this
    # node. The assumption is, the node must
    # be non-full when this function is called
    def insert_non_full(self, newKey):
        i = self.numOfKeys - 1
        if self.leafNode:
            while i >= 0 and self.keys[i] > newKey:
                self.keys[i + 1] = self.keys[i]
                i -= 1
            self.keys[i + 1] = newKey
            self.numOfKeys += 1
        else:
            while i >= 0 and self.keys[i] > newKey:
                i -= 1
            if self.ChildPointers[i + 1].numOfKeys == 2 * self.minDegree - 1:
                self.split_child(i + 1, self.ChildPointers[i + 1])
                if self.keys[i + 1] < newKey:
                    i += 1
            self.ChildPointers[i + 1].insert_non_full(newKey)

    # defining a utility function to split the child y_node
    # of this node. i is index of y_node in child
    # array ChildPointers[]. The Child y_node must
    # be full when this function is called
    def split_child(self, i, y_node):
        z_node = BTreeNode(y_node.minDegree, y_node.leafNode)
        z_node.numOfKeys = self.minDegree - 1
        for j in range(self.minDegree - 1):
            z_node.keys[j] = y_node.keys[j + self.minDegree]
        if not y_node.leafNode:
            for j in range(self.minDegree):
                z_node.ChildPointers[j] = y_node.ChildPointers[j + self.minDegree]
        y_node.numOfKeys = self.minDegree - 1
        for j in range(self.numOfKeys, i, -1):
            self.ChildPointers[j + 1] = self.ChildPointers[j]
        self.ChildPointers[i + 1] = z_node
        for j in range(self.numOfKeys - 1, i - 1, -1):
            self.keys[j + 1] = self.keys[j]
        self.keys[i] = y_node.keys[self.minDegree - 1]
        self.numOfKeys += 1

    # defining a function to traverse all nodes in a subtree
    # rooted with this node
    def tree_traversal(self):
        for i in range(self.numOfKeys):
            if not self.leafNode:
                self.ChildPointers[i].tree_traversal()
            print(self.keys[i], end = ' ')
        if not self.leafNode:
            self.ChildPointers[i + 1].tree_traversal()

# defining a class to create a B Tree
class B_Tree:
    def __init__(self, minDegree):
        self.root_node = None # Pointer to root node
        self.minDegree = minDegree # Minimum degree

    # defining a function to traverse the tree
    def tree_traversal(self):
        if self.root_node != None:
            self.root_node.tree_traversal()

    # The main function that inserts a new key in this B Tree
    def insertValue(self, newKey):
        if self.root_node == None:
            self.root_node = BTreeNode(self.minDegree, True)
            self.root_node.keys[0] = newKey
            self.root_node.numOfKeys = 1
        else:
            if self.root_node.numOfKeys == 2 * self.minDegree - 1:
                s = BTreeNode(self.minDegree, False)
                s.ChildPointers[0] = self.root_node
                s.split_child(0, self.root_node)
                i = 0
                if s.keys[0] < newKey:
                    i += 1
                s.ChildPointers[i].insert_non_full(newKey)
                self.root_node = s
            else:
                self.root_node.insert_non_full(newKey)
                
# main function
if __name__ == '__main__':
    minDegree = B_Tree(3)
    minDegree.insertValue(4)
    minDegree.insertValue(6)
    minDegree.insertValue(2)
    minDegree.insertValue(8)
    minDegree.insertValue(10)
    minDegree.insertValue(9)
    minDegree.insertValue(1)
    minDegree.insertValue(3)
    minDegree.insertValue(12)
    minDegree.insertValue(11)
    minDegree.insertValue(13)

    print("The B Tree is :", end = ' ')
    minDegree.tree_traversal()

输出

The B Tree is : 1 2 3 4 6 8 9 10 11 12 13

说明

在上面的代码片段中，我们定义了一个类来创建 B 树节点的结构。在此类中，我们声明了必要的变量并定义了一些函数，例如向以该特定节点为根的子树插入新键的函数、拆分子节点以及遍历树的函数。然后我们定义了另一个类来创建 B 树。在此类中，我们初始化了一些变量并定义了不同的函数，例如遍历树和向节点插入值的函数。最后，我们定义了 main 函数，我们在其中使用 insertValue() 函数将不同的键插入到树中，并通过调用 tree_traversal() 函数打印结果树。

B 树插入操作的时间复杂度取决于节点的数量，因此是 O(log n)。

结论

在本教程中，我们学习了 B 树插入操作的基础知识。我们还讨论了在 B 树中执行键插入的算法及其在 C、C++、Java 和 Python 等不同编程语言中的实现。

下一主题后缀表示法的求值

← 上一个下一个 →

B 树插入

什么是 B 树？

B 树的属性

B 树中的插入操作

将元素插入 B 树的算法

B 树插入操作示例

C 语言中插入 B 树元素的程序

C++ 语言中插入 B 树元素的程序

Java 语言中插入 B 树元素的程序

Python 语言中插入 B 树元素的程序

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

B 树插入

什么是 B 树？

B 树的属性

B 树中的插入操作

将元素插入 B 树的算法

B 树插入操作示例

C 语言中插入 B 树元素的程序

C++ 语言中插入 B 树元素的程序

Java 语言中插入 B 树元素的程序

Python 语言中插入 B 树元素的程序

结论

相关帖子

循环链表导论和应用

DSA 中的无额外空间合并问题

列表数据结构

二叉搜索树 vs 三元搜索树

找出最后一个拿到票的人（队列中的问题）

堆与树的比较

以最小成本连接 n 根绳子

N 元树的序列化和反序列化

握手引理和有趣的树属性

使用 Python 对矩阵数据结构执行不同操作

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器