【数据结构】B-树_ds b-树构建及查找

性质

B-树实际上是一棵M阶（M>2）的M路平衡搜索树，可以是空树或者满足下面性质：

• 根节点至少有两个孩子
• 每个非根节点至少有M/2(上取整)个孩子,至多有M个孩子
• 每个非根节点至少有M/2-1(上取整)个关键字,至多有M-1个关键字，并且以升序排列
• key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间
• 所有的叶子节点都在同一层

插入分析

我们可以通过模拟实现一个简单的B-树插入过程来理解以上的性质，因为在整个插入的过程中，都是围绕着以上的性质来进行的
为了实现的简单，我们选择三叉树，而三叉树就要求每个非根节点至多有2个关键字，所以我们设置一个节点有三个数据域用于存放关键字，四个指针域用于存放孩子，当判断数据域存放了三个关键字时进行节点的分裂

先用一个插入案例演示一下整个构建B-树的过程：{53, 139, 75, 49, 145, 36, 101}
每个节点都按照插入排序的进行插入

当节点不满足B-树的性质时进行分裂，为了满足上面B-树的性质，分裂的时候将需要分裂节点数据域右半边的数据分裂出去，创建一个新节点存放，将中间位置数据上提到该节点的父亲节点中，如果父亲节点不存在，则创建一个，然后将父亲节点中该数据所对应的指针域中的孩子指向相应节点，并且要让孩子节点的父指针指向父节点（图中未画出）

当从根节点继续插入的时候，49小于数据域中的第一个数据，然后继续到该数据的左孩子节点中去插入，145则相应的到右孩子中去插入

当插入36的时候该节点不满足B-树性质继续进行分裂，右半边53分裂，中间49上提，在上提的插入过程中依然是进行插入排序，此时需要对75进行右移，右移的时候别忘了连带它的右孩子一起移动，然后将分裂出来的节点作为上提49的右孩子，左孩子为原来75对应的左孩子

插入101后底层的节点虽然分裂了，但是上提后发现根节点此时已经不满足B-树的性质了，则继续要对根节点进行分裂

在这里要特别注意两点：在节点分裂的过程中，不仅要对数据域进行分裂，而且要把该数据域所对应的的指针域进行相应的分裂，在分裂的过程中由于每一个节点都维护了一个数据域的size，则要对新老节点进行size的重置

由此不难看出B-树是一个天然平衡的树，是基于它是一个横向增长+倒着增长的特点所决定的

代码实现

首先定义了一个类，由数据域，指针域，父节点，以及维护的数据域size四部分组成

class BTreeNode {
    int[] datas;//数据域
    BTreeNode[] pSub;//孩子节点指针域
    BTreeNode[] pParent;//父节点指针
    int[] size;

