B-树的高度及性能分析
B-树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成。B-树上大部分基本操作所需访问盘的次数均取决于树高h。关键字总数相同的情况下B-树的高度越小,磁盘I/O所花的时间越少。
与高速的CPU计算相比,磁盘I/O要慢得多,所以有时忽略CPU的计算时间,只分析算法所需的磁盘访问次数(磁盘访问次数乘以一次读写盘的平均时间(每次读写的时间略有差别)就是磁盘I/O的总时间)。
1、B-树的高度
定理9.1 若n≥1,m≥3,则对任意一棵具有n个关键字的m阶B-树,其树高h至多为:logt((n+1)/2)+1。
这里t是每个(除根外)内部结点的最小度数,即t=[m/2]。
由上述定理可知:B-树的高度为O(logtn)。于是在B-树上查找、插入和删除的读写盘的次数为O(logtn),CPU计算时间为O(mlogtn)。
2、性能分析
①n个结点的平衡的二叉排序的高度H(即lgn)比B-树的高度h约大lgt倍。
【例】若m=1024,则lgt=lg512=9。此时若B-树高度为4,则平衡的二叉排序树的高度约为36。显然,若m越大,则B-树高度越小。
②若要作为内存中的查找表,B-树却不一定比平衡的二叉排序树好,尤其当m较大时更是如此。
因为查找等操作的CPU计算时间在B-树上是
O(mlogtn)=0(lgn·(m/lgt))
而m/lgt>1,所以m较大时O(mlogtn)比平衡的二叉排序树上相应操作的时间O(lgn)大得多。因此,仅在内存中使用的B-树必须取较小的m。(通常取最小值m=3,此时B-树中每个内部结点可以有2或3个孩子,这种3阶的B-树称为2-3树)。
B+树
B+树是B-树的变体,也是一种多路搜索树:
1.其定义基本与B-树同,除了非叶子结点的子树指针与关键字个数相同;
2.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);
3.为所有叶子结点增加一个链指针;
4.所有关键字都在叶子结点出现;如:(M=3)。如图:
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+树要低,空间使用率更高;
- 大小: 37 KB
- 大小: 41.3 KB
分享到:
相关推荐
烧伤创疡再生医疗技术治疗手指末节损伤疗效分析.pdf
其实最终的目的都是围绕一个——方便优化,就是减小路由表大小,提升设备性能,加快数据的转发,但是单纯的区域划分只是让它有了一个层次化,并不能实际的减小路由表大小,所以ospf有了区域优化的功能。
ospf 重发布 ,汇总, 末节, 虚拟连接的实验报告
web前端期末节课大作业 ,...有个人中心、我的信息、班级信息、短信息、学院通知、我的异议、教务中心、我的报考、我的成绩、我的书籍、学习中心、资料下载、学习历程、财务中心、我的财务、教学系统等系统功能菜单。
原位再生医疗技术治疗手指末节缺损的临床效果.pdf
web前端期末节课大作业 ,html+css+javascript实现~ jQuery小米官网竖直分类导航菜单基于jquery-1.4.2.min.js制作,页面左侧竖直显示详细产品分类导航菜单。
web前端期末节课大作业 ,html+css+javascript实现~ (功能齐全)小米商城官网首页模板,包括导航栏,商品分类菜单等。
web前端期末节课大作业 ,html+css+javascript实现~红色简单自考大学官网HTML模板,界面简洁,全套模板,包括首页、学校简介、校园风光、招生动态、网上报名等网站模板页面。
web前端期末节课大作业 ,html+css+javascript实现绿色特产商城购物网HTML模板,DIV+CSS布局,全套模板,包括商城首页、特色产品、产品详情、相关资讯、商城简介、注册、登录等HTML商城模板
web前端期末节课大作业 ,html+css+javascript实现~HTML学校后台用户登录界面模板,江西师范大学软件学院毕业设计选题,选项卡切换不同角色的登录,分别是学生登录、导师登录、教务登录,有表单验证功能。
web前端期末节课大作业 ,html+css+javascript实现 红色教育培训画室HTML网站模板,DIV+CSS布局设计,全套模板,包括网站首页、画室简介、画室资讯、招生咨询、作品欣赏、艺考成绩、艺考资讯、在线报名、联系我们等...
web前端期末节课大作业 ,html+css+javascript实现~ (功能齐全)HTML教育培训机构网站模板,DIV+CSS布局,宽屏设计,自适应分辨率,全套模板,包括学院首页、教师风采、课程介绍、推荐阅读、加入我们等网站模板页面。
web前端期末节课大作业 ,html+css+javascript实现~HTML5大学生网上报到系统响应式模板基于Bootstrap3.3.7制作,响应式设计,自适应分辨率,兼容PC端和移动端,全套模板,包括阅读注意事项填写身份证号、大学毕业生...
html+css+javascript实现~绿色特产商城购物网HTML模板,DIV+CSS布局,全套模板,包括商城首页、特色产品、产品详情、相关资讯、商城简介、注册、登录等HTML商城模板
第三部分高级篇主要介绍图像应用技术,包括图像分割技术、特征分析和复杂视频处理技术。进阶篇与高级篇的每章末节均提供了与本章内容相关的应用实例,意在让读者更好理解知识点,进而有效地进行图像处理开发。, ...
HTML5响应式少儿舞蹈培训学校网站模板,自适应分辨率,兼容PC端和移动端,全套模板,包括首页、关于我们、课程展示、师资团队、教室环境、新闻资讯、教学成果、联系我们等HTML网站模板页面。
第三部分高级篇主要介绍图像应用技术,包括图像分割技术、特征分析和复杂视频处理技术。进阶篇与高级篇的每章末节均提供了与本章内容相关的应用实例,意在让读者更好理解知识点,进而有效地进行图像处理开发。
本人学习CCNP一些笔记,详细记录了OSPF协议在NBMA网络中的配置过程,帧中继网络的配置方法(包括帧中继交换机的配置),OSPF虚拟链路连接area 0的方法,以及OSPF末节区域、次末节区域的配置方法;另外还详细介绍了...
//返回树(根)的高度(重写) public int getHeight() {return isEmpty() ? -1 : getRoot().getHeight(); } /*---------- ComplBinTree接口中各方法的实现 ----------*/ //生成并返回一个存放e的外部节点,该...
ccna学习资料,欢迎大家下载。 为了优化ospf,末梢只需要知道骨干路由就好,末梢路由怎么不接收其他末梢路由通告: 1 可以汇总过滤 2 可以区域设置成summary 不接收五类lsa 3 可以stubby area 末节区域(私有区域 纯...