[B 树、B 树、B+ 树、B* 树] - I. B 树（即 B 树）的定义和操作

1.1、定义

B-tree即B树，B是Balanced，平衡的意思，因为B树的原英文名称为B-tree，国内很多人将其译为B-tree，所以B树就是B-树。

磁盘管理系统中的目录管理，以及数据库系统中的索引组织多数都采用B树这种数据结构。

一棵m阶的B树，或为空树，或是满足以下特性的m叉树：

1. 树中每个结点至多有m棵子树；
2. 若根结点不是叶子结点，则至少有两棵子树；
3. 除根之外的所有非终端结点至少有[m/2]（向上取整）棵子树；
4. 所有叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点（失败结点并不存在，指向这些结点的指针为空，引入失败结点是为了便于分析B树的查找性能）；
5. 所有非终端结点最少有[m/2]-1个关键字，最多有m-1个关键字，结点的结构如图所示：
   
   其中，n为结点中关键字的个数，K为关键字，且；P为指向子树根结点的指针，且指针所指子树中所有结点的关键字均小于，所指子树中所有结点的关键字均大于。
   对任一关键字K而言，相当于指向其左子树，相当于指向其右子树。
   B树具有平衡、有序、多路的特点。
   
   具体实现时，为记录其双亲结点，B树结点的存储结构通常会增加一个parent指针，指向其双亲结点，如图：
   

#define MaxSize 3

typedef struct BTnode{
    int keynum;//结点中关键字的个数，即结点的大小
    struct BTnode *parent;//指向双亲结点
    ElemType key[m+1];//关键字向量，0号单元未用
    struct BTnode *ptr[m+1];//子树指针向量
    Record *recptr[m+1];//记录指针向量，0号单元未用
}BTnode, *BTree;

//B树查找结果类型
typedef struct{
    BTnode *pt;
    int i;//1...m，在结点中的关键字序号
    int tag;//1：查找成功，0：查找失败
}Result;

1.2、操作

1.2.1、查找

算法思想：
将给定值key与根结点的各个关键字进行比较，由于该关键字序列是有序的，所以查找时可采用顺序查找，也可采用折半查找，查找时：

1. 若，则查找成功；
2. 若，则顺着指针所指向的子树继续向下查找；
3. 若，则顺着指针所指向的子树继续向下查找；
4. 若，则顺着指针所指向的子树继续向下查找。
5. 如果在自上而下的查找过程中，找到了关键字key，则查找成功，如果直到叶子结点也未找到，则查找失败。

1.2.2、插入

思想：针对m阶高度h的B树，插入一个元素时，首先在B树中是否存在，如果不存在，即在叶子结点处结束，然后在叶子结点中插入该新的元素。

1. 若该结点元素个数小于m-1，则直接插入；
2. 若该结点元素个数等于m-1，引起结点分裂，以该结点中间元素为分界，取中间元素（若中间元素为两个，则随机选取一个）插入到父结点中；
3. 重复上述操作，直到所有结点符合B树的规则，最坏的情况是一直分裂到根结点，生成新的根结点，高度增加1。

示例分析：
以5阶B树为例，5阶B树的规则：

1. 2<=根结点的子树<=5；
2. 3<=分支结点的子树<=5
3. 1<=根结点元素个数<=4
4. 2<=分支结点元素个数<=4
   
   
   

1.2.3、删除

首先查找B树中需删除的元素,如果该元素在B树中存在，则将该元素在其结点中进行删除；删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素(“左孩子最右边的节点”或“右孩子最左边的节点”)到父节点中，然后是移动之后的情况；如果没有，直接删除。

1. 某结点中元素数目小于[m/2]-1,则需要看其某相邻兄弟结点是否丰满；
2. 如果丰满（结点中元素个数大于(m/2)-1），则向父节点借一个元素来满足条件；
3. 如果其相邻兄弟都不丰满，即其结点数目等于(m/2)-1，则该结点与其相邻的某一兄弟结点进行“合并”成一个结点；
   以5阶B树为例，详细讲解删除的动作：
   如图依次删除依次删除【8】,【20】,【18】,【5】