B树

顺序查找，折半查找、分块查找等查找方法都是适用于计算机中内存较小的文件，统称为内查找法。若文件很大，且存放于外存进行查找时，这些查找方法就不适用了。

下面学习一种适用于外查找的平衡多叉树——B树。磁盘管理系统中的目录管理，以及数据库系统中的索引组织多数都采用B树这种数据结构。

B树的相关定义

一棵非空的m阶的B树，有以下性质：

1. 树种每个结点至多有m棵子树
2. 除叶子结点的其它结点都至少有两棵子树
3. 除根结点和叶子结点外其它结点都至少有$\lceil m/2\rceil$（向上取整）棵子树 $\to$向上取整
4. 所有叶子结点都处于同一层次上
5. 除叶子结点外其它结点最多有m-1个关键字

那么为什么B树被称为平衡多叉树？

“平衡”二字说明它是一棵平衡树，有平衡二叉树的性质，而平衡二叉树又属于二叉排序树，所以B树就是平衡、有序的，那么多叉呢？从它的性质可以看出来，B树不再局限于“二叉”，每个结点可以拥有多棵子树，且每个结点可以有多个关键字。

例如：上图就是一棵4阶的B树中我们可以看到，有些结点有两棵子树，有些结点有三棵子树；有些结点只有1个关键字，有些结点有2、3个关键字，这就是B树的多路。同时我们可以发现，箭头都是从关键字旁边的空白处出发，分别指向它们的子树的。如果我们将它们的子树放回到箭头出发的空白处，那么这棵B树的关键字从左往右看就是从小到大的排序，这就是B树的有序。

由上图，我们可以进一步定义B树结点的存储结构

其中parent指针指向其双亲，n表示该结点关键字的个数，$P$为指向子树的指针（也就是前面所说的空白），$K$为关键字。再由前面的性质，我们可以知道关键字的个数总是比子树的个数小1，那么它的存储结构也就好理解了。

进而再用代码来描述它：

typedef struct BTNode
{
	int keynum;				//关键字个数
	struct BTNode *parent;
	int K[m+1];				//m为B树的阶数，自己定义
	struct BTNode *ptr[m+1]	//指向子树的指针数组
	Record *recptr[m+1];
}BTNode,*BTree;

typedef struct				//用于保存查找的结果
{
	BTNode *pt;				//指向找到的结点
	int i;					//关键字序号
	int tag;				//标志域，tag=1成功，tag=0失败
}Result;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在这里需要注意每个数组的大小$m+1$，把它设为$m+1$不是没有道理的。

因为每个关键字左右都有一个指针，所以每个关键字要像前面那样排列，即下面这种间断式。

所以$K$数组的0号元素不用，是为了表示$P_0$在$K_1$的左边，那么$K$数组中$m+1$号位置有什么用？若所给值比该结点中最大关键字还要大，那么应从它右边指针指向的子树中继续去查找。这个要结合B树查找的代码一起理解。

B树的查找

由B树的存储结构可知，一个结点中的每个关键字前后都有一个指向子树的指针，因此，对于给定要查找的值$key$，我们需要与这个结点的各个关键字比较，如果等于该结点中的关键字，则查找成功；若不等于，则确定该给定值在哪棵子树。

例如：若$K_i<key<K_{i+1}$，则说明，$key$在$K_i$和$K_{i+1}$之间（它们之间有一个指向子树的指针）的子树里，进而再去子树中比较。

具体代码：

