Demostración animada del árbol B

传统二叉搜索树的局限性可能令人沮丧。 B 树是一种多才多艺的数据结构，可以轻松处理大量数据。当涉及到存储和搜索大量数据时，传统的二叉搜索树由于其性能差和内存使用率高而变得不切实际。 B 树，也称为 B 树或平衡树，是一种自平衡树，专门为克服这些限制而设计。

与传统的二叉搜索树不同，B 树的特点是可以在单个节点中存储大量键，这就是为什么它们也被称为“大键”树。 B 树中的每个节点可以包含多个键，这使得树具有更大的分支因子，从而具有更浅的高度。这种浅高度会减少磁盘 I/O，从而加快搜索和插入操作的速度。 B 树特别适合具有缓慢、大量数据访问的存储系统，例如硬盘驱动器、闪存和 CD-ROM。

B 树通过确保每个节点具有最少数量的键来保持平衡，因此树始终是平衡的。这种平衡保证了插入、删除和搜索等操作的时间复杂度始终为 O(log n)，无论树的初始形状如何。

B树的时间复杂度：

先生。出色地。	算法	时间复杂度
1.	搜索	O(logn)
2.	插入	O(logn)
3.	删除	O(logn)

注： “n”是B树中元素的总数

B 树的性质：

所有叶子都处于同一水平。
B 树由术语最小度“ t ”定义。 “ t ”的值取决于磁盘块大小。
除根节点外的每个节点最多只能包含 t-1 个键。根可能至少包含 1 个 密钥。
所有节点（包括根节点）最多可以包含 ( 2*t – 1 ) 个密钥。
节点的子节点数量等于其中的键数量加 1 。
节点的所有键均按升序排序。 两个键k1 和 k2 之间的子键包含 k1 和 k2 范围内的所有键。
B 树从根开始生长和收缩，这与二叉搜索树不同。二叉搜索树向下生长，也向下收缩。
与其他平衡二叉搜索树一样，搜索、插入和删除的时间复杂度为 O(log n)。
B 树中节点的插入仅发生在叶节点处。

以下是最小阶数为 5 的 B 树的示例
注意： 在实际的 B 树中，最小阶数的值远大于 5。

从上图中我们可以看到，所有的叶子节点都处于同一级别，所有非叶子节点都没有空子树，并且键的值比其子节点的数量少一。

关于 B 树的有趣事实：

可以存在 n 个节点且 m 是节点可以拥有的最大子节点数的 B 树的最小高度为： $h_{min} =\lceil\log_m (n + 1)\rceil - 1$

可以存在 n 个节点且 t 是非根节点可以拥有的最小子节点数的 B 树的最大高度为 $h_{max} =\lfloor\log_t\frac {n + 1}{2}\rfloor$ ： $t = \lceil\frac {m}{2}\rceil$

B树中的遍历：

遍历也类似于二叉树的中序遍历。我们从最左边的孩子开始，递归地打印最左边的孩子，然后对其余的孩子和键重复相同的过程。最后，递归打印最右边的孩子。

B树中的搜索操作：

搜索类似于二叉搜索树中的搜索。设要搜索的键为k。

从根开始，递归向下遍历。
对于每个访问过的非叶节点，
- 如果节点有密钥，我们只需返回该节点即可。
- 否则，我们递归到该节点的适当子节点（位于第一个更大键之前的子节点）。
如果我们到达叶节点并且在叶节点中没有找到 k，则返回 NULL。

搜索 B 树类似于搜索二叉树。算法类似，都是递归的。在每个级别，搜索都会得到优化，就好像键值不存在于父级范围中，然后键存在于另一个分支中一样。由于这些值限制了搜索，因此它们也称为限制值或分离值。如果我们到达叶节点但没有找到所需的键，那么它将显示 NULL。

在 B 树中搜索元素的算法：-

C++

              
                
                    struct Node {
    int
                          n;
    int
                          key[MAX_KEYS];
    Node* child[MAX_CHILDREN];
    bool leaf;
};
 
Node* BtreeSearch(Node* x, int k) {
    int
                          i = 0;
    while (i < x->n && k > x->key[i]) {
        i++;
    }
    if
                          (i < x->n && k == x->key[i]) {
        return x;
    }
    if
                          (x->leaf) {
        return nullptr;
    }
    return BtreeSearch(x->child[i], k);
}

                  

              
            

