| 一棵m阶的B_树，或为空树，或为满足下列特性的m叉树。
|
|
|
|
|
|
|
（3）除根之外的所有非终端结点最少有 棵子树。
|
|
|
|
|
| （n，A0，K1，A1，K2，A2，…，Kn，An）
|
|
|
其中，Ki（i=1，2，…，n）为关键字，且Ki<Ki+1（i=1，2，…，n-1）；Ai（i=0，1，…，n）为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki（i=1，2，…，n），An所指子树中所有结点的关键字均大于Kn，n为结点中关键字的个数且满足 。
|
|
|
| （5）所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。
|
|
|
|
|
|
|
|
|
| 由B_树的定义可知，在B_树上进行查找的过程是：首先在根结点所包含的关键字中查找给定的关键字，若找到则成功返回；否则确定待查找的关键字所在的子树并继续进行查找，直到查找成功或查找失败（指针为空）时为止。
|
|
|
B_树上的插入和删除运算较为复杂，因为要保证运算后结点中关键字的个数大于等于 ，因此涉及结点的“分裂”及“合并”问题。
|
|
|
| 在B_树中插入一个关键字时，不是在树中增加一个叶子结点，而是首先在低层的某个非终端结点中添加一个关键字，若该结点中关键字的个数不超过m-1，则完成插入；否则，要进行结点的“分裂”处理。所谓“分裂”，就是把结点中处于中间位置上的关键字取出来插入到其父结点中，并以该关键字为分界线，把原结点分成两个结点。“分裂”过程可能会一直持续到树根。
|
|
|
同样，在B_树中删除一个结点时，首先找到关键字所在的结点，若该结点在含有信息的最后一层，且其中关键字的数目不少于 ，则完成删除；否则需进行结点的“合并”运算。
|
|
|
| 若待删除的关键字所在的结点不在含有信息的最后一层，则将该关键字用其在B_树中的后继替代，然后删除其后继元素，即将需要处理的情况统一转化为在含有信息的最后一层再进行删除运算。
|
|
|
