欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 财经 > 创投人物 > B树和B+树

B树和B+树

2025/5/10 6:55:40 来源:https://blog.csdn.net/wjm041006/article/details/147836405  浏览:    关键词:B树和B+树

一棵m阶B树,或者是空树,或者满足如下特性

1. 树中每个节点最多有m棵子树,且至多有m-1个关键字

2.若根节点不是叶子节点,那么至少两棵子树,至少一个关键字

3.除了根节点以外的节点,每个非叶节点至少有m/2向上取整棵子树

4.所有叶子节点(在B树中视为外部结点)都在同一个层面上

5.各个结点内关键字按照升序或者降序排列

B树所有结点都包含信息

B树的插入,如果一个结点插入后关键字个数为m,那就需要进行分裂,如果影响到了根节点,会使得B树高度加一

分裂的具体过程,将中间的数提到上面即可,然后两边结点进行分裂

最多需要3h+1次IO操作(影响到根节点)

B树的删除,如果一个结点删除后关键字个数小于最少个数,那么就需要进行合并

删除的步骤:

        1. 直接删除关键字(如果删除后没有破坏B树的性质)

        2. 破坏了,兄弟够借,就是将兄弟的一个元素放到父亲,然后父节点的一个元素降落下来

        3.兄弟不够借,那就将父亲的一个结点和自己的兄弟合并起来

在B+树中

1.每个关键字对应一棵子树

2.每个结点的关键字范围是m/2向上取整<=n<=m

3.叶子结点包含全部关键字,叶子结点包含信息,非叶子结点索引只包含对应子树最大关键字和指向该子树的指针

B+树的非叶子结点仅起到索引作用,查找成功需要查找到叶子结点,即每次查找长度都相同(保证查找公平性)

B+树支持顺序查找,所有叶子结点类似于一个链表结构

B树和B+树都能够有效支持随机查找

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词