单选题 25.下列关于m阶B+树的说法中,正确的是( )。
Ⅰ.具有n个关键字的结点至少含有n+1棵子树 Ⅱ.所有叶子结点包含全部关键字 Ⅲ.B+树支持随机索引 IV.B+树可用于文件的索引结构
【正确答案】 B
【答案解析】一棵m阶B+树满足下列条件。
①每个分支结点至多有m棵子树。
②根结点或者没有子树,或者至少有两棵子树。
③除根结点外,其他每个分支结点至少有[m/2]棵子树。
④具有n个关键字的结点含有n棵子树。
⑤所有叶子结点包含伞部关键字及指向相应记录的指针,而且叶子结点按关键字的大小顺序链接。
⑥所有分支结点中仅包含它的各个子结点中最大关键字及指向子结点的指针。
⑦B+树中,所有非终端结点可以看成是索引部分,故可用于文件的索引结构。
注意:由于B+树为链式存储结构,因此不支持随机检索。 综上所述,可知Ⅱ、IV正确,Ⅰ、Ⅲ错误,故B选项正确。
补充知识点:很多考生被B+树和B-树的基本概念弄混,下面做一个小结。 提示:m阶B+树和m阶B-树的主要差异如下。
①在B+树中,具有n个关键字的结点含有n棵子树;而在B-树中,具有n个关键字的结点至少含有(n+1)棵子树。
②在B+树中,每个结点(除根结点外)中的关键字个数n的取值范围是[m/2]≤n≤m,根结点n的取值范围是2≤n≤m;而在B一树中,除根结点外,其他所有非叶子结点的关键字个数n的取值范围是[m/2]—1≤n≤m一1,根结点n的取值范围是1≤n≤m—1。 记忆方式:“B一”中有个“一”号,自然关键字个数相对于B+减掉了1。
③在B+树中,所有叶子结点包含了全部关键字,即其他非叶子结点中的关键字包含在叶子结点中:而在B一树中,关键字是不重复的。
④在B+树中,所有非叶子结点仅仅是起到了索引的作用,即结点中的每个索引项只含有对应子树的最大关键字和指向子树的指针,不含有该关键字对应记录的存储地址。而在B一树中,每个关键字对应一个记录的存储地址。
⑤在B+树上有两个头指针,一个指向根结点,另一个指向关键字最小的叶子结点,所有叶子结点链接成一个链表;而在B一树中,叶子结点并不会有指针相连。