数据结构和算法 - B 树

B 树是扩展的二叉搜索树，专门用于 m 路搜索，因为 B 树的顺序是“m”。树的阶数定义为节点可以容纳的最大子节点数。因此，ab树的高度相对小于AVL树和RB树的高度。

它们是二叉搜索树的一般形式，因为它包含多个键和两个子项。

B 树的各种属性包括 -

B 树中的每个节点最多可容纳 m 个子节点和 (m-1) 个键，因为树的顺序为 m。
B 树中的每个节点（除了根和叶）至少可以容纳 m/2 个子节点
根节点必须有不少于两个子节点。
B树中的所有路径必须在同一层结束，即叶节点必须在同一层。
AB 树始终维护排序的数据。

B树也广泛应用于磁盘访问，由于ab树的高度较低，可以最大限度地减少磁盘访问时间。

注- 磁盘访问是对存储信息的计算机磁盘的内存访问，磁盘访问时间是系统访问磁盘内存所花费的时间。

B树的基本操作

B树支持的操作有插入、删除和搜索，每个操作的时间复杂度为O(log n) 。

插入

B 树的插入操作与二叉搜索树类似，但元素被插入到同一节点中，直到达到最大键数。插入是使用以下过程完成的 -

步骤 1 - 计算最大值 $\mathrm{\left ( m-1 \right )}$ 和最小值 $\mathrm{\left ( \left \lceil \frac{m}{2}\right \rceil-1 \right )}$ 一个节点可以保存的键的数量，其中 m 由 B 树的阶数表示。

步骤 2 - 使用二分搜索插入将数据插入到树中，一旦键达到最大数量，节点就会分成两半，中间键成为内部节点，而左右键成为其子节点。

步骤 3 - 所有叶节点必须位于同一级别。

键 5、3、21、9、13 都根据二分查找属性添加到节点中，但如果我们添加键 22，则会违反最大键属性。因此，节点被分成两半，中值键被转移到父节点，然后继续插入。

在插入 11 的过程中发生了另一个问题，因此该节点被分裂，中位数被转移到父节点。

当插入16时，即使节点被分成两部分，父节点也会因为达到最大键值而溢出。因此，父节点首先被分裂，中值键成为根。然后，叶节点被分成两半，叶节点的中位数移至其父节点。

插入所有元素后就得到了最终的B树。

例子

// Insert the value
void insertion(int item) {
   int flag, i;
   struct btreeNode *child;
   flag = setNodeValue(item, &i, root, &child);
   if (flag)
      root = createNode(i, child);
}

删除

B树中的删除操作与二叉搜索树的删除操作略有不同。从 B 树中删除节点的过程如下 -

情况 1 - 如果要删除的键位于叶节点中，并且删除不违反最小键属性，则只需删除该节点。

情况 2 - 如果要删除的键位于叶节点中，但删除违反了最小键属性，则从其左同级或右同级借用键。如果两个同级节点都有确切的最小数量的键，则合并其中一个节点中的节点。

情况 3 - 如果要删除的键位于内部节点中，则根据哪个子节点拥有更多键，将其替换为左子节点或右子节点中的键。但如果两个子节点都有最小数量的键，它们就会合并在一起。

情况 4 - 如果要删除的键位于违反最小键属性的内部节点中，并且其子节点和兄弟节点都具有最小数量的键，则合并子节点。然后将其兄弟与其父级合并。

以下是 B 树中删除操作的功能 C++ 代码片段 -

// Deletion operation
void deletion(int key){
   int index = searchkey(key);
   if (index < n && keys[index] == key) {
      if (leaf)
         deletion_at_leaf(index);
      else
         deletion_at_nonleaf(index);
   } else {
      if (leaf) {
         cout << "key " << key << " does not exist in the tree\n";
         return;
      }
      bool flag = ((index == n) ? true : false);
      if (C[index]->n < t)
         fill(index);
      if (flag && index > n)
         C[index - 1]->deletion(key);
      else
         C[index]->deletion(key);
   }
   return;
}

// Deletion at the leaf nodes
void deletion_at_leaf(int index){
   for (int i = index + 1; i < n; ++i)
      keys[i - 1] = keys[i];
   n--;
   return;
}

// Deletion at the non leaf node
void deletion_at_nonleaf(int index){
   int key = keys[index];
   if (C[index]->n >= t) {
      int pred = get_Predecessor(index);
      keys[index] = pred;
      C[index]->deletion(pred);
   } else if (C[index + 1]->n >= t) {
      int successor = copysuccessoressor(index);
      keys[index] = successor;
      C[index + 1]->deletion(successor);
   } else {
      merge(index);
      C[index]->deletion(key);
   }
   return;
}

