详解数据结构——B-树

数据结构课程设计用,简单学一下,不过好像有点难。。?

我想我需要纠正一下这个数据结构的名称,此前我一直称它为B树,但有些教程把它叫做B-树或者B_树,其实它们都是一样的。

B-树的基本概念

B-树中所有结点中孩子结点个数的最大值成为B-树的阶,通常用m表示,从查找效率考虑,一般要求m>=3。一棵m阶B-树,或者是一棵空树,需要满足下面的特性:

  • 树中每个结点至多有 m 棵子树,每个结点最多有m个分支(子树),而最少分支数要看是否为根节点。
  • 除根之外的所有非终端结点至少有两棵子树;根非叶节点至少有ceil(m/2)个分支。(ceil代表向上取整)
  • 所有的非终端结点中包含下列信息数据:(n,A0,K1,A1,K2,A2,…,Kn,An);

其中n为该结点中关键字的个数;ki为该结点的关键字且满足ki < ki+1;Ai为该结点的孩子结点指针,且满足Ai所指结点上的关键字 > Ki 且 < Ki+1,A0所指结点上的关键字小于K1,An所指结点上的关键字 > Kn

  • 结点内各关键字互不相等且按从小到大排列,如果一个结点有n-1个关键组,那么该结点有n个分支。
  • 叶子结点处于同一层;可以用空指针表示,是查找失败到达的位置。

简单来说,B树的阶是人为定义的,假如有一个4阶的B树,则除了叶结点都是NULL外,其他的结点最多保存3个信息和4个连接域,而且这是互相关联的。如果要保存2个信息则必须是3个连接域,保存1个信息则必须是2个连接域。B树本身也就是一种二叉排序树,所以也适用二叉排序树的一些性质。

下图展示了一个4阶的B树。解释一下每个结点,最左边的数字代表的是这个结点的元素个数,4阶的话元素个数最多是3。对于只有1个元素的结点,应该有2个连接域,对于只有2个元素的结点应该有3个连接域,3个元素的结点应该有4个连接域,多个元素存在的情况下应该保持有序。

由于B-树具有分支多层数少的特点,使得它更多应用在数据库系统中。将大型数据库文件存储在硬盘上,为了减少访问次数,就可以使用B-树。它的检索效率很不错。

B树相对于平衡二叉树的不同是,每个节点包含的关键字增多了,特别是在B树应用到数据库中的时候,数据库充分利用了磁盘块的原理(磁盘数据存储是采用块的形式存储的,每个块的大小为4K,每次IO进行数据读取时,同一个磁盘块的数据可以一次性读取出来)把节点大小限制和充分使用在磁盘快大小范围;把树的节点关键字增多后树的层级比原来的二叉树少了,减少数据查找的次数和复杂度;

B-树的查找操作

以上图为例,演示一下查找的过程。B树的查找是二叉排序树的扩展,区别在于二叉排序树是二路查找,而B树是多路查找。

