首页 > 试题广场 >

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

[单选题]
下面关于B-和B+树的叙述中,不正确的是
  • B-树和B+树都是平衡的多叉树
  • B-树和B+树都可用于文件的索引结构
  • B-树和B+树都能有效地支持顺序检索
  • B-树和B+树都能有效地支持随机检索
B树的定义是这样的,一棵m阶的B树满足下列条件:(1)每个结点至多有m棵子树;(2)除根结点外,其他每个非叶子结点至少有m/2棵子树;(3)若根结点不是叶子结点,则至少有两棵子树;(4)所有叶结点在同一层上。B树的叶结点可以看成一种外部结点,不包含任何信息;(5)所有的非叶子结点中包含的信息数据为:(n,p0,k1,p1,k2,P2,…,kj-1,Pj-1)其中,ki为关键字,且满足kiki+1;pi为指向子树根结点的指针,并且Pi-1所指的子树中的所有结点的关键字均小于ki,Pj-1所指的子树中的所有结点的关键字均大于kj-1。B+树是应文件系统所需而出现的一种B树的变型树,其主要区别是一棵非叶子结点有n个子树就有n个关键字,这些关键字的作用是索引;所有的叶子结点包含了全部关键字的信息,以及指向这些关键字记录的指针,且叶子结点本身的关键字的大小自小而大顺序链接。从上述的特点中我们知道,这两种树都是平衡的多分树,它们都可以用于文件的索引结构,但B树只能支持随机检索,而B+树是有序的树,既能支持随机检索,又能支持顺序检索。选C.
发表于 2015-03-26 17:48:35 回复(0)
选c。b树的叶子不在同一层无法顺序检索。
发表于 2015-10-12 06:18:08 回复(1)
c,b树只支持随机检索。
发表于 2019-01-28 22:20:15 回复(0)
b树的叶子结点之间没有指针,不方便进行顺序检索。
发表于 2018-07-20 10:09:30 回复(0)
B-树支持从根节点开始随机检索,不支持顺序检索,B+树有两个头指针,一个指向根节点,支持随机检索;一个指向关键字最小的叶子节点,支持顺序查找;且B-树叶子节点不带信息,B+树叶子节点本身依关键字从小到大顺序链接!
发表于 2017-12-18 17:15:20 回复(0)
C:
    B-树只支持随机检索不支持顺序检索。
发表于 2015-03-29 20:18:14 回复(0)

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

     image ‍ 

       B- 树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点;

B- 树的特性:

       1. 关键字集合分布在整颗树中;

       2. 任何一个关键字出现且只出现在一个结点中;

       3. 搜索有可能在非叶子结点结束;

       4. 其搜索性能等价于在关键字全集内做一次二分查找;

       5. 自动层次控制;

        由于限制了除根结点以外的非叶子结点,至少含有 M/2 个儿子,确保了结点的至少利用率,其最底搜索性能为:

             image

        其中, 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

     image ‍ 

    B+ 的搜索与 B- 树也基本相同,区别是 B+ 树只有达到叶子结点才命中( B- 树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;

       B+ 的特性:

       1. 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;

       2. 不可能在非叶子结点命中;

       3. 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;

       4. 更适合文件索引系统;

   

B*

        B+ 树的变体,在 B+ 树的非根和非叶子结点再增加指向兄弟的指针;

     image ‍ 

    B* 树定义了非叶子结点关键字个数至少为 (2/3)*M ,即块的最低使用率为 2/3 (代替 B+ 树的 1/2 );

       B+ 树的分裂:当一个结点满时,分配一个新的结点,并将原结点中 1/2 的数据复制到新结点,最后在父结点中增加新结点的指针; B+ 树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;

       B* 树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制 1/3 的数据到新结点,最后在父结点增加新结点的指针;

        所以, B* 树分配新结点的概率比 B+ 树要低,空间使用率更高;

发表于 2015-08-04 23:34:36 回复(5)
顺序检索和随机检索
发表于 2024-06-05 11:47:31 回复(0)
发表于 2022-03-21 16:04:51 回复(0)
B-树不支持顺序检索。
发表于 2018-07-03 18:48:19 回复(0)
B-不支持顺序检索
发表于 2017-10-29 17:19:18 回复(0)
不是说B+不是树吗
发表于 2017-04-19 21:27:17 回复(0)
为什么一定是平衡的树?
比如目录结构
c - empty_folder
   - folder1 - folder2 - folder3
这也算平衡? 选A
发表于 2017-02-08 01:58:05 回复(0)
没有B—树这个东西,是B树
发表于 2016-09-10 21:52:48 回复(3)
是不是可以这样认为:因为B-树的所有关键字都存储在非叶子节点上,并没有放在叶子结点,因为无法进行顺序查找
发表于 2016-08-01 10:57:00 回复(1)
选C,B-树只适用于随机检索,不适用于顺序检索
编辑于 2015-03-24 23:53:26 回复(0)
答案选D,给定一个关键字,只能通过不断的比较才能检索到目标,不是随机检索。
发表于 2015-03-05 09:39:44 回复(1)