例子

C C++ Java Python

// C Program for B trees 
#include <stdio.h>
#include <stdlib.h>
struct BTree {
    //node declaration
   int *d;
   struct BTree **child_ptr;
   int l;
   int n;
};
struct BTree *r = NULL;
struct BTree *np = NULL;
struct BTree *x = NULL;
//creation of node
struct BTree* init() {
   int i;
   np = (struct BTree*)malloc(sizeof(struct BTree));
   //order 6
   np->d = (int*)malloc(6 * sizeof(int));
   np->child_ptr = (struct BTree**)malloc(7 * sizeof(struct BTree*));
   np->l = 1;
   np->n = 0;
   for (i = 0; i < 7; i++) {
      np->child_ptr[i] = NULL;
   }
   return np;
}
//traverse the tree
void traverse(struct BTree *p) {
   printf("\n");
   int i;
   for (i = 0; i < p->n; i++) {
      if (p->l == 0) {
         traverse(p->child_ptr[i]);
      }
      printf(" %d", p->d[i]);
   }
   if (p->l == 0) {
      traverse(p->child_ptr[i]);
   }
   printf("\n");
}
//sort the tree
void sort(int *p, int n) {
   int i, j, t;
   for (i = 0; i < n; i++) {
      for (j = i; j <= n; j++) {
         if (p[i] > p[j]) {
            t = p[i];
            p[i] = p[j];
            p[j] = t;
         }
      }
   }
}
int split_child(struct BTree *x, int i) {
   int j, mid;
   struct BTree *np1, *np3, *y;
   np3 = init();
   //create new node
   np3->l = 1;
   if (i == -1) {
      mid = x->d[2];
      //find mid
      x->d[2] = 0;
      x->n--;
      np1 = init();
      np1->l = 0;
      x->l = 1;
      for (j = 3; j < 6; j++) {
         np3->d[j - 3] = x->d[j];
         np3->child_ptr[j - 3] = x->child_ptr[j];
         np3->n++;
         x->d[j] = 0;
         x->n--;
      }
      for (j = 0; j < 6; j++) {
         x->child_ptr[j] = NULL;
      }
      np1->d[0] = mid;
      np1->child_ptr[np1->n] = x;
      np1->child_ptr[np1->n + 1] = np3;
      np1->n++;
      r = np1;
   } else {
      y = x->child_ptr[i];
      mid = y->d[2];
      y->d[2] = 0;
      y->n--;
      for (j = 3; j < 6; j++) {
         np3->d[j - 3] = y->d[j];
         np3->n++;
         y->d[j] = 0;
         y->n--;
      }
      x->child_ptr[i + 1] = y;
      x->child_ptr[i + 1] = np3;
   }
   return mid;
}
void insert(int a) {
   int i, t;
   x = r;
   if (x == NULL) {
      r = init();
      x = r;
   } else {
      if (x->l == 1 && x->n == 6) {
         t = split_child(x, -1);
         x = r;
         for (i = 0; i < x->n; i++) {
            if (a > x->d[i] && a < x->d[i + 1]) {
               i++;
               break;
            } else if (a < x->d[0]) {
               break;
            } else {
               continue;
            }
         }
         x = x->child_ptr[i];
      } else {
         while (x->l == 0) {
            for (i = 0; i < x->n; i++) {
               if (a > x->d[i] && a < x->d[i + 1]) {
                  i++;
                  break;
               } else if (a < x->d[0]) {
                  break;
               } else {
                  continue;
               }
            }
            if (x->child_ptr[i]->n == 6) {
               t = split_child(x, i);
               x->d[x->n] = t;
               x->n++;
               continue;
            } else {
               x = x->child_ptr[i];
            }
         }
      }
   }
   x->d[x->n] = a;
   sort(x->d, x->n);
   x->n++;
}

int main() {
   int i, n, t;
   insert(10);
   insert(20);
   insert(30);
   insert(40);
   insert(50);
   printf("B tree:\n");
   traverse(r);
   return 0;
}

输出

B tree:
 10 20 30 40 50

#include<iostream>
using namespace std;
struct BTree {//node declaration
   int *d;
   BTree **child_ptr;
   bool l;
   int n;
}*r = NULL, *np = NULL, *x = NULL;

BTree* init() {//creation of node
   int i;
   np = new BTree;
   np->d = new int[6];//order 6
   np->child_ptr = new BTree *[7];
   np->l = true;
   np->n = 0;
   for (i = 0; i < 7; i++) {
      np->child_ptr[i] = NULL;
   }
   return np;
}