    /*
    三叉树：一个节点最多有3个孩子和2个数据
    为了实现简单，数据域和孩子域多增加一个
     */
    public BTreeNode() {
        this.datas = new int[3];
        this.pSub = new BTreeNode[4];
        //Java没有值传递，w我在这里的解决方案是传size为1的数组
        this.size = new int[1];
        this.pParent = new BTreeNode[1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

因为需要对插入的位置进行查找，所以这里定义了一个返回值的类型

class ResultType{
    BTreeNode bTreeNode;
    int index;

    public ResultType(BTreeNode bTreeNode, int index) {
        this.bTreeNode = bTreeNode;
        this.index = index;
    }
}

1
2
3
4
5
6
7
8
9
10

查找方法

查找成功，则该插入数据在B-树中已有重复，返回该节点以及该节点插入数据域的下标（此时下标肯定大于等于0，在后面的插入中会用到这个返回值），查找失败表示树中没有该数据，最后遍历的子节点和-1，此时的子节点就是需要进行插入的节点

    public static ResultType find(BTreeNode root, int key){
        BTreeNode cur = root;
        BTreeNode parent = null;
        int i = 0;

        while (cur != null){
            i = 0;
            while (i < cur.size[0]){
                if (key == cur.datas[i]){
                    return new ResultType(cur, i);
                }else if (key < cur.datas[i]){
                    break;
                }else {
                    i++;
                }
            }
            parent = cur;
            cur = cur.pSub[i];
        }
        return new ResultType(parent, -1);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

插入方法

这个方法是已经确定要插入了才执行，则按照插入排序的思想进行插入

public static void insertKey(BTreeNode cur, int key, BTreeNode sub){
        int end = cur.size[0] - 1;
        while (end >= 0){
            if (key < cur.datas[end]){
                cur.datas[end + 1] = cur.datas[end];
                cur.pSub[end + 2] = cur.pSub[end + 1];
                end--;
            }else {
                break;
            }
        }

        cur.datas[end + 1] = key;
        cur.pSub[end + 2] = sub;

        if (sub != null){
            sub.pParent[0] = cur;
        }
        cur.size[0]++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

具体的插入方法

public class Insert {

    public static ResultType find(BTreeNode root, int key){
        BTreeNode cur = root;
        BTreeNode parent = null;
        int i = 0;

        while (cur != null){
            i = 0;
            while (i < cur.size[0]){
                if (key == cur.datas[i]){
                    return new ResultType(cur, i);
                }else if (key < cur.datas[i]){
                    break;
                }else {
                    i++;
                }
            }
            parent = cur;
            cur = cur.pSub[i];
        }
        return new ResultType(parent, -1);
    }

    public static void insertKey(BTreeNode cur, int key, BTreeNode sub){
        int end = cur.size[0] - 1;
        while (end >= 0){
            if (key < cur.datas[end]){
                cur.datas[end + 1] = cur.datas[end];
                cur.pSub[end + 2] = cur.pSub[end + 1];
                end--;
            }else {
                break;
            }
        }

        cur.datas[end + 1] = key;
        cur.pSub[end + 2] = sub;

        if (sub != null){
            sub.pParent[0] = cur;
        }
        cur.size[0]++;
    }

    public static boolean insert(BTreeNode[] rootArr, int key){
        // 找插入位置，如果该元素已经存在，则不插入
        ResultType ret = find(rootArr[0], key);
        if (ret.index != -1){
            return false;
        }
        int k = key;
        BTreeNode temp = null;
        BTreeNode cur = ret.bTreeNode;
        while (true){
            // 将key插入到pCur所指向的节点中
            insertKey(cur, k, temp);
            // 检测该节点是否满足B-树的性质，如果满足则插入成功返回，否则，对pCur节点进行分裂
            if (cur.size[0] < 3){
                return true;
            }

            // 申请新节点
            temp = new BTreeNode();

            // 找到pCur节点的中间位置
            // 将中间位置右侧的元素以及孩子搬移到新节点中
            int mid = 1;
            for (int i = mid + 1; i<cur.size[0]; i++){
                temp.datas[temp.size[0]] = cur.datas[i];
                temp.pSub[temp.size[0]++] = cur.pSub[i];

                // 更新孩子节点的双亲
                if (cur.pSub[i] != null){
                    cur.pSub[i].pParent[0] = temp;
                }
                // 注意：孩子比关键字多搬移一个
                temp.pSub[temp.size[0]] = cur.pSub[cur.size[0]];
                if (cur.pSub[cur.size[0]] != null){
                    cur.pSub[cur.size[0]].pParent[0] = temp;
                }
                // 更新pCur节点的剩余数据个数
                cur.size[0] -= (temp.size[0] + 1);
                // 如果分裂的节点为根节点，重新申请一个新的根节点，将中间位置数据以及分裂出的新节点插入到新 的根节点中，插入结束
                if (cur == rootArr[0]){
                    rootArr[0] = new BTreeNode();
                    rootArr[0].datas[0] = cur.datas[mid];
                    rootArr[0].pSub[0] = cur;
                    rootArr[0].pSub[1] = temp;
                    rootArr[0].size[0] = 1;
                    cur.pParent[0] = temp.pParent[0] = rootArr[0];
                    return true;
                }else {
                    // 如果分裂的节点不是根节点，将中间位置数据以及新分裂出的节点继续向pCur的双亲中进行插 入
                    k = cur.datas[mid];
                    cur = cur.pParent[0];
                }
            }
        }
    }
    /*
    中序遍历
     */
    public static void inorder(BTreeNode root){
        if (root == null){
            return;
        }

        for (int i = 0; i<root.size[0]; i++){
            inorder(root.pSub[i]);
            System.out.print(root.datas[i] + " ");
        }
        inorder(root.pSub[root.size[0]]);
    }
    public static void main(String[] args) {
        BTreeNode[] rootArr = new BTreeNode[1];
        int[] testData = new int[]{53, 139, 75, 49, 145, 36, 101};
        // 如果树为空，直接插入
        if (rootArr[0] == null){
            BTreeNode root = new BTreeNode();
            root.datas[0] = testData[0];
            root.size[0] = 1;
            rootArr[0] = root;
        }
        for (int i : testData){
            if (i != testData[0]) {
                insert(rootArr, i);
            }
        }
        inorder(rootArr[0]);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133