诚讯网站设计,中国建设银行网站济南网点,高端网站建设团队,鑫诺科技网站建设一、B树 B树是一种多路搜索树#xff08;并不是二叉的#xff09;#xff0c;性质如下#xff1a; 1、定义任意非叶子结点最多只有M个儿子#xff1b;且M2#xff1b; 2、根结点的儿子数为[2, M]#xff1b; 3、除根结点以外的非叶子结点的儿子数为[M/2, M]#…一、B树 B树是一种多路搜索树并不是二叉的性质如下 1、定义任意非叶子结点最多只有M个儿子且M2 2、根结点的儿子数为[2, M] 3、除根结点以外的非叶子结点的儿子数为[M/2, M] 4、每个结点存放至少M/2-1取上整和至多M-1个关键字至少2个关键字 5、非叶子结点的关键字个数指向儿子的指针个数-1 6、非叶子结点的关键字K[1], K[2], …, K[M-1]且K[i] K[i1] 7、非叶子结点的指针P[1], P[2], …, P[M]其中P[1]指向关键字小于K[1]的 子树P[M]指向关键字大于K[M-1]的子树其它P[i]指向关键字属于(K[i-1], K[i])的子树 8、所有叶子结点位于同一层。 B树的特点 1、关键字集合分布在整颗树中 2、任何一个关键字出现且只出现在一个结点中 3、搜索有可能在非叶子结点结束 4、其搜索性能等价于在关键字全集内做一次二分查找 5、自动层次控制。 二、B树 B树 B树是B树的变体也是一种多路搜索树特点如下 1、其定义基本与B-树同 2、非叶子结点的子树指针与关键字个数相同 3、非叶子结点的子树指针P[i]指向关键字值属于[K[i], K[i1])的子树B-树是开区间 4、为所有叶子结点增加一个链指针 5、所有关键字都在叶子结点出现。 B的搜索与B-树也基本相同区别是B树只有达到叶子结点才命中B-树可以在非叶子结点命中其性能也等价于在关键字全集做一次二分查找 B的特性 1、所有关键字都出现在叶子结点的链表中稠密索引且链表中的关键字恰好是有序的 2、不可能在非叶子结点命中 3、非叶子结点相当于是叶子结点的索引稀疏索引叶子结点相当于是存储关键字数据的数据层 4、更适合文件索引系统。 三、B*树 是B树的变体在B树的非根和非叶子结点再增加指向兄弟的指针。 B*树定义了非叶子结点关键字个数至少为(2/3)*M即块的最低使用率为2/3代替B树的1/2 B树的分裂当一个结点满时分配一个新的结点并将原结点中1/2的数据复制到新结点最后在父结点中增加新结点的指针B树的分裂只影响原结点和父结点而不会影响兄弟结点所以它不需要指向兄弟的指针B*树的分裂当一个结点满时如果它的下一个兄弟结点未满那么将一部分数据移到兄弟结点中再在原结点插入关键字最后修改父结点中兄弟结点的关键字因为兄弟结点的关键字范围改变了如果兄弟也满了则在原结点与兄弟结点之间增加新结点并各复制1/3的数据到新结点最后在父结点增加新结点的指针所以B*树分配新结点的概率比B树要低空间使用率更高 四、小结 B-树多路搜索树每个结点存储M/2到M个关键字非叶子结点存储指向关键字范围的子结点所有关键字在整颗树中出现且只出现一次非叶子结点可以命中 B树在B-树基础上为叶子结点增加链表指针所有关键字都在叶子结点中出现非叶子结点作为叶子结点的索引B树总是到叶子结点才命中 B*树在B树基础上为非叶子结点也增加链表指针将结点的最低利用率从1/2提高到2/3。 参考资料
1、七月算法--从B树、B树、B*树谈到R 树 http://blog.csdn.net/v_july_v/article/details/6530142
2、B树、B树、B*树 http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html
