B树和B+树_4阶b+树最多关键字个数

B树

B树又称为多路平衡查找树，是一种组织和维护外存文件系统非常有效的数据结构。

1、 B树的定义

一棵3阶B树：

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
1、根结点至少有两个子女；
2、每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；
3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；
4、所有的叶子结点都位于同一层。
在B树中，每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。
非根非外部结点的关键字个数：1～2。
非根非外部结点的孩子结点个数：2～3。
说明：外部结点就是失败结点，指向它的指针为空，不含有任何信息，是虚设的。一棵B树中总有n个关键字，则外部结点个数为n+1。
在B树的存储结构中，结点的类型定义如下：

#define MAXM 10		//定义B树的最大的阶数
typedef   int KeyType;       	//KeyType为关键字类型
typedef struct node 
{      int keynum; 	         	 //结点当前拥有的关键字的个数
       KeyType key[MAXM];      	//[1..keynum]存放关键字
       struct node *parent;	   	//双亲结点指针
       struct node *ptr[MAXM]; 	//孩子结点指针数组[0..keynum]
}  BTNode;
1
2
3
4
5
6
7
8

2、B树的查找

将k与根结点中的key[i]进行比较：
若k=key[i]，则查找成功；
若k＜key[1]，则沿着指针ptr[0]所指的子树继续查找；
若key[i]＜k＜key[i+1]，则沿着指针ptr[i]所指的子树继续查找；
若k＞key[n]，则沿着指针ptr[n]所指的子树继续查找。

说明：当查找到某个叶结点时，若相应的指针为空，落入一个外部结点，表示查找失败。

3、 B树的插入

将关键字k插入到B树的过程分两步完成：
（1）查找该关键字的插入结点（注意B树的插入结点一定是叶子结点层的结点）。
（2）插入关键字。
在某个叶子结点中插入关键字分两种情况
插入结点有空位置，即关键字个数n＜m-1：直接把关键字k有序插入到该结点的合适位置上。
插入结点没有空位置，即原关键字个数n=m-1  分裂。

如果没有双亲结点，新建一个双亲结点，树的高度增加一层。
如果有双亲结点，将ki插入到双亲结点中。
【例9-7】 关键字序列为：
(1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15)。
创建一棵5阶B树。
注意：最多的关键字个数Max = m-1 = 4
Max=4

4、B树的删除

在B树上删除关键字k的过程分两步完成：
（1）查找关键字k所在的结点。
（2）删除关键字k。
删除关键字k分两种情况：
在叶子结点层上删除关键字k。
在非叶子结点层上删除关键字k。
注意：非根、非叶子结点的关键字最少个数Min=m/2-1
在非叶子结点上删除关键字k  在叶子结点上删除关键字k

在B树的叶子结点b上删除关键字共有以下3种情况：
假如b结点的关键字个数大于Min，说明删去该关键字后该结点仍满足B树的定义，则可直接删去该关键字。

假如b结点的关键字个数等于Min，说明删去关键字后该结点将不满足B树的定义。若可以从兄弟结点借。

假如b结点的关键字个数等于Min，说明删去关键字后该结点将不满足B树的定义。若不能从兄弟结点借。

【例9-8】对于前例生成的B树，给出删除8，16，15，4等4个关键字的过程。

B+树

B+树是B树的一些变形。一棵4阶的B+树示例：　

B+树的定义：一棵m阶B+树满足下列要求：
(1)每个结点至多有m个子女；
(2)除根结点外，每个结点至少有[m/2]个子女，根结点至少有两个子女；
(3)有k个子女的结点必有k个关键字。
B+树的查找与B树不同，当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止。
欢迎大家加我微信交流讨论（请备注csdn上添加）