C

              
                
                    BtreeSearch(x, k)
    i = 1
                        
     
    // n[x] means number of keys in x node
    while i ≤ n[x] and k ≥ keyi[x]
        do i = i + 1
    if
                          i  n[x] and k = keyi[x]
        then return (x, i)   
    if
                          leaf [x]
        then return NIL
    else
        return BtreeSearch(ci[x], k)

                  

              
            

Java

              
                
                    class Node {
    int
                          n;
    int[] key = new int[MAX_KEYS];
    Node[] child = new Node[MAX_CHILDREN];
    boolean
                          leaf;
}
 
Node BtreeSearch(Node x, int k) {
    int
                          i = 0;
    while
                          (i < x.n && k >= x.key[i]) {
        i++;
    }
    if
                          (i < x.n && k == x.key[i]) {
        return x;
    }
    if
                          (x.leaf) {
        return null;
                        
    }
    return
                          BtreeSearch(x.child[i], k);
}

                  

              
            

Python3

              
                
                    class Node:
    def
                          __init__(self):
        self.n = 0
        self.key =
                          [0] * MAX_KEYS
        self.child =
                          [None] * MAX_CHILDREN
        self.leaf =
                          True
 
def BtreeSearch(x, k):
    i = 0
    while
                          i < x.n and k >= x.key[i]:
        i += 1
    if
                          i < x.n and k == x.key[i]:
        return x
    if
                          x.leaf:
        return None
    return
                          BtreeSearch(x.child[i], k)

                  

              
            

C＃

              
                
                    class Node {
    public
                          int n;
    public
                          int[] key = new int[MAX_KEYS];
    public
                          Node[] child = new Node[MAX_CHILDREN];
    public
                          bool leaf;
}
 
Node BtreeSearch(Node x, int k) {
    int
                          i = 0;
    while
                          (i < x.n && k >= x.key[i]) {
        i++;
    }
    if
                          (i < x.n && k == x.key[i]) {
        return x;
    }
    if
                          (x.leaf) {
        return null;
                        
    }
    return
                          BtreeSearch(x.child[i], k);
}

                  

              
            

JavaScript

              
                
                    // Define a Node class with properties n, key, child, and leaf
class Node {
    constructor() {
        this.n = 0;
        this.key = new Array(MAX_KEYS);
        this.child = new Array(MAX_CHILDREN);
        this.leaf = false;
    }
}
 
// Define a function BtreeSearch that takes in a Node object x and an integer k
                        
function BtreeSearch(x, k) {
    let i = 0;
    while
                          (i < x.n && k >= x.key[i]) {
        i++;
    }
    if
                          (i < x.n && k == x.key[i]) {
        return x;
    }
    if
                          (x.leaf) {
        return null;
                        
    }
    return
                          BtreeSearch(x.child[i], k);
}

                  

              
            

例子：

输入： 在给定的 B 树中搜索 120。

解决方案：

在这个例子中，我们可以看到，通过限制包含值的键出现的机会，我们的搜索量就减少了。类似地，如果在上面的示例中我们要查找 180，那么控制将在步骤 2 处停止，因为程序会发现键 180 存在于当前节点中。同样，如果要查找 90，则 90 < 100，因此它将自动转到左子树，因此控制流程将与上面示例中所示的类似。

下面是上述方法的实现：

C++

            
              
                  // C++ implementation of search() and traverse() methods
#include <iostream>
                      
using namespace std;
 
// A BTree node
class BTreeNode {
    int* keys; // An array of keys
    int
                        t; // Minimum degree (defines the range for number
           // of keys)
    BTreeNode** C; // An array of child pointers
    int
                        n; // Current number of keys
    bool
                        leaf; // Is true when node is leaf. Otherwise false
public:
    BTreeNode(int _t, bool _leaf); // Constructor
 
    // A function to traverse all nodes in a subtree rooted
    // with this node
    void
                        traverse();
 
    // A function to search a key in the subtree rooted with
    // this node.
    BTreeNode*
                      
    search(int k); // returns NULL if k is not present.
                      
 
    // Make the BTree friend of this so that we can access
    // private members of this class in BTree functions
    friend class BTree;
};
 
// A BTree
class BTree {
    BTreeNode* root; // Pointer to root node
                      