void traverse(BTree *p) { //traverse the tree
   cout<<endl;
   int i;
   for (i = 0; i < p->n; i++) {
      if (p->l == false) {
         traverse(p->child_ptr[i]);
      }
      cout << " " << p->d[i];
   }
   if (p->l == false) {
      traverse(p->child_ptr[i]);
   }
   cout<<endl;
}

void sort(int *p, int n){ //sort the tree
   int i, j, t;
   for (i = 0; i < n; i++) {
      for (j = i; j <= n; j++) {
         if (p[i] >p[j]) {
            t = p[i];
            p[i] = p[j];
            p[j] = t;
         }
      }
   }
}

int split_child(BTree *x, int i) {
   int j, mid;
   BTree *np1, *np3, *y;
   np3 = init();//create new node
   np3->l = true;
   if (i == -1) {
      mid = x->d[2];//find mid
      x->d[2] = 0;
      x->n--;
      np1 = init();
      np1->l= false;
      x->l= true;
      for (j = 3; j < 6; j++) {
         np3->d[j - 3] = x->d[j];
         np3->child_ptr[j - 3] = x->child_ptr[j];
         np3->n++;
         x->d[j] = 0;
         x->n--;
      }
      for (j = 0; j < 6; j++) {
         x->child_ptr[j] = NULL;
      }
      np1->d[0] = mid;
      np1->child_ptr[np1->n] = x;
      np1->child_ptr[np1->n + 1] = np3;
      np1->n++;
      r = np1;
   } else {
      y = x->child_ptr[i];
      mid = y->d[2];
      y->d[2] = 0;
      y->n--;
      for (j = 3; j <6 ; j++) {
         np3->d[j - 3] = y->d[j];
         np3->n++;
         y->d[j] = 0;
         y->n--;
      }
      x->child_ptr[i + 1] = y;
      x->child_ptr[i + 1] = np3;
   }
   return mid;
}

void insert(int a) {
   int i, t;
   x = r;
   if (x == NULL) {
      r = init();
      x = r;
   } else {
      if (x->l== true && x->n == 6) {
         t = split_child(x, -1);
         x = r;
         for (i = 0; i < (x->n); i++) {
            if ((a >x->d[i]) && (a < x->d[i + 1])) {
               i++;
               break;
            } else if (a < x->d[0]) {
               break;
            } else {
               continue;
            }
         }
         x = x->child_ptr[i];
      } else {
         while (x->l == false) {
            for (i = 0; i < (x->n); i++) {
               if ((a >x->d[i]) && (a < x->d[i + 1])) {
                  i++;
                  break;
               } else if (a < x->d[0]) {
                  break;
               } else {
                  continue;
               }
            }
            if ((x->child_ptr[i])->n == 6) {
               t = split_child(x, i);
               x->d[x->n] = t;
               x->n++;
               continue;
            } else {
               x = x->child_ptr[i];
            }
         }
      }
   }
   x->d[x->n] = a;
   sort(x->d, x->n);
   x->n++;
}

int main() {
   int i, n, t;
   insert(10);
   insert(20);
   insert(30);
   insert(40);
   insert(50);
   cout<<"B tree:\n";
   traverse(r);
}

输出

B tree:
10 20 30 40 50

