B+树的基本概念
标签: 数据结构
学习人数: 3080


全屏播放
赞赏支持

B+树的基本概念及性质

B+树是B树的一种变形形式,B+树上的叶子结点存储关键字以及相应记录的地址,叶子结点以上各层作为索引使用。

 

一棵m阶的B+树需满足下列条件:

1、每个分支结点最多有m棵子树。
2、非叶根结点至少有两棵子树,其他每个分支结点至少有⌈m/2⌉棵子树。
3、结点的子树个数与关键字个数相等。
4、所有叶结点包含全部关键字及指向相应记录的指针,而且叶结点中将关键字按大小顺序排列,并且相邻叶结点按大小顺序相互链接起来。
5、所有分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块)中关键字的最大值及指向其子结点的指针。

 

B树与B+树的区别

1、在B树中,具有n个关键字的结点含有(n+1)棵子树;而在B+树中,具有n个关键字的结点只含有n棵子树,即每个关键字对应一棵子树。
2、在B树中,根结点的关键字个数n的范围是1 <= n <= m-1,非根结点的范围是⌈m/2⌉-1<=n <= m-1;...

登录查看完整内容


课后作业

课后习题

 

【2017年真题】下列应用中,适合使用B+树的是()
A.编译器中的词法分析        B.关系数据库系统中的索引
C.网络中的路由表快速查找        D.操作系统的磁盘空闲块管理

参考答案:B

 

【2016年真题】B+树不同于B树的特点之一是()
A.能支持顺序查找
B.结点中含有关键字
C.根结点至少有两个分支
D.所有叶结点都在同一层上

参考答案:A


登录后发布评论

1 条评论
von
2021年1月25日 23:43

233