通俗的B树入门及查找、插入、删除操作

定义

B树是一个查找关键字的树,树的结点存的是关键字,通过该关键字的位置可以找到对应的表,这体现了数据的索引机制.

即有索引的关键字abcde(已建立B树),现在要通过关键字c来查找.那么就在B树上查找关键字c对应的位置(及所在的结点).

B树的结构

相比于普通平衡树,B树的每个结点都存了一个类似数组的东西,用来保存关键字及关键字对应的索引(以下统称元素).

struct Node{
	T keys[N];//每个结点都存了一个类似数组的东西,用来保存关键字及关键字对应的索引.
    Node *child;//k个关键字则一定有k+1个子树.
}
1
2
3
4

在这里插入图片描述

特点

首先,本质上来说,B树就是一棵平衡树. 当结点X 只有两个子节点时, 结点X必然只有一个关键字(如10),且左子树所有关键字都小于 x的唯一关键字,同时右子树的所有关键字都大于x**的唯一关键字.

由此可见

结点x的关键字个数为k, 则结点x的子树数量为 k+1
结点内的关键字按顺序排序

查找

当前需要查找关键字x.

首先找根节点,根节点上有 k个关键字(是顺序的).

通过二分查找找到第一个大于等于x的关键字B. 如果相等就找到了.

如果不相等,说明关键字x 在关键字B左边的子树中.
用同样的方法查找B左边的子树.如此递归.如果找到了叶子结点(说明该关键字不存在)

在这里插入图片描述

例1

当前要查找5关键字

先从根节点中找到第一个大于等于5的关键字 10
发现10 > 5,说明 5 只有可能在10左边的子树中.(即3、6关键字所在的结点)

	从（3、6所在的）结点中 查找第一个大于等于5的关键字 6
	发现6 > 5,说明 5 只有可能在6左边的子树中.(即4、5关键字所在的结点)
		从（4、5所在的）结点中 查找第一个大于等于5的关键字 5
		发现找到了5关键字。查找成功！
1
2
3
4
5
6
7
8
9

例2

当前要查找8关键字

先从根节点中找到第一个大于等于8的关键字 10
发现10 > 8,说明 8 只有可能在10左边的子树中.(即3、6关键字所在的结点)

	从（3、6所在的）结点中 查找第一个大于等于8的关键字 null
	发现没有关键字大于8,说明 8 只有可能最右边的子树中.(即7、8、9关键字所在的结点)
		从（7、8、9所在的）结点中 查找第一个大于等于8的关键字 8
		发现找到了8关键字。查找成功！
1
2
3
4
5
6
7
8
9

插入

通过查找知道了 B树的查询原理后，那么B树是通过什么样的机制来维持呢？

引入B树的限制

M阶B树有以下限制

2 <= 根结点子结点个数 <= M ,因此元素个数: 1 <= 根结点元素个数 <= M-1
M/2 <= 内结点子结点个数 <= M,因此元素个数: M/2-1 <= 内结点元素个数 <= M-1
叶子结点没有子结点，但元素个数: M/2 -1<= 元素个数 <= M-1

M/2 为向上取整!!!

目前只需要知道，对于每种结点都有子节点数量和元素个数的限制.因此,每当超出限制时,就需要通过一定的方式去调整.

插入中的分裂操作

对于5阶B树,

2 <= 根结点子结点个数 <= 5 ,因此元素个数: 1 <= 根结点元素个数 <= 4
3 <= 内结点子结点个数 <= 5,因此元素个数: 2 <= 内结点元素个数 <= 4
叶子结点没有子结点，但元素个数: 2 <= 元素个数 <= 4

对于插入来说,所要关注的是,结点元素个数大于限制时应该怎么做

对于任何一个结点,只要它的元素个数大于限制,那么该结点将会分裂成L,R结点:

首先从找到最中间的元素K (如果是偶数则两数随机选择),把该元素放入父亲结点中.
L,R结点为以元素K为分界,分别存左半部分和右半部分的元素.
且L是挂在元素K的左边,R是挂在元素K的右边

如有5阶B数,刚在合适的位置(这个等会说)插入了13,

但发现该结点的元素个数大于m-1,所以需要由13元素为中心来分裂,因此分裂成如下:

如何找到合适的位置

从上面的调整可以发现,B树插入的全步骤,就是

找到合适的位置放入X(有可能已经存在,就不放入)
判断有没有超过限制,而后进行调整

其实可以就是通过查找这一步骤来找到合适的位置( 如果查找到了X,那么就说明根本不需要插入了)

并且显而易见的是,合适的位置一定是在叶子结点中.(这里可以留作思考)

那么就可以通过叶子结点来不断调整维持B树的平衡.

删除

既然插入操作涉及结点超出限制,那么删除操作就肯定涉及结点少于限制的情况.

B树有一个合并的操作来处理少于限制的情况

删除中的合并

首先, 删除操作肯定是基于 B树已合法的情况下发生(即所有结点的元素个数和子结点个数都在限制范围之内)。

其次,明确一点合并的操作与 当前结点兄弟结点父亲结点 都有关.

现在先考虑在叶子结点删除了元素！！！

若当前结点元素个数不足，有以下三种选择进行（优先级从大到小）：

如自身元素个数合法，则不用处理。否则：
如相邻兄弟结点丰满（即元素个数大于下限+1），则向兄弟结点借一个元素。（具体是先从相邻方向上的父亲结点拿一个元素，而后对应相邻的兄弟补回这个元素）。否则：
与相邻的兄弟结点合并 （包括他们中间的父亲结点，因为上限是 M-1，而下限是 M/2-1）

$(\lceil M/2 \rceil - 2) + (\lceil M/2 \rceil - 1) = (2*\lceil M/2 \rceil - 3) <= M-1$