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┐-1typedef 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
     
      key[i];i--)； //从后向前找第1个小于等于K的关键字  if(i>0 && T->key[i]==1){ //查找成功，返回T及i    *pos=i；    return T；   } //结点内查找失败，但T->key[i]
      
       
        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等关键字的过程【】。