又因为B树某结点内部元素是有序的,在结点内查找时可以二分查找来提升速度(确信

假如我们要查找53和20,在查找53的时候,先从根结点开始,比较大小,如果比根大则去右子树,否则去左子树。(二叉排序树性质)

重点来了,现在到了43和78的结点,查找的53要比43大,所以是不会到达39的结点的。然后对比78,如果比78大的话则肯定去了99所在的结点,不过我们查找的53在43和78之间,所以会进47 53 64的结点,此时再从左到右进行查找,就可以找到53。

如果要查找20,首先从根节点往左子树出发,发现18,然后往右子树出发,右子树发现27,往左子树出发,发现NULL,表示查找失败,这个B树里没有20。

叶子结点不保存任何信息,如果某次查找跑到了叶子结点,则表示查找失败。

B树的标准的查找规则如下,假设查找key:

  1. 先让key与根结点中的关键字比较,如果key等于K[i](K[]为结点内的关键字数组),则查找成功
  2. 若key < K[1],则到A[0]所指示的子树中进行继续查找(A[]为结点内的指针数组),这里要注意B-树中每个结点的内部结构。
  3. 若key > K[n],则到A[n]所指示的子树中继续查找。
  4. 若K[i] < key < K[i+1],则沿着指针A[I]所指示的子树继续查找。
  5. 如果最后遇到空指针,则证明查找不成功。

B-树的插入与构筑操作

B-树也是从空树开始,不断插入新的数据元素构筑的。但是B-树构建的过程与前面的二叉排序树和AVL树不同,B-树在插入新的数据元素时并不是每次都向树中插入新的结点。因为对于m阶的B-树来说,在定义中规定所有的非终端结点(终端结点即叶结点,关键字个数为0)包含关键字个数范围是[ceil(m / 2) - 1, m - 1],所以在插入新的数据元素时,首先向最底层的某个非终端结点中添加,如果该结点中的关键字个数没有超过m-1,则直接插入成功,否则还需要继续对该结点进行处理。

对于关键字的插入,需要找到插入为位置。在B-树的查找过程中,当遇到空指针时,则证明查找不成功,同时也找到了插入位置,即根据空指针可以确定在最底层非叶节点中的插入位置。由此可见,B树的结点插入总是在终端结点上。但是,在插入过程中有可能会破坏B-树的特征,比如一个4阶的B-树出现了一个结点保存4个数据+5个连接域的情况,这种情况就需要一个“裂开”操作,即拆分结点。

假设有关键字序列{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15},以此构筑一棵5阶B-树,过程如下。

确定结点中关键字个数的范围

由于要求5阶,则关键字个数的范围为2-4。

2是怎么算出来的?因为根非叶节点至少有ceil(m/2)个分支,所以5阶的话最少要有3个分支,3个分支则必定有2条关键字。

4是怎么算出来的?因为是5阶,所以每个结点最多有5个连接域,所以最多有4个关键字。

确定根节点

由于根节点可以最多容纳4个信息,则根节点应该是下图这样:

插入后续节点 拆分操作

当准备插入11时,11是不可以再插入到根节点了,因为这样关键字的个数变成了5,超出了范围,此时需要进行拆分操作。

拆分时需要取关键字数组的中间位置,这里由于11的加入,关键字的个数会变成5,取中间位置应该是3而不是2。我们让k[3] = 6作为一个新的根节点,6左右的关键字分别做成两个结点,作为新结点的两个分支。此时变成了这样。

新关键字总是插在叶子结点上。当插入4 8 13后,树变成了:

插入关键字10需要插在8和11之间,此时又会出现需要拆分的情况,拆分时需要把10放入根节点,并把10左右的关键字拆成两个新结点连在根节点上。

(图我不画了,太麻烦了QAQ)

按照上述步骤,插入过程中不超范围就直接插,超出范围就让它裂开,最后它会变成这样:

(手画了个,将就着看吧x)

需要注意一个事,插入最后一个关键字15,15应该插入在14之后,此时会出现关键字个数超出范围的情况,则需要拆分,13并入根节点,13并入根节点后,根节点超出范围,需要再次拆分,10作为新的根节点,并将10左右的关键字做成两个新节点连接到新的根节点。这种插入一个关键字后出现多次拆分的情况称为连锁反应。

B-树的删除

对于删除,我们需要先找到待删除的关键字,但是直接的删除是不可以的,因为这有可能会破坏B-树的特性。比如旧关键字删除之后结点的个数不再满足定义,此时需要做出一些调整。可能需要向其兄弟结点借一些关键字或者和其孩子结点进行关键字的交换,也可能需要进行结点的合并,其中,和当前结点的孩子进行关键字交换的操作可以保证删除操作总是发生在终端结点上。

  1. 删除关键字8和16,关键字8在终端结点上,并且删除后所在结点关键字个数不会超出限制,所以可以直接删除。关键字16不在终端结点上,但是可以用17覆盖16,然后把原来的17删除掉。这里便是与孩子结点进行关键字交换的操作。这里不能用15和16进行关键字交换,因为这样会导致15所在结点中关键字的个数小于2。

  2. 删除关键字15,15虽然也在终端结点上,但是不能直接删除,因为删除后当前结点中关键字的个数小于2,这样不满足5阶B树的定义。此时需要向其兄弟结点借关键字,显然应该向其右兄弟来借关键字,因为左兄弟的关键字个数已经是下限2。借关键字不能直接将18移到15所在的结点上,因为这样会使得15所在的结点上出现比17大的关键字,所以正确的借法应该是先用17覆盖15,再用18覆盖原来的17,最后删除原来的18。

  3. 删除关键字4,4在终端结点上,但是此时4所在的结点的关键字个数已经到下限,需要借关键字。不过可以看到其左右兄弟结点已经没有多余的关键字可借。所以就需要进行关键字的合并。可以先将关键字4删除,然后将关键字5、6、7、9进行合并作为一个结点链接在关键字3右边的指针上,也可以将关键字1、2、3、5合并作为一个结点链接在关键字6左边的指针上。但是这样单纯的合并后仍然不可以,因为会出现非根的双分支结点(我就不画图了这个),这样需要继续进行合并。

参考代码

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

struct Index {
string id;
int loc;
};

//B-Tree 结点
class BTreeNode {
protected:
//string *keys;//存储关键字的数据
Index* keys;
int t; //最小度 (决定了key的数量范围)
BTreeNode** C; //存储孩子结点的数组
int n; //现在key的个数
bool leaf; //如果这个结点是一个叶子 则为TRUE , 否则 为FALSE
public:
BTreeNode(int _t, bool _leaf);
void traverse(); //遍历以该结点为根的子树中所有结点
BTreeNode* search(Index k);//在以该节点为根的子树中查找键为k的结点

void insertNonFull(Index k);
void splitChild(int i, BTreeNode* y);

friend class BTree;
};

class BTree {
protected:
BTreeNode* root; //根节点的指针
int t; //最小度
public:
BTree(int _t) {
root = NULL; t = _t;
}
void traverse() {
if (root != NULL) root->traverse();
}
BTreeNode* search(Index k) {
if (root == NULL) return NULL;
else return root->search(k);
}
void insert(Index _k);
};

BTreeNode::BTreeNode(int _t, bool _leaf) {
t = _t;
leaf = _leaf;
keys = new Index[2 * t - 1]; //一个结点key最多有2*t-1个
C = new BTreeNode * [2 * t]; //一个结点孩子最多有2*t个
n = 0; //新建结点当前key的数量为0
}

void BTreeNode::traverse() {
// 有n个key和n+1个子key,遍历n个key
// 还有前n个子key
int i;
for (i = 0; i < n; ++i) {
// 如果这不是叶节点,在打印key[i]之前先遍历以C[i]为根的子树
if (leaf == false)
C[i]->traverse();
cout << " " << keys[i].id;
}
// 打印最后一个子树的根
if (leaf == false)
C[i]->traverse();
}

BTreeNode* BTreeNode::search(Index k) {
// 找到第一个大于等于k的key
int i = 0;
while (i < n && k.id > keys[i].id)
i++;
//如果找到的key值等于k,则返回此结点
if (keys[i].id == k.id)
return this;
// 如果这里没有找到key而这里是一个叶节点
if (leaf == true)
return NULL;
// 去找一个适当的子树继续查询
return C[i]->search(k);
}

void BTree::insert(Index k) {
//如果树为空
if (root == NULL) {
root = new BTreeNode(t, true);
root->keys[0] = k; //插入 key
root->n = 1; //更新当前root结点的key的个数为1
}
else {//树不为空
// 如果树的根结点已满,则树的高度会增加
if (root->n == 2 * t - 1) {
BTreeNode* s = new BTreeNode(t, false);
// 旧的根结点成为新的根节点的孩子
s->C[0] = root;
// 拆分旧根结点并将一个key移动到新根结点上
s->splitChild(0, root);
// 新的根节点现在有了两个子结点。现在决定两个子结点中的哪一个会有新的key
int i = 0;
if (s->keys[0].id < k.id)
++i;
s->C[i]->insertNonFull(k);
//改变根节点
root = s;
}
else
root->insertNonFull(k);
}
}

// 在此结点中插入新key
// 假设在调用这个函数时,结点必须是非满的
void BTreeNode::insertNonFull(Index k) {
//将index初始化为最右边元素的索引
int i = n - 1;

// 如果这是一个叶节点
if (leaf == true) {
// 下面的循环做两件事
// a) 查找要插入新key的未知
// b) 将所有较大的key移动到前方一个位置
while (i >= 0 && keys[i].id > k.id) {
keys[i + 1] = keys[i];
i--;
}
// 在找到的位置插入新的key
keys[i + 1] = k;
n = n + 1;
}
else { // 如果这个结点不是叶节点
// 找到将拥有新key的子结点
while (i >= 0 && keys[i].id > k.id)
i--;

// 查看找到的子元素是否已满
if (C[i + 1]->n == 2 * t - 1) {
// 如果某个子结点已满,则需要对子结点进行拆分
// 机翻:如果孩子吃饱了,就把它切开(草 我裂开了
splitChild(i + 1, C[i + 1]);

// 执行拆分操作后,C[i]中间的key会上升一级,并且C[i]会一分为二
// 看看哪一个会得到新key
if (keys[i + 1].id < k.id)
i++;
}
C[i + 1]->insertNonFull(k);
}
}

// 分割此结点的子结点y
// 注意,当调用这个函数时,y必须是满的
void BTreeNode::splitChild(int i, BTreeNode* y) {
// 创建一个将要存储y结点的t-1个key的新结点
BTreeNode* z = new BTreeNode(y->t, y->leaf);
z->n = t - 1;

// 复制y中最后t-1个key到z
for (int j = 0; j < t - 1; j++)
z->keys[j] = y->keys[j + t];

// 复制y中最后t的子结点到z
if (y->leaf == false) {
for (int j = 0; j < t; ++j)
z->C[j] = y->C[j + t];
}

// 减少y中的key数量
y->n = t - 1;

// 因为这个结点将有一个新的子结点,所以要给新的子结点开辟空间
for (int j = n; j >= i + 1; --j)
C[j + 1] = C[j];

// 将新的子结点链接到此结点
C[i + 1] = z;

// 一个y的key将会移动到这个结点,找到新key的位置并将所有较大的key移动一个位置。
for (int j = n - 1; j >= i; --j)
keys[j + 1] = keys[j];

// 将y中间的key复制到这个结点
keys[i] = y->keys[t - 1];

// 此结点中的键数量增加1
n++;
}

int main() {
BTree t(3);
t.insert({ "10",1 });
t.insert({ "20",2 });
t.insert({ "5",3 });
t.insert({ "6",4 });
t.insert({ "12",5 });
t.insert({ "30",6 });
t.insert({ "7",7 });
t.insert({ "17",8 });

t.traverse();
cout << endl;
Index k = { "20",2 };
if (t.search(k) != NULL)
cout << "exist" << endl;
else
cout << "not exist" << endl;
}

参考资料

B-树及其基本操作(插入和删除)详解 http://data.biancheng.net/view/60.html

B-树(B树)详解 https://www.jianshu.com/p/7dedb7ebe033

平衡二叉树、B树、B+树、B*树 理解其中一种你就都明白了 https://zhuanlan.zhihu.com/p/27700617

代码是我同学给的,我把里面的注释给翻译了一下

打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2018-2020 Shawn Zhou
  • Powered by Hexo Theme Ayer
  • PV: UV:

感谢打赏~

支付宝
微信