    int
                        t; // Minimum degree
public:
    // Constructor (Initializes tree as empty)
    BTree(int _t)
    {
        root = NULL;
        t = _t;
    }
 
    // function to traverse the tree
    void
                        traverse()
    {
        if (root != NULL)
            root->traverse();
    }
 
    // function to search a key in this tree
    BTreeNode* search(int k)
    {
        return (root == NULL) ? NULL : root->search(k);
    }
};
 
// Constructor for BTreeNode class
BTreeNode::BTreeNode(int _t, bool _leaf)
{
    // Copy the given minimum degree and leaf property
    t = _t;
                      
    leaf = _leaf;
 
    // Allocate memory for maximum number of possible keys
    // and child pointers
    keys = new int[2 * t - 1];
    C = new BTreeNode*[2 * t];
 
    // Initialize the number of keys as 0
    n = 0;
                      
}
 
// Function to traverse all nodes in a subtree rooted with
// this node
void BTreeNode::traverse()
{
    // There are n keys and n+1 children, traverse through n
    // keys and first n children
    int
                        i;
    for
                        (i = 0; i < n; i++) {
        // If this is not leaf, then before printing key[i],
        // traverse the subtree rooted with child C[i].
        if (leaf == false)
            C[i]->traverse();
        cout << " " << keys[i];
    }
 
    // Print the subtree rooted with last child
    if
                        (leaf == false)
        C[i]->traverse();
}
 
// Function to search key k in subtree rooted with this node
BTreeNode* BTreeNode::search(int k)
{
    // Find the first key greater than or equal to k
    int
                        i = 0;
    while (i < n && k > keys[i])
        i++;
 
    // If the found key is equal to k, return this node
    if
                        (keys[i] == k)
        return this;
 
    // If the key is not found here and this is a leaf node
    if
                        (leaf == true)
        return NULL;
 
    // Go to the appropriate child
    return C[i]->search(k);
}

                

            
          

Java

            
              
                  // Java program to illustrate the sum of two numbers
 
// A BTree
class Btree {
    public
                        BTreeNode root; // Pointer to root node
                      
    public
                        int t; // Minimum degree
 
    // Constructor (Initializes tree as empty)
    Btree(int t)
    {
        this.root = null;
        this.t = t;
    }
 
    // function to traverse the tree
    public
                        void traverse()
    {
        if (this.root != null)
                      
            this.root.traverse();
        System.out.println();
    }
 
    // function to search a key in this tree
    public
                        BTreeNode search(int k)
    {
        if (this.root == null)
                      
            return null;
                      
        else
            return this.root.search(k);
    }
}
 
// A BTree node
class BTreeNode {
    int[] keys; // An array of keys
    int t; // Minimum degree (defines the range for number
           // of keys)
    BTreeNode[] C; // An array of child pointers
    int n; // Current number of keys
    boolean
                      
        leaf; // Is true when node is leaf. Otherwise false
 
    // Constructor
    BTreeNode(int t, boolean leaf)
                      
    {
        this.t = t;
        this.leaf = leaf;
        this.keys = new
                        int[2 * t - 1];
        this.C = new
                        BTreeNode[2 * t];
        this.n = 0;
    }
 
    // A function to traverse all nodes in a subtree rooted
    // with this node
    public
                        void traverse()
    {
 
        // There are n keys and n+1 children, traverse
        // through n keys and first n children
        int i = 0;
        for (i = 0; i < this.n; i++) {
 
            // If this is not leaf, then before printing
            // key[i], traverse the subtree rooted with
            // child C[i].
            if (this.leaf == false) {
                      
                C[i].traverse();
            }
            System.out.print(keys[i] + " ");
        }
 
        // Print the subtree rooted with last child
        if (leaf == false)
            C[i].traverse();
    }
 
    // A function to search a key in the subtree rooted with
    // this node.
    BTreeNode search(int k)
    { // returns NULL if k is not present.
 
        // Find the first key greater than or equal to k
        int i = 0;
        while (i < n && k > keys[i])
                      
            i++;
 
        // If the found key is equal to k, return this node
        if (keys[i] == k)
            return this;
                      
 
        // If the key is not found here and this is a leaf
        // node
        if (leaf == true)
            return null;
                      
 
        // Go to the appropriate child
        return C[i].search(k);
    }
}

                

            
          

