0%

【算法导论】B树

发表于 更新于
本文字数： 24k 阅读时长 ≈ 34 分钟

一棵B树T是具有如下性质的有根树（设根为root）:

  • 每个节点x有一下域：

    • num,当前存储在节点x的关键字个数,关键字以非降序存放，因此$key[i]\le key[i+1]\le\cdots \le key[n]$;
    • isleaf,是一个bool值，如果x为叶子节点，则isleaf=true；
    • 每个节点包括$num+1$个指向其子女的指针$p[0], p[1], \cdots ,p[num]$。如果$x$为叶子，则$p=NULL$；
    • 每个节点包括$num$个关键字$key[0], key[1], \cdots, key[num-1]$。各关键字$key[i]$对存储在各子树中的关键字范围加以分隔： $k1\le key[1]\le k2\le key[2]\le\cdots$

  • 每个叶节点具有相同的深度；

  • 每一个节点包含的关键字有上下界。这些界可以用一个称为B树的最小度数的固定整数$M\ge2$来表示。每个非根节点的个数$n$必须满足$M-1\le n\le 2M-1$。根节点至少包括 一个关键字。如果一个节点是满的，则它恰好有$2M-1$个关键字。

​ 一棵B树可以表示如下：

图1

​ B树与红黑树的相似之处在于，每棵有$n$个节点的B树高度为$O(\log n)$，但可能要比一棵红黑树的高度小很多，因为它的分支比较多！因为在磁盘存储中，需要经常读取数据，所以选择一个大的分支因子，可以大大地降低树的高度，以及磁盘存取次数。这样说可能比较抽象，下面举例说明：下图为一棵分支因子为$1001$、高度为$2$的B树，可以看出它可以存储超过$10$亿个关键字；但是，因为根节点可以持久的保留在主存中，因此需找某个关键字至多只需要两次磁盘存取。如果用二叉树存储的话，树的深度将会很大，那么寻找位于叶子节点处的关键字将需要很多次磁盘读取！假设有$n$个节点，那么二叉树的高度为$h\le\log(n+1)$,而B树为$h\le\log((n+1)/2)/\log(M)$,其中$M$为最小度数。

图2

B树的各种操作

查找

查找b树和查找二叉树类似，就是在分支处进行判断选择正确的子树，然后递归调用。查找过程的时间复杂读为$M\log n/\log M$具体程序实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**********************************************************\
函数功能：查找关键字所在的节点
输入：    树的根，关键字
输出：    关键字所在的节点
\**********************************************************/
BtreeNode *BtreeSearch(BtreeNode *TestNode,int keyword)
{
	int i=0;
	while(i<TestNode->num&&keyword>TestNode->key[i])
		i=i+1;
	if(i<=TestNode->num&&keyword==TestNode->key[i])
		return TestNode;
	if(TestNode->isleaf)
	{
		printf("Not founded!\n");
		return NULL;
	}
	else
	{
		return BtreeSearch(TestNode->p[i],keyword);
	}
}

创建空的B树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**********************************************************\
函数功能：创建节点
输入：无
输出：新节点
\**********************************************************/
BtreeNode * BtreeCreate()
{
	BtreeNode *node=(BtreeNode *)malloc(sizeof(BtreeNode));
	if(NULL==node)
		return NULL;
	node->isleaf=true;
	node->num=0;
	for(int i=0;i<2*M;i++)
		node->p[i]=NULL;
	for(int i=0;i<2*M-1;i++)
		node->key[i]=0;
	return node;
}

插入

​ B树的插入比二叉树的插入要复杂的多，因为二叉树的插入是插入新的节点，而B树的插入是将关键字插入到已存在的节点，而节点可能已经是满节点（前面提到过），就会破坏B树的性质。因此不能将关键字插入到满节点上。根据B树的规则，每个节点的关键字个数在$[M-1, 2M-1]$之间，故当keyword(要插入的关键字)要加入到某个叶子时，如果该叶子节点已经有$2M-1$个关键字，则再加入keyword就违反了B树的定义，这时就需要对该叶子节点进行分裂，将叶子以中间节点为界，分成两个包含$M-1$个关键字的子节点，同时把中间节点提升到该叶子的父节点中，如果这样使得父节点的关键字个数超过$2M-1$，则要继续向上分裂，直到根节点，根节点的分裂会使得树加高一层。

​ 为了解决上面问题，我们需要不断地回溯，这显然比较复杂，我们可以未雨绸缪：我们不是等到发现是否真的需要分裂一个满节点时才做插入操作。相反地，当沿着树向下查找要插入关键字所处位置时，就分裂沿途遇到的每个满节点。这样做后，每当要分裂一个满节点时，就能保证其双亲不是满节点。

分裂满节点的过程图解如下：

图3

​ 我们还要考虑特殊情况：当分裂一个满的根时，需要先让根成为一个新的空根节点的孩子，这样才能被上面的分解过程分解。树的高度增加$1$，分裂是树增高的唯一途径！其操作如下图：

图4

综上所述，插入过程的具体实现如下：

删除

​ B树的删除比插入操作更加复杂，插入操作只需考虑三种情况，而删除操作需要考虑的情况很多，情况如下：

图5

​ 和插入操作类似，根据B树的规则，每个节点的关键字个数在$[M-1, 2M-1]$之间，故当keyword(要插入的关键字)要从某个叶子删除时，如果该叶子节点只有$M-1$个关键字，则再删除keyword就违反了B树的定义，这时就需要对该叶子节点进行合并。上图中各种情况中的t就是我所说的$M$即最小度数。具体程序实现如下：

下面用具体实例来形象地说明B树的操作：

假设初始的B树如下：

图6

经过一系列的插入操作后：

图7

图8

在程序中为表示方便，将关键字由字母换成了数字，A、B、C……Y、Z对应于1、2、3……25、26.

经过上面的插入操作后，紧接在进行一系列删除操作：

图9

图10

图11

具体的完整实例程序实现如下：

用于分开不同节点的关键字，下图显示是按树的层次遍历的，可以看出结果与上面插入和删除的图解过程完全相同！）：

图12

坚持原创技术分享，您的支持将鼓励我继续创作！