【摘要】:B+树是B-树的一种变形,它和B-树有很多相似之处,可以对比着来记忆B+树的特点。先举一个例子,用同一组关键字分别建立一棵B-树和一棵B+树,观察一下它们的不同。图9-26所示为同一组关键字所建立的B-树和B+树。通过图9-26可以看,出m阶的B-树定义中的1)、2)、3)、5)四条同样适用于m阶的B+树,这里主要讨论它们的差别。1)在B+树中,具有n个关键字的结点含有n个分支;而在B-树中,具有n个关键字的结点含有n+1个分支。
B+树是B-树的一种变形,它和B-树有很多相似之处,可以对比着来记忆B+树的特点。
先举一个例子,用同一组关键字分别建立一棵B-树和一棵B+树,观察一下它们的不同。图9-26所示为同一组关键字所建立的B-树和B+树。
通过图9-26可以看,出m阶的B-树定义中的1)、2)、3)、5)四条同样适用于m阶的B+树,这里主要讨论它们的差别。
1)在B+树中,具有n个关键字的结点含有n个分支;而在B-树中,具有n个关键字的结点含有n+1个分支。
2)在B+树中,每个结点(除根结点以外)中的关键字个数n的取值范围为m/2≤n≤m,根结点的取值范围为2≤n≤m;而在B-树中,它们的取值范围分别是m/2-1≤n≤m-1和1≤n≤m-1。
3)在B+树中叶子结点包含信息,并且包含了全部关键字,叶子结点引出的指针指向记录(在本节中,关键字和记录要区分开来理解,之前为了方便写程序,可以认为关键字就是记录)。(www.daowen.com)
图9-26 同一组关键字所建立的4阶B-树和4阶B+树
a)B-树 b)B+树
4)B+树中的所有非叶子结点仅起到一个索引的作用,即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址;而在B-树中,每个关键字对应一个记录的存储地址。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。
有关2019版数据结构高分笔记的文章