数据结构小记【Python/C++版】——B树篇

一，基础概念

B树也是一种自平衡搜索树，常用于数据库中索引的实现。

B树和AVL树的区别在于：

B树是一种多路平衡查找树，B树的节点可以有两个以上的子节点(AVL树是二叉树，最多只能有两个子节点)。

B树的每个节点可以存储一个以上的数据域(在之前介绍过的树结构中，一个节点只有一个数据域)。由于B树的节点可以存放多条数据，因此B树特别适合应用在块存储的开发场景。

B树和AVL树的相同点在于：

B树的节点分布也是按照左小右大排列，子节点与节点的大小比较结果决定了子节点的位置。

每个节点中，左子树的数据比当前节点都小，右子树的数据比当前节点都大。

关于B树的阶：

M阶B树表示该树每个节点最多有M个子树。若B树中一个节点的子节点数目的最大值为4，则该树为4阶。

M阶B树可以定义为M路搜索树：

节点的最多子节点数为M。

节点的最大数据量为M-1。

所有非叶子节点(根节点除外)应该至少有M/2个子节点。

所有节点(根节点除外)应该至少有M/2-1条数据。

B树的阶数可以帮助我们确定节点在B树中可以容纳的子节点数。如果B树的阶数为3，则子节点的最小数量为2，最大数量为3，节点最多可以存放2个数据。类似地，如果B树的阶数为4，则子节点的最小和最大数量将分别为2和4，节点最多可以存放3个数据。

B树的基本结构：

B树的结构特点：

所有叶子节点都出现在同一水平高度。

B树是一棵扁平树，层数很小，B树的节点不再只存储一条数据。

B树节点内的所有数据必须按键值升序排列。

B树的设计原则就是，将尽可能多的数据放入B树的每个节点中，从而使B树的层数保持在最小值。由于不用遍历很多层节点，与其他平衡树相比，B树的访问速度更快。

二，B树的基本操作

搜索节点：

节点在B树中的搜索步骤与BST树中的类似。

插入节点：

如果树为空，则创建一个新节点并将其作为根节点插入到树中。

如果树不为空，插入节点包含两个操作：

1.搜索合适的位置以插入节点

按照升序插入节点。

2.当节点的数据量过大时拆分节点

插入新节点以后，节点中数据的数量超过了限制(节点的最大数据量为M-1)，则按中位数拆分。将中间节点推往上一层，使左边节点成为左子节点，右边节点成为右子节点。

图示样例：

三，完整代码实现

C++实现：

#include 
using namespace std;
class Node {
    int* keys;
    int t;
    Node** C;
    int n;
    bool leaf;
public:
    Node(int _t, bool _leaf);
    void insertNonFull(int k);
    void splitChild(int i, Node* y);
    void traverse();
    friend class BTree;
};
class BTree {
    Node* root;
    int t;
public:
    BTree(int _t) {
        root = NULL;
        t = _t;
    }
    void traverse() {
        if (root != NULL)
            root->traverse();
    }
    void insert(int k);
};
Node::Node(int t1, bool leaf1) {
    t = t1;
    leaf = leaf1;
    keys = new int[2 * t - 1];
    C = new Node * [2 * t];
    n = 0;
}
//遍历节点
void Node::traverse() {
    int i;
    for (i = 0; i < n; i++) {
        if (leaf == false)
            C[i]->traverse();
        cout << " " << keys[i];
    }
    if (leaf == false)
        C[i]->traverse();
}
void BTree::insert(int k) {
    if (root == NULL) {
        root = new Node(t, true);
        root->keys[0] = k;
        root->n = 1;
    }
    else {
        if (root->n == 2 * t - 1) {
            Node* s = new Node(t, false);
            s->C[0] = root;
            s->splitChild(0, root);
            int i = 0;
            if (s->keys[0] < k)
                i++;
            s->C[i]->insertNonFull(k);
            root = s;
        }
        else
            root->insertNonFull(k);
    }
}
void Node::insertNonFull(int k) {
    int i = n - 1;
    if (leaf == 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 * t - 1) {
            splitChild(i + 1, C[i + 1]);
            if (keys[i + 1] < k)
                i++;
        }
        C[i + 1]->insertNonFull(k);
    }
}
//拆分节点
void Node::splitChild(int i, Node* y) {
    Node* z = new Node(y->t, y->leaf);
    z->n = t - 1;
    for (int j = 0; j < t - 1; j++)
        z->keys[j] = y->keys[j + t];
    if (y->leaf == false) {
        for (int j = 0; j < t; j++)
            z->C[j] = y->C[j + t];
    }
    y->n = t - 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[t - 1];
    n = n + 1;
}
int main() {
    BTree t(3);
    t.insert(8);
    t.insert(9);
    t.insert(10);
    t.insert(11);
    t.insert(15);
    t.insert(20);
    t.insert(17);
    cout << "The B-tree is: ";
    t.traverse();
}

运行结果：

The B-tree is:  8 9 10 11 15 17 20

Python实现：

class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.child = []
 
class BTree:
    def __init__(self, t):
        self.root = BTreeNode(True)
        self.t = t
 
    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)
 
    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)
 
    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]
 
    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)
 
def main():
    B = BTree(3)
    for i in range(10):
        B.insert((i, 2 * i))
    B.print_tree(B.root)
 
if __name__ == '__main__':
    main()

四，参考阅读

https://iq.opengenus.org/b-tree-searching-insertion/

https://www.programiz.com/dsa/insertion-into-a-b-tree

https://www.programiz.com/dsa/b-plus-tree