B-树

1、B-树的定义
    　一棵m(m≥3)阶的B-树是满足如下性质的m叉树：
(1)每个结点至少包含下列数据域：
    (j，P₀，K_l，P₁，K₂，…，K_i，P_i)
　　其中：
    j为关键字总数
    K_i(1≤i≤j)是关键字，关键字序列递增有序：K₁ <K₂<…<K_i。
    P_i(0≤i≤j)是孩子指针。对于叶结点，每个P_i为空指针。
注意：
    　①实用中为节省空间，叶结点中可省去指针域P_i，但必须在每个结点中增加一个标志域leaf，其值为真时表示叶结点，否则为内部结点。

2、B-树的结点规模
　在大多数系统中，B-树上的算法执行时间主要由读、写磁盘的次数来决定，每次读写尽可能多的信息可提高算法得执行速度。
　B-树中的结点的规模一般是一个磁盘页，而结点中所包含的关键字及其孩子的数目取决于磁盘页的大小。

3、B-树的存储结构

#define Max l000 //结点中关键字的最大数目：Max=m-1，m是B-树的阶
#define Min 500 //非根结点中关键字的最小数目：Min=┌m/2┐-1
typedef int KeyType； //KeyType应由用户定义
typedef struct node{ //结点定义中省略了指向关键字代表的记录的指针
  　int keynum； //结点中当前拥有的关键字的个数，keynum《Max
  　KeyType key[Max+1]； //关键字向量为key[1..keynum]，key[0]不用。
  　struct node *parent； //指向双亲结点
  　struct node *son[Max+1]；//孩子指针向量为son[0..keynum]
 }BTreeNode；
typedef BTreeNode *BTree；

注意：
　为简单起见，以上说明省略了辅助信息域。在实用中，与每个关键字存储在一起的不是相关的辅助信息域，而是一个指向另一磁盘页的指针。磁盘页中包含有该关键字所代表的记录，而相关的辅助信息正是存储在此记录中。

B-树上的基本运算

1、B-树的查找
（1）B-树的查找方法
　在B-树中查找给定关键字的方法类似于二叉排序树上的查找。不同的是在每个结点上确定向下查找的路径不一定是二路而是keynum+1路的。

（2）B-树的查找算法

BTreeNode *SearchBTree(BTree T，KeyType K，int *pos)
 { //在B-树T中查找关键字K，成功时返回找到的结点的地址及K在其中的位置*pos
//失败则返回NULL，且*pos无定义
  int i；
  T→key[0]=k; //设哨兵．下面用顺序查找key[1..keynum]
  for(i=T->keynum；K<t->key[i];i--)； //从后向前找第1个小于等于K的关键字
  if(i>0 && T->key[i]==1){ //查找成功，返回T及i
    *pos=i；
    return T；
   } //结点内查找失败，但T->key[i]<K<T->key[i+1]，下一个查找的结点应为
     //son[i]
  if(!T->son[i]) //*T为叶子，在叶子中仍未找到K，则整个查找过程失败
    return NULL；
    //查找插入关键字的位置，则应令*pos=i，并返回T，见后面的插入操作
  DiskRead(T->son[i])； //在磁盘上读人下一查找的树结点到内存中
  return SearchBTree(T->Son[i]，k，pos)； //递归地继续查找于树T->son[i]
 }

（3）查找操作的时间开销
　B-树上的查找有两个基本步骤：
　①在B-树中查找结点，该查找涉及读盘DiskRead操作，属外查找；
　②在结点内查找，该查找属内查找。
　查找操作的时间为：
　①外查找的读盘次数不超过树高h，故其时间是O(h)；
　②内查找中，每个结点内的关键字数目keynum<m(m是B-树的阶数)，故其时间为O(nh)。

（4）B-树的生成
　由空树开始，逐个插入关键字，即可生成B-树。
【例】以关键字序列(a，g，f，b，k，d，h，m，i，e， s，i，r，x，c，l，n，t，u，p)建立一棵5阶B-树的生长过程【参见动画演示】

3、B-树的删除
（1）删除操作的两个步骤
　第一步骤：在树中查找被删关键字K所在的地点
　第二步骤：进行删去K的操作
　删除5阶B-树的h、r、p、 d等关键字的过程【参见动画演示】。