博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
B*树
阅读量:5099 次
发布时间:2019-06-13

本文共 496 字,大约阅读时间需要 1 分钟。

  B*-tree是B+-tree的变体,在B+树的基础上(所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针),B*树中非根和非叶子结点再增加指向兄弟的指针;B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2)。给出了一个简单实例,如下图所示:

  

  B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针。

  B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。

所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

 

转载于:https://www.cnblogs.com/vipchenwei/p/7894881.html

你可能感兴趣的文章
springboot笔记04——读取配置文件+使用slf4j日志
查看>>
[Swift]LeetCode653. 两数之和 IV - 输入 BST | Two Sum IV - Input is a BST
查看>>
[Swift]LeetCode922.按奇偶排序数组 II | Sort Array By Parity II
查看>>
微信小程序的wxml文件和wxss文件在webstrom的支持
查看>>
Html5 离线页面缓存
查看>>
[php]在PHP中读取和写入WORD文档的代码
查看>>
WCF傻瓜模式写程序
查看>>
《绿色·精简·性感·迷你版》易语言,小到不可想象
查看>>
Java Web学习总结(13)Listener监听器
查看>>
开始Flask项目
查看>>
Ruby:多线程队列(Queue)下载博客文章到本地
查看>>
Android打包key密码丢失找回
查看>>
03 jQuery动画
查看>>
医药箱APP静态小项目
查看>>
安装使用eclipse
查看>>
VC6.0调试技巧(一)(转)
查看>>
linux命令
查看>>
类库与框架,强类型与弱类型的闲聊
查看>>
webView添加头视图
查看>>
php match_model的简单使用
查看>>