Result SearchBTree(BTree T,int key)
{					
	int i=0;
	bool found=false;			//指示是否查找成功
	BTree p,q;
	p=T;						//p指向待查找结点
	q=NULL;						//q指向p的双亲
	while(p&&!found)
	{
		i++;
		//获得满足Ki<=key
		for(;i<=p->keynum;i++)
		{
			if(key<=p->K[i])
				break;
		}
		
		if(i>0&&p->K[i]==key)
			found=true;
		else
		{
			i=0;
			q=p;
			p=p->ptr[i-1];
		}
		
		if(found)
			return(p,i,1);
		else
			return(q,i,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

在B树中的查找，无非就是两步：

1. 先找到对应结点
2. 再从结点中找对应的关键字

由于B树通常存储在磁盘上，则对结点的查找是在磁盘上进行的，而后一查找是在内存中进行的。即在磁盘上找到指针p所指结点后，先将结点中的信息读入内存，然后再利用顺序查找或折半查找查询等于$key$的关键字。显然，在磁盘上进行一次查找比在内存中进行一次查找耗费时间多出很多，所以，在磁盘上进行查找的次数，即待查找关键字所在结点在B树上的层次数，是决定B树查找效率的首要因素。

先回忆一下B树的相关性质，除根结点外的所有非终端结点至少有$\lceil m/2\rceil$棵子树。

若要求深度为$h+1$的$m$阶B树的最少结点树，根据B树的定义，第一层至少有1个结点，第二层至少有2个结点，第三层至少有$2\times \lceil m/2\rceil$个结点（第二层至少有两个结点，每个结点有至少有$\lceil m/2\rceil$棵子树），第4层至少有$2\lceil m/2{\rceil }^2$个结点（第三层有$2\lceil m/2\rceil$个结点，每个结点至少有$\lceil m/2\rceil$棵子树），…，第$h+1$层至少有$2\lceil m/2{\rceil }^{h-1}$个结点。

若该B树中有$N$个关键字，由前面可知，每个关键字左右都有一个指向子树的指针，因此可以推出叶子结点有$N+1$个。所以有$N+1\ge 2\lceil m/2{\rceil }^{h-1}$，经变换，有$h\le {\log }_{\lceil m/2\rceil }(\frac{N+1}{2})+1$。也就是说，**在含有N个关键字的B树上进行查找时，从根结点到关键字所在结点的路径上涉及的结点数（层数）不超过${\log }_{\lceil m/2\rceil }(\frac{N+1}{2})+1$。

B树的插入

B树是动态查找树，因此其生成过程是从空树起，在查找过程中通过逐个插入关键字而得到。每一次插入一个关键是在最底层（也就是叶子结点处）的某个结点中添加一个关键字，若添加后该结点关键字不超过$m-1$，则插入完成，否则说明该结点的关键字已满，这是该结点就需要分裂，将此结点在同一层分为两个结点。一般情况下分裂方法是：以中间关键字为界把结点一分为二，并把中间关键字插入到双亲结点上，若双亲结点已满，则采用同样的方法继续分解。最坏的请开个下，一直分解到树根结点，这时B树高度增加1。

例如，对下图的3阶B树进行各种插入：

1. 插入30：
   因为，该B树最大关键字为2，所以成功插入30。

2. 插入26：
   原来$(30,37)$结点插入26后变成了$(26,30,37)$，很明显关键字最大数已经超过2了，所以将中间关键字30拿到双亲结点，再将其余的分为两半，就变成了上图。

3. 插入85：
   
   原先结点的中间关键字加入到双亲结点后又满了，这时需要再一次地分裂：

算法分析：

1. 首先，若插入关键字所在的结点$K$数组未满，就很好操作，直接插入数组$K$即可
2. 若插入前$K$数组已满插入后，该结点中的关键字就为$m$个，多出了一个（最大为$m-1$个），这时就以该结点的第$\lceil m/2\rceil$个关键字$K_{\lceil m/2\rceil }$，将该结点分成3部分：$K_{\lceil m/2\rceil }$左边部分、$K_{\lceil m/2\rceil }$、$K_{\lceil m/2\rceil }$右边部分。$K_{\lceil m/2\rceil }$左边部分保留在原结点；$K_{\lceil m/2\rceil }$右边部分存放在一个新创建的结点中；$K_{\lceil m/2\rceil }$就插入到该结点的双亲结点中
3. 若步骤2中$K_{\lceil m/2\rceil }$插入到双亲结点后它的双亲结点中关键字个数又是$m$，那么就再重复步骤的操作
4. 若经2、3步骤后，某个结点的$K_{\lceil m/2\rceil }$插入到了根结点中，由于根结点无双亲结点，这时就会产生一个新的根结点，该结点的关键字是原根结点的$K_{\lceil m/2\rceil }$

具体代码：

int Roundup(int s,BTree q)
{
	s=(float)(q->keynum+1)/2;
	int s1=(q->keynum+1)/2;
	if(s-s1==0)
		return s1;
	else if(s-s1>0)
		return (s1+1);
}

int InsertBTree(BTree *T,int key,BTree q,int i)					//q表示插入的结点，i表示在K[i]和K[i+1]之间的位置，即ptr[i]
{
	int x=key,s;								//新插入的关键字
	BTree ap=NULL;
	ap=(BTree)malloc(sizeof(BTNode));							//空指针
	bool finished=false;
	while(q&&!finished)
	{
		//先把K[i]后面的元素往后移，然后i+1空出来把插入元素放进去
		for(int j=q->keynum+1;j>i+1;j--)
		{
			q->K[j]=q->K[j-1];
			q->ptr[j]=q->ptr[j-1];
		}
		q->K[i+1]=x;
		q->ptr[i+1]=ap;
		q->keynum++;
		//然后判断关键字是否超出了最大值
		if(q->keynum<m)
			finished=true;
		else
		{
			s=Roundup(s,q);
			for(int j=s+1,u=0;j<=q->keynum;j++,u++)
			{
				ap->K[u]=q->K[j];
				ap->ptr[u]=q->ptr[j];
				ap->recptr[u]=q->recptr[j];
			}
			x=q->K[s];
			q=q->parent;
			if(q)
			{
				for(int j=1;j<=q->keynum;j++)
				{
					if(x<=q->K[i])
					{
						i=j;
						break;
					}
				}
			}
		}
	}
	
	if(!finished)
	{
		BTree newT=NULL;
		newT=(BTree)malloc(sizeof(BTNode));
		newT->K[1]=x;
		newT->ptr[0]=(*T);
		newT->ptr[1]=ap;
	}
	
	return 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

B树的删除

B树的删除操作不同于一般树的删除操作，它是在B树的某个结点中删除指定的关键字及其邻近的一个指针，删除后应进行调整使该树满足B树的定义，也就是要保证每个结点的关键字数目范围为$[\lceil m/2\rceil -1,m]$，为什么是$\lceil m/2\rceil -1$？根据B树的性质，每个结点至少有$\lceil m/2\rceil$棵子树，也就是有$\lceil m/2\rceil$指向子树的指针，而关键字的个数比该指针域的个数少1。

B树的删除可以分为两大情况：删除最底层结点的关键字、删除其它层结点的关键字。

首先是能同时针对这两种情况的一种方法：

1. 将要删除记录用其右边邻近指针指向的子树中关键字最小的记录替换。这个最小的记录也就是该关键字右边的指针指向的子树中最左下的一个关键字。因为这个关键字比要删除的关键字和它前面的指针指向的子树的所有关键字大，且比它后面的指针指向的子树的所有关键字小。同时，也可以是用其左边邻近指针指向的子树中关键字最大的记录替换。例如，删除下图中的45，就用50来替代：
   

然后是一种针对删除最下层结点的关键字的方法，分为三种情况：

• 被删除关键字所在结点中的关键字数目大于等于$\lceil m/2\rceil -1$。
  只需从该结点中删除该关键字$K_i$和相应指针$P_i$，树的其它部分不变
• 被删除关键字所在结点中的关键字数目等于$\lceil m/2\rceil -1$，它的右兄弟结点中的关键字数目大于$\lceil m/2\rceil -1$。
  假设被删除关键字为所在子树为指针$P_i$所指向的结点，则需将它双亲结点中$K_{i+1}$去替换被删除关键字，而又将$P_{i+1}$所指子树中最小的关键字去替换$K_{i+1}$
• 被删除关键字所在结点和它的兄弟结点中的关键字数目等于$\lceil m/2\rceil -1$。
  假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针$P_i$所指，则在删除关键字之后，它所在结点中剩余的关键字、指针和双亲结点中的关键字$K_i$一起合并到$P_i$所指的兄弟结点中

上述的右兄弟结点只是一个特例，左兄弟结点也可以，不过某些地方要做一些小小的调整。

具体算法：待写——

B+树

B+树是B树的一种变形树。其性质如下：

1. 有n棵子树的结点中含有n个关键字
2. 非终端结点中仅含有子树中的最大关键字
3. 最底层的结点（叶子结点）包含了B+树种所有关键字的信息，还包含了指向这些关键字的指针，且结点中的关键字依从小到大的顺序排列
4. 通常在B+树上有两个指针，一个指向根结点，一个指向有最小关键字的结点，分别可以进行两种查找运算：从根结点开始、从最小关键字开始

例如下图：
代码待学习

总结

B树本质上还是一棵树，且有平衡二叉树的性质，不过是从二叉变成多叉，每个结点中可以有好几个关键字和好几棵，主要用于外查找，也就是在外存中查找。比如磁盘管理系统中的目录管理以及数据库系统中的索引组织等。
B+树不能说是一种特殊的B树，它们两者的性质相差还是比较大的，只能说是B树的一种变形。B+树就在于“+”，结点中增加了相应的一些信息，且B+树的各种限制也更好理解。因为它独特的存储结构，相较于B树，它更适用于文件索引系统。