首页 > 试题广场 >

下面关于 B 树和 B+ 树的叙述中,不正确的结论是

[单选题]
下面关于 B 树和 B+ 树的叙述中,不正确的结论是
  • B树和B+树都能有效的支持顺序查找
  • B树和B+树都能有效的支持随机查找
  • B树和B+树都是平衡的多叉树
  • B树和B+树都可用于文件索引结构
本题选A
这两种树都是平衡的多分树,它们都可以用于文件的索引结构。
B树只能支持随机检索;
B+树是有序的树,既能支持随机检索,又能支持顺序检索。
发表于 2017-10-17 20:12:31 回复(2)
选项A:B树的元素值分布在各个节点中,属于树状分布,且使用链式存储(保证增删性能),所以并不支持顺序查找;而B+树的元素值统一分布在叶子节点中,并添加指针域来将相邻的叶子链接起来(链表),中间节点仅仅起到索引叶子元素的作用,不储存元素值,所以B+树支持顺序查找(叶子链表)。
选项B:首先要对 “随机查找” 有个概念,网上没找到,所以不知道;
选项C:B树和B+树的叶子节点都处于同一层(详见后文说明),且孩子节点数量维持在50%以上,所以说他们是(大致)平衡的,当然这和平衡的定义有所出入(子树高度差不超过1),但是我们仍然说他平衡(这和我们说 “红黑树” 是平衡的差不多)
选项D:确实是这样的,呵呵呵呵呵~

关于B树:
粗暴点说,B树可以当成是二叉搜索树的泛化,当然这样说其实不太对,B树的介绍如下:
1. N阶B树就是一棵N叉树,每个节点都对应着一个数值区间,兄弟节点的区间是相邻的,孩子节点是对父节点区间的分割;
2. 节点的关键字就是本区间上的一个分割点,是直接使用插入的元素值来作为分割点的,N叉搜索树的一个节点最多有N-1个关键字;
3. B树节点的空间利用率保持在50%~100%,这是通过节点的分裂和合并来实现的,插入时空间满了就分裂,删除时少于50%就合并(根节点除外,因为当有元素插入时,如果所有节点都满了,当前的根节点就会诞生出2个新的孩子节点,并把节点内容转移到这两个孩子中去,此时树高+1);
4. 此外,B树的所有叶子都保持在同一层(这需要去把整个插入删除、分裂合并的过程认真过一遍才能明白);
B树保证了动态性能查找性能(树是整体平衡的

关于B+树:
B+树在B树基础上进行了扩展和改变,具体不同如下:
1. B+树的元素值统一存储在叶子上,树的中间节点仅作索引之用;
2. 叶子节点添加指针域,链接相邻叶子,使之构成顺序结构
B+这样做优化了 “排序需求” 和 “范围查找和输出(只要找到两个端点,然后在叶子链表上从前往后依次输出就OK了)

关于B*树:
B*树在B+树基础上进行了扩展和改变,具体不同如下:
1. 在中间节点上也额外添加指针域,指向兄弟节点;
增加元素时,如果当前节点已满,如果兄弟节点有空间就挤出部分数据到兄弟节点中去,以腾出空间供插入;如果兄弟节点也满,则分裂:创建新节点,分担当前节点的1/3数据和兄弟节点的1/3数据,这样,当前节点、兄弟节点和新节点就都有2/3的空间利用率)
很明显,B*树是进一步优化了空间利用率(从50%至66.7%)
编辑于 2019-11-17 20:14:50 回复(1)
B树只能支持随机检索,B+树是有序的树,既能支持随机检索,又能支持顺序检索。
发表于 2021-12-06 17:47:20 回复(0)
B 树和 B+ 树相同点:
1、B 树和 B+ 树都至少有两个分支
2、所有叶节点都位于同一层
3、个结点内的关键字均一升序或降序排序

B 树和 B+ 树不同点
1、B 树 : 叶子结点不带信息
      B+ 树 : 叶子结点包含所有关键字,仅起索引作用
2、B 树 : 随机查找
      B+ 树 : 支持顺序查找(叶节点)和随机查找 

发表于 2021-10-24 16:48:34 回复(0)
B树只适合随机检索,B+树是有序的树同时支持随机检索和顺序检索
发表于 2019-03-22 23:04:23 回复(0)
我这边显示A.B树和B+树都能有效的支持顺序存储,B.B树和B+树都能有效的支持随机存储,要求选择不正确的,然后系统给出的答案是A
发表于 2018-04-09 16:45:02 回复(1)