右边也是一个B树,但它的搜索性能已经是线性的了;同样的关键字集合有可能导致不同的树结构索引;所以,使用B树还要考虑尽可能让B树保持左图的结构,和避免右图的结构,也就是所谓的“平衡”问题;
实际使用的B树都是在原B树的基础上加上平衡算法,即“平衡二叉树”;如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键;平衡算法是一种在B树中插入和删除结点的策略;
B-树
是一种多路搜索树(并不是二叉的):
1.定义任意非叶子结点最多只有M个儿子;且M>2;
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[i+1];
7.非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
8.所有叶子结点位于同一层;
如:(M=3)
B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点;
B-树的特性:
1.关键字集合分布在整颗树中;
2.任何一个关键字出现且只出现在一个结点中;
3.搜索有可能在非叶子结点结束;
4.其搜索性能等价于在关键字全集内做一次二分查找;
5.自动层次控制;
由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率,其最底搜索性能为:
其中,M为设定的非叶子结点最多子树个数,N为关键字总数;
所以B-树的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题;
由于M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合并;
B+树
B+树是B-树的变体,也是一种多路搜索树:
1.其定义基本与B-树同,除了:
2.非叶子结点的子树指针与关键字个数相同;
3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);
5.为所有叶子结点增加一个链指针;
6.所有关键字都在叶子结点出现;
如:(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+树要低,空间使用率更高;
小结
B树:二叉树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于走右结点;
B-树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点;
所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;
B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;
B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3;
相关推荐
建筑工地扬尘治理与文明施工检查表.docx
基于java的个性化旅游攻略定制系统设计与实现.docx
数学建模培训资料 数学建模实战题目真题答案解析解题过程&论文报告 导弹追击模型的建立与求解 共6页.pdf
基础课程辅助教学-JAVA-基于springBoot程序设计基础课程辅助教学系统设计与实现
适用人群:大学生 自学者 使用场景:大学生毕设 自学者练手项目 学习与交流 其它说明:部分资源来源网络及开源社区、仅供参考与学习、不可商用、若有侵权请联系删除! 内容概要:用springmvc实现的校园选课管理系统
java课程期末考试
C++ Vigenère 密码(解密代码)
工程研究中心申报基本情况一览表.docx
Vigenère 密码(加密代码)
密码学AES算法源代码,密码学实验
基于java的百货中心供应链管理系统设计与实现.docx
环境说明:开发语言:Java 框架:springboot JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7 数据库工具:Navicat 开发软件:eclipse/myeclipse/idea Maven包:Maven 浏览器:谷歌浏览器。 项目均可完美运行
【资源说明】 大数据毕业设计 基于Python+Spark机器学习天气预测系统详细文档+全部资料.zip 【备注】 1、该项目是个人高分项目源码,已获导师指导认可通过,答辩评审分达到95分 2、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 3、本项目适合计算机相关专业(人工智能、通信工程、自动化、电子信息、物联网等)的在校学生、老师或者企业员工下载使用,也可作为毕业设计、课程设计、作业、项目初期立项演示等,当然也适合小白学习进阶。 4、如果基础还行,可以在此代码基础上进行修改,以实现其他功能,也可直接用于毕设、课设、作业等。 欢迎下载,沟通交流,互相学习,共同进步!
购物系统 微信小程序+PHP毕业设计 源码+数据库+论文+启动教程
BIM 人才培养的框架和方法 相关的标准
源项目文件
ActiveMQ消息中间件的测试案例
内容概要:本文全面解析了汽车电动化、智能化背景下,车规芯片SoC的重要性和发展趋势。首先概述了汽车行业发展三大趋势——新能源车市场崛起、智能化引领新潮流、商业模式及价值链重构。随后详细介绍了车规芯片SoC的应用领域,包括主控芯片、功率芯片、CMOS芯片、射频接收器、传感器、存储芯片及汽车面板,并阐述了它们的作用和技术需求。文章接着讨论了电子电气架构的演进路径,从分布式向集中式的演进对汽车芯片供应链带来的影响。最后探讨了汽车SoC的技术特征、应用领域、未来发展方向及其面临的挑战。 适合人群:汽车芯片设计师、汽车制造商、科研机构及相关行业的专业人士。 使用场景及目标:理解和掌握汽车芯片尤其是SoC在智能电动汽车中的应用及未来发展,帮助相关从业者做出更好的技术和商业决策。 其他说明:随着智能电动汽车市场的快速成长,车规芯片SoC作为核心技术将面临前所未有的机遇和挑战。
用于控制 Broadlink RM2/3 (Pro) 遥控器、A1 传感器平台和 SP2/3 智能插头的 Python 模块python-broadlink用于本地控制 Broadlink 设备的 Python 模块和 CLI。支持以下设备通用遥控器RM home、RM mini 3、RM plus、RM pro、RM pro+、RM4 mini、RM4 pro、RM4C mini、RM4S、RM4 TV mate智能插头SP mini、SP mini 3、SP mini+、SP1、SP2、SP2-BR、SP2-CL、SP2-IN、SP2-UK、SP3、SP3-EU、SP3S-EU、SP3S-US、SP4L-AU、SP4L-EU、SP4L-UK、SP4M、SP4M-US、Ankuoo NEO、Ankuoo NEO PRO、Efergy Ego、BG AHC/U-01开关MCB1、SC1、SCB1E、SCB2出口BG 800, BG 900电源板MP1-1K3S2U、MP1-1K4S、MP2环境传感器A1报警套件S1C、S2KIT灯泡LB1、LB26 R1、LB2
这是一份关于五个城市的PM2.5监测数据文件,以CSV格式存储。数据涵盖了广州、北京、沈阳等地的空气质量情况,旨在帮助研究人员和数据分析人员更好地理解城市空气污染状况。 使用人群 适合对环境科学、大气污染研究感兴趣的科研工作者、学生及环保组织成员使用。 数据内容 包含五个主要城市的PM2.5浓度数据 时间跨度较长,覆盖多年数据 CSV格式方便导入各种数据分析软件进行进一步处理和分析