Python3

            
              
                  # Create a node
class BTreeNode:
  def __init__(self, leaf=False):
    self.leaf = leaf
                      
    self.keys = []
    self.child = []
 
 
# Tree
class BTree:
  def __init__(self, t):
    self.root = BTreeNode(True)
                      
    self.t = t
 
    # Insert node
  def insert(self, k):
    root = self.root
                      
    if len(root.keys) == (2 * self.t) - 1:
      temp = BTreeNode()
      self.root =
                        temp
      temp.child.insert(0, root)
      self.split_child(temp, 0)
      self.insert_non_full(temp, k)
    else:
      self.insert_non_full(root, k)
 
    # Insert nonfull
  def insert_non_full(self, x, k):
    i = len(x.keys) - 1
                      
    if x.leaf:
      x.keys.append((None, None))
      while i >=
                        0 and k[0] < x.keys[i][0]:
        x.keys[i + 1] = x.keys[i]
                      
        i -= 1
      x.keys[i + 1] = k
    else:
      while i >=
                        0 and k[0] < x.keys[i][0]:
        i -= 1
      i += 1
      if len(x.child[i].keys) == (2 * self.t) - 1:
        self.split_child(x, i)
        if k[0] > x.keys[i][0]:
          i += 1
      self.insert_non_full(x.child[i], k)
 
    # Split the child
  def split_child(self, x, i):
    t = self.t
    y = x.child[i]
    z = BTreeNode(y.leaf)
    x.child.insert(i + 1, z)
    x.keys.insert(i, y.keys[t - 1])
    z.keys = y.keys[t: (2 *
                        t) - 1]
    y.keys = y.keys[0: t - 1]
    if not y.leaf:
      z.child = y.child[t: 2 *
                        t]
      y.child = y.child[0: t - 1]
 
  # Print the tree
  def print_tree(self, x, l=0):
    print("Level ", l, " ", len(x.keys), end=":")
    for i in x.keys:
                      
      print(i, end=" ")
    print()
    l += 1
    if len(x.child) > 0:
      for i in x.child:
        self.print_tree(i, l)
 
  # Search key in the tree
  def search_key(self, k, x=None):
    if x is not None:
      i = 0
      while i < len(x.keys) and k > x.keys[i][0]:
        i += 1
      if i < len(x.keys) and k == x.keys[i][0]:
        return (x, i)
      elif x.leaf:
        return None
      else:
        return self.search_key(k, x.child[i])
       
    else:
      return self.search_key(k, self.root)
 
 
def main():
  B = BTree(3)
 
  for i in range(10):
    B.insert((i, 2 *
                        i))
 
  B.print_tree(B.root)
 
  if B.search_key(8) is not None:
    print("\nFound")
  else:
    print("\nNot Found")
 
 
if __name__ ==
                        '__main__':
  main()

                

            
          

C＃

            
              
                  // C# program to illustrate the sum of two numbers
using System;
 
// A BTree
class Btree {
    public
                        BTreeNode root; // Pointer to root node
                      
    public
                        int t; // Minimum degree
 
    // Constructor (Initializes tree as empty)
    Btree(int t)
    {
        this.root = null;
        this.t = t;
    }
 
    // function to traverse the tree
    public
                        void traverse()
    {
        if (this.root != null)
                      
            this.root.traverse();
        Console.WriteLine();
    }
 
    // function to search a key in this tree
    public
                        BTreeNode search(int k)
    {
        if (this.root == null)
                      
            return null;
                      
        else
            return this.root.search(k);
    }
}
 
// A BTree node
class BTreeNode {
    int[] keys; // An array of keys
    int t; // Minimum degree (defines the range for number
           // of keys)
    BTreeNode[] C; // An array of child pointers
    int n; // Current number of keys
    bool
                        leaf; // Is true when node is leaf. Otherwise false
 
    // Constructor
    BTreeNode(int t, bool leaf)
                      
    {
        this.t = t;
        this.leaf = leaf;
        this.keys = new
                        int[2 * t - 1];
        this.C = new
                        BTreeNode[2 * t];
        this.n = 0;
    }
 
