多路查找树（B树）_4阶b+树最多关键字个数

多路查找树

下面的图片均来自教材《大话数据结构》和《数据结构(C语言版)》

前面文章中的数据结构，处理数据都是在内存中
若操作的数据集非常大，就需要不断从硬盘等存储设备中调入或调出数据

多路查找树其每个结点的孩子数可以多于两个，且每个结点处可以存储多个元素
（前面文章谈到的树中结点每个结点仅存储一个元素）

B树是针对内存与外存之间的存取而专门设计的

结点最大的孩子数目称为B树的阶

1.三阶B树（2-3树）

2-3树中有2结点（此结点的孩子有2个，存储1个元素）和3结点（此结点的其孩子有3个，存储2个元素）
所有叶子结点在同一层次（深度）

4 $<$ 8 $<$ 12 $<$ 14
1 $<$ 4 $<$ 6 $<$ 7 \qquad 9 $<$ 10 $<$ 12 $<$ 13 $<$ 14 $<$ 15

左孩子元素 $<$ 双亲元素 $<$ 右孩子元素

1.1 三阶B树的元素插入

插入元素3，因为 1(双亲左孩子) $<$ 3 $<$ 4（双亲结点），所以插入位置如下图

插入元素5，因为1，3（双亲左孩子） $<$ 4（双亲结点）$<$ 5 $<$ 6，7（双亲右孩子）
因为这是一个三阶B树（一个结点最多有3个孩子，此结点最多存储着2个元素）
如果将5，6，7作为一个结点（存储3个元素），这将会产生4个孩子，所以不符合要求。
双亲结点4目前只存储着1个元素，故可以向此结点4填入一个结点6（由于4 $<$ 5 $<$ 6)

总之：5替6，6移上

插入元素11，结点（9，10）变为（9，10，11）不符合三阶B树要求，故需拆解此结点，将结点10上移至结点（12，14）变为（10，12，14）不符合三阶B树要求，故需拆解此结点，将结点12上移至结点8变为（8，12）

插入元素2，结点（1，3）变为（1，2，3）不符合三阶B树要求，故需拆解此结点，将结点2上移至结点（4，6）变为（2，4，6）不符合三阶B树要求，故需拆解此结点，将结点4上移至结点（8，12）变为（4，8，12）不符合三阶B树要求，故需拆解此结点

1.2 三阶B树的元素删除

1.2.0 删除3结点（叶子结点）上的元素

删除结点（9，10）中元素9

1.2.1 删除2结点（叶子结点）上的元素

删除结点1，使得结点4（2结点）不满足拥有2个孩子

情形一：
删除结点1，左旋使得结点6作为双亲，结点4作为结点6的左孩子，结点7作为结点6的右孩子

情形二：
删除结点4，左旋结点6，结点7（变为双亲），使得此结点7没有右孩子，将结点8下移到右孩子位置（结点8 $>$ 结点7）
将结点9替代原先结点9的位置（结点7 $<$ 结点9 $<$ 结点12）

情形三：
删除结点12，结点（12，14）变为结点14，而此结点（12，14）原有3个孩子，所以现在应该将结点14增添进一个元素，使得此结点变为3结点（结点有3个孩子）
因为结点9 $<$ 结点10 $<$ 结点13，所以将结点10上移

情形四：
删除结点8，结点7无右孩子，结点6，7合并后，所有叶子结点要保持同一深度，所以得合并其他结点，这里我们将结点9和结点14合并

删除结点4，将结点6上移

2.四阶B树（2-3-4树）

2.1 四阶B树的元素(关键字)插入

2.2 四阶B树的元素(关键字)删除

删除顺序：1、6、3、4、5、2、9

3.B树（平衡多路查找树）

B树的结点存储结构

#define m 3 //B树的阶(结点最多有m个孩子)
//结点类型
typedef struct BTNode{
	int keynum;	//单个结点中关键字的个数
	struct BTNode *parent;	//结点指向其双亲
	KeyType K[m+1];	//存储关键字数组，0号下标弃用  
	struct BTNode *ptr[m+1];	//指针数组（数组中元素为指针）指向结点的子树根结点
	Record *recptr[m+1];	//记录指针，0号下标弃用
}BTNode,*BTree;
//查找结果类型
typedef struct{
	BTNode *pt;	//指向找到的结点
	int i;	//结点中关键字的序号(1..m)
	int tag;  //1:查找关键字成功 0:查找失败
}Result;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.1 B树中元素(关键字)的查找

先查找结点，再查找结点内存储的关键字

Result SearchBTree(BTree T,KeyType key){
	p=T;	//p指向待查结点
	q=NULL;	//q指向p的双亲
	found=FALSE;
	i=0;
	while(p && !found){
		i=Search(p,key); //在p所指的结点中的所有关键字中返回某一关键字的下标,使得p->key[i]<= key < p->key[i+1]
		if(i>0 && p->K[i]==key)
			found=TRUE;
		else{
			q=p;	//q指向p所指结点(p所指结点作为下一待查结点的双亲)
			p=p->ptr[i]; //新p指向原p的子树根结点
		}
		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

下图为不同关键字对应的B树
(b)1个关键字，B树有一层
©2个关键字，B树有两层
(d)3个关键字，B树有三层
(e)4个关键字，B树有三层
(f)5个关键字，B树有三层
关键字个数 $\le$ 6，B树至少3层
(g)7个关键字，B树有3层
B树深度为4，关键字个数 $\ge$ 7

3.2 B树中元素(关键字)的插入

//在m阶B树T上结点*q的关键字key[i]和关键字key[i+1]之间插入关键字K
Status InsertBTree(BTree &T,KeyType K, BTree q, int i){
	x=K;	//x为待插入的关键字
	ap=NULL;
	finished=FALSE;
	while(q && !finished){
		Insert(q,i,x,ap);	//将x和ap分别插入到q->key[i+1]和q->ptr[i+1]
		if(q->keynum < m)
			finished=TRUE;	//插入完成
		else				//分裂结点*q
		{	//将q->key[s+1...m],q->ptr[s..m]和q->recptr[s+1..m]移入新结点*ap
			s=ceil(m/2);  split(q,s,ap); x=q->key[s];	
			q=q->parent;
			if(q)	//在双亲结点*q中查找x的插入位置
				i=Search(q,x);
		}
	}
	if(!finished)	//T是空树或根结点已分裂成为结点*q和*p
		NewRoot(T,q,x,ap);	//生成含(T,x,ap)的新的根结点*T，原T和ap为子树指针
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4.B+树

B+树是应文件系统所需而出的一种B树的变形树
每一个叶子结点都会保存一个指向后一叶子结点的指针