理论教育 树概念完全解析-2019版数据结构高分笔记

树概念完全解析-2019版数据结构高分笔记

时间:2023-11-03 理论教育 版权反馈
【摘要】: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个分支。

树概念完全解析-2019版数据结构高分笔记

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的取值范围为978-7-111-58746-0-Chapter09-105.jpgm/2978-7-111-58746-0-Chapter09-106.jpg≤n≤m,根结点的取值范围为2≤n≤m;而在B-树中,它们的取值范围分别是978-7-111-58746-0-Chapter09-107.jpgm/2978-7-111-58746-0-Chapter09-108.jpg-1≤n≤m-1和1≤n≤m-1。

3)在B+树中叶子结点包含信息,并且包含了全部关键字,叶子结点引出的指针指向记录(在本节中,关键字和记录要区分开来理解,之前为了方便写程序,可以认为关键字就是记录)。(www.daowen.com)

978-7-111-58746-0-Chapter09-109.jpg

图9-26 同一组关键字所建立的4阶B-树和4阶B+树

a)B-树 b)B+树

4)B+树中的所有非叶子结点仅起到一个索引的作用,即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址;而在B-树中,每个关键字对应一个记录的存储地址。

5)在B+树上有一个指针指向关键字最小的叶子结点,所有叶子结点链接成一个线性链表,而B-树没有。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