//Java code for B trees 
import java.util.Arrays;
class BTree {
    private int[] d;
    private BTree[] child_ptr;
    private boolean l;
    private int n;
    public BTree() {
        d = new int[6]; // order 6
        child_ptr = new BTree[7];
        l = true;
        n = 0;
        Arrays.fill(child_ptr, null);
    }
    public void traverse() {
        System.out.println("B tree: ");
        for (int i = 0; i < n; i++) {
            if (!l) {
                child_ptr[i].traverse();
            }
            System.out.print(d[i] + " ");
        }
        if (!l) {
            child_ptr[n].traverse();
        }
        System.out.println();
    }
   public void sort() {
        Arrays.sort(d, 0, n);
    }
    public int splitChild(int i) {
        int j, mid;
        BTree np1, np3, y;
        np3 = new BTree();
        np3.l = true;
        if (i == -1) {
            mid = d[2];
            d[2] = 0;
            n--;
            np1 = new BTree();
            np1.l = false;
            l = true;
            for (j = 3; j < 6; j++) {
                np3.d[j - 3] = d[j];
                np3.n++;
                d[j] = 0;
                n--;
            }
            for (j = 0; j < 6; j++) {
                np3.child_ptr[j] = child_ptr[j + 3];
                child_ptr[j + 3] = null;
            }
            np1.d[0] = mid;
            np1.child_ptr[0] = this;
            np1.child_ptr[1] = np3;
            np1.n++;
            return mid;
        } else {
            y = child_ptr[i];
            mid = y.d[2];
            y.d[2] = 0;
            y.n--;
            for (j = 3; j < 6; j++) {
                np3.d[j - 3] = y.d[j];
                np3.n++;
                y.d[j] = 0;
                y.n--;
            }
            child_ptr[i + 1] = y;
            child_ptr[i + 2] = np3;
            return mid;
        }
    }
    public void insert(int a) {
        int i, t;
        BTree x = this;
        if (x.l && x.n == 6) {
            t = x.splitChild(-1);
            x = this;
            for (i = 0; i > x.n; i++) {
                if (a > x.d[i] && a < x.d[i + 1]) {
                    i++;
                    break;
                } else if (a < x.d[0]) {
                    break;
                }
            }
            x = x.child_ptr[i];
        } else {
            while (!x.l) {
                for (i = 0; i < x.n; i++) {
                    if (a > x.d[i] && a < x.d[i + 1]) {
                        i++;
                        break;
                    } else if (a < x.d[0]) {
                        break;
                    }
                }
                if (x.child_ptr[i].n == 6) {
                    t = x.splitChild(i);
                    x.d[x.n] = t;
                    x.n++;
                    continue;
                }
                x = x.child_ptr[i];
            }
        }
        x.d[x.n] = a;
        x.sort();
        x.n++;
    }
}
public class Main {
    public static void main(String[] args) {
        BTree bTree = new BTree();
        bTree.insert(20);
        bTree.insert(10);
        bTree.insert(40);
        bTree.insert(30);
        bTree.insert(50); // Duplicate value, ignored
        //call the traverse method
        bTree.traverse();
    }
}

输出

B tree:
10 20 30 40 50

#python program for B treesa
class BTree:
    def __init__(self):
        #node declartion
        self.d = [0] * 6
        self.child_ptr = [None] * 7
        self.l = True
        self.n = 0

#creation of node
def init():
    np = BTree()
    np.l = True
    np.n = 0
    return np

#traverse the tree 
def traverse(p):
    if p is not None:
        for i in range(p.n):
            if not p.l:
                traverse(p.child_ptr[i])
            print(p.d[i], end=" ")
        if not p.l:
            traverse(p.child_ptr[p.n])
 #sort the tree   
def sort(p, n):
    for i in range(n):
        for j in range(i, n+1):
            if p[i] > p[j]:
                p[i], p[j] = p[j], p[i]

def split_child(x, i):
    np3 = init()
    #create new node
    np3.l = True
    if i == -1:
        mid = x.d[2]
        #find mid
        x.d[2] = 0
        x.n -= 1
        np1 = init()
        np1.l = False
        x.l = True
        for j in range(3, 6):
            np3.d[j-3] = x.d[j]
            np3.child_ptr[j-3] = x.child_ptr[j]
            np3.n += 1
            x.d[j] = 0
            x.n -= 1
        for j in range(6):
            x.child_ptr[j] = None
        np1.d[0] = mid
        np1.child_ptr[np1.n] = x
        np1.child_ptr[np1.n + 1] = np3
        np1.n += 1
        return np1
    else:
        y = x.child_ptr[i]
        mid = y.d[2]
        y.d[2] = 0
        y.n -= 1
        for j in range(3, 6):
            np3.d[j-3] = y.d[j]
            np3.n += 1
            y.d[j] = 0
            y.n -= 1
        x.child_ptr[i + 1] = y
        x.child_ptr[i + 1] = np3
    return mid

def insert(a):
    global r, x
    if r is None:
        r = init()
        x = r
    else:
        if x.l and x.n == 6:
            t = split_child(x, -1)
            x = r
            for i in range(x.n):
                if a > x.d[i] and a < x.d[i + 1]:
                    i += 1
                    break
                elif a < x.d[0]:
                    break
                else:
                    continue
            x = x.child_ptr[i]
        else:
            while not x.l:
                for i in range(x.n):
                    if a > x.d[i] and a < x.d[i + 1]:
                        i += 1
                        break
                    elif a < x.d[0]:
                        break
                    else:
                        continue
                if x.child_ptr[i].n == 6:
                    t = split_child(x, i)
                    x.d[x.n] = t
                    x.n += 1
                    continue
                else:
                    x = x.child_ptr[i]
    x.d[x.n] = a
    sort(x.d, x.n)
    x.n += 1
if __name__ == '__main__':
    r = None
    x = None
    insert(10)
    insert(20)
    insert(30)
    insert(40)
    insert(50)
    print("B tree:")
    traverse(r)

输出

B tree:
 10 20 30 40 50