下面关于B树运算的叙述中,正确的是A.若插入过程中根结点发生分裂,则B树的高度加1B.每当进行插入

Question

下面关于B树运算的叙述中，正确的是

A．若插入过程中根结点发生分裂，则B树的高度加1

B．每当进行插入运算，就往B树的最下面一层增加一个新结点

C．若要删除的关键码出现在根结点中，则不能真正删除，只能做标记

D．删除可能引起B树结点个数减少，但不会造成B树高度减小

Answer 1

正确答案：A
解析：在B树里插入一个关键码的方法是很简单的。对于叶结点处于第i层的B树，插入的关键码总是进入第i-l层的结点。插入可能导致B树朝着根的方向生长。如果要插入的那个结点包含的关键码是满的，不能再往里插了，在这种情况下，要把这个结点分裂为两个，并把中间的一个关键码拿出来插到结点的双亲结点里去。双亲结点也可能是满的，就需要再分裂，再往上插。最坏的情况，这个过程可能一直传到根，如果需要分裂根，由于根是没有双亲的，这时就建立一个新的根结点。整个B树增加了一层。删除的过程与之类似，但要稍微复杂。如果删除的关键码不在第i-1层，则先把此关键码与它在B树里的后继对换位置，然后再删除该关键码。如果删除的关键码在第i-1层，则把它从它所在的结点里去掉，这可能导致此结点所包含的关键码的个数小于[m／2]-1。这种情况下，考查该结点的左或右兄弟，从兄弟结点移若干个关键码到该结点中来，使两个结点所含关键码个数基本相同。只有在兄弟结点的关键码个数也很少，刚好等于[m／2]-1时，这个移动才不能进行。这种情况下，要把删除了关键码的结点、它的兄弟结点及它们的双亲结点中的一个关键码合并为一个结点。从双亲结点中包含一个关键码有时也可能导致进一步的合并，甚至这种合并一直传到根结点。在根结点只包含一个关键码的情况下，将发生直到根结点的合并，使结点和它的两个子女进行合并，形成新的根结点，从而使整个树减少一层。