B-树

1.B-树的性质

（1）树中每个结点至多有m个子树

（2）若根结点不是叶子结点，则至少有两个子树

（3）除根结点以外所有非叶子结点至少有[m/2]（上限符号）个子树

（4）所有非终端结点包含以下信息：n,A0,K1,A1,K2,A2,……,Kn,An。其中，Ki是关键字，Ai是指向子树根结点的指针

（5）所有叶子结点都出现在同一层次上，且不带信息

2.B-树的查找

是顺指针查找结点和在结点的关键字中进行查找交叉进行的过程

3.B-树的插入

先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插入完成，否则要产生结点的分裂

4.B-树的删除

（1）找到该关键字所在结点，并从中删除之

（2）若该结点为最下层非终端结点，且其关键字数目不少于[m/2]（取上限），则删除完成。否则要进行合并结点操作

（3）若所删的关键字为非终端结点中的Ki，则可以指针Ai所指子树中最小的关键字Y替代Ki，然后在相应的结点中删去Y