B-树，也称为B树（Banlance Tree），是一种平衡的多叉树。

定义

B树的叶子节点都需要在同一层
假设B树的度为t，该值取决于磁盘的块大小
除了根节点，每个节点至少包含t-1个键，根节点至少包含1个键
所有节点最多包含2*t-1个键
每个节点的子节点个数为其键的个数+1
所有的节点必须是升序，k1和k2的子节点，就包含了从k1到k2全部的值（range搜索）
插入只会发生在叶子节点

操作

Traversal
类似于二叉树的中序遍历

Search

算法
搜索k
从根节点出发
对于非叶子节点，如果节点中存在k，则返回该非叶子节点
否则选择第一个比k大的叶子节点
当到达叶子节点，叶子节点中没有k，则返回null
示例
搜索120

代码
```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);

}

} ```