算法

B-树是一种多路搜索树(并不一定是二叉的)

1970年,R.Bayer和E.mccreight提出了一种适用于外查找的 ,它是一种平衡的多叉树,称为B树(或B-树、B_树)。

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树,或者是满足下列性质的树:

1、根结点至少有两个子女;

2、每个非根节点所包含的关键字个数 j 满足:┌m/2┐ – 1 <= j <= m – 1;

3、除根结点以外的所有结点(不包括叶子结点)的度数正好是关键字总数加1,故 内部子树个数 k 满足:┌m/2┐ <= k <= m ;

4、所有的叶子结点都位于同一层。