    // A function to traverse all nodes in a subtree rooted
    // with this node
    public
                        void traverse()
    {
 
        // There are n keys and n+1 children, traverse
        // through n keys and first n children
        int i = 0;
        for (i = 0; i < this.n; i++) {
 
            // If this is not leaf, then before printing
            // key[i], traverse the subtree rooted with
            // child C[i].
            if (this.leaf == false) {
                      
                C[i].traverse();
            }
            Console.Write(keys[i] + " ");
        }
 
        // Print the subtree rooted with last child
        if (leaf == false)
            C[i].traverse();
    }
 
    // A function to search a key in the subtree rooted with
    // this node.
    public
                        BTreeNode search(int k)
    { // returns NULL if k is not present.
 
        // Find the first key greater than or equal to k
        int i = 0;
        while (i < n && k > keys[i])
                      
            i++;
 
        // If the found key is equal to k, return this node
        if (keys[i] == k)
            return this;
                      
 
        // If the key is not found here and this is a leaf
        // node
        if (leaf == true)
            return null;
                      
 
        // Go to the appropriate child
        return C[i].search(k);
    }
}
 
// This code is contributed by Rajput-Ji

                

            
          

JavaScript

            
              
                  // Javascript program to illustrate the sum of two numbers
 
// A BTree
class Btree
{
 
    // Constructor (Initializes tree as empty)
    constructor(t)
    {
        this.root = null;
        this.t = t;
    }
     
    // function to traverse the tree
    traverse()
                      
    {
        if (this.root != null)
                      
            this.root.traverse();
        document.write("<br>");
    }
     
    // function to search a key in this tree
    search(k)
                      
    {
        if (this.root == null)
                      
            return null;
                      
        else
            return this.root.search(k);
    }
     
}
 
// A BTree node
class BTreeNode
{
     // Constructor
    constructor(t,leaf)
    {
        this.t = t;
        this.leaf = leaf;
        this.keys = new
                        Array(2 * t - 1);
        this.C = new
                        Array(2 * t);
        this.n = 0;
    }
    // A function to traverse all nodes in a subtree rooted with this node
                      
    traverse()
                      
    {
        // There are n keys and n+1 children, traverse through n keys
        // and first n children
        let i = 0;
        for (i = 0; i < this.n; i++) {
  
            // If this is not leaf, then before printing key[i],
            // traverse the subtree rooted with child C[i].
            if (this.leaf == false) {
                      
                C[i].traverse();
            }
            document.write(keys[i] + " ");
        }
  
        // Print the subtree rooted with last child
        if (leaf == false)
            C[i].traverse();
    }
     
    // A function to search a key in the subtree rooted with this node.
                      
    search(k)    // returns NULL if k is not present.
    {
     
        // Find the first key greater than or equal to k
        let i = 0;
        while (i < n && k > keys[i])
                      
            i++;
  
        // If the found key is equal to k, return this node
        if (keys[i] == k)
            return this;
                      
  
        // If the key is not found here and this is a leaf node
        if (leaf == true)
            return null;
                      
  
        // Go to the appropriate child
        return C[i].search(k);
    }
}
 
// This code is contributed by patel2127

                

            
          

注意： 以上代码不包含驱动程序。我们将在下一篇关于B 树插入的文章中介绍完整的程序。

定义B-Tree有两种约定，一是按最小度定义，二是按顺序定义。我们遵循了最小度数约定，并且在接下来的 B-Tree 帖子中也将遵循相同的约定。上面程序中使用的变量名也保持不变

B树的应用：

它在大型数据库中用于访问存储在磁盘上的数据
使用 B 树可以在更短的时间内搜索数据集中的数据
通过索引功能，可以实现多级索引。
大多数服务器也使用B树方法。
B 树在 CAD 系统中用于组织和搜索几何数据。
B 树还用于其他领域，例如自然语言处理、计算机网络和密码学。

B 树的优点：

对于插入、删除和搜索等基本操作，B 树的时间复杂度保证为 O(log n)，这使得它们适合大型数据集和实时应用。
B 树是自平衡的。
高并发、高吞吐量。
高效的存储利用率。

B 树的缺点：

B 树基于基于磁盘的数据结构，并且可能具有较高的磁盘使用率。
并非对所有情况都是最好的。
与其他数据结构相比速度较慢。

插入和删除：
B 树插入 B 树删除

如果您发现任何不正确的内容，或者您想分享有关上述主题的更多信息，请发表评论。