B-树

时间：2014-03-23 09:23:35 阅读：472 评论：0 收藏：0 [点我收藏+]

【B-树】

　　B-树是一种多路搜索树（并不是二叉的）。相当于压缩后的平衡二叉排序树。

　　 bubuko.com,布布扣

【B-树特性】

　1.关键字集合分布在整颗树中；

　2.任何一个关键字出现且只出现在一个结点中；

　3.搜索有可能在非叶子结点结束；

　4.其搜索性能等价于在关键字全集内做一次二分查找；

　5.自动层次控制；

　由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为：其中，M为设定的非叶子结点最多子树个数，N为关键字总数；所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟节点合并.

参考：

B-树,布布扣,bubuko.com

B-树

原文：http://www.cnblogs.com/tekkaman/p/3618290.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)