如何将B树转换为B *树？ /最小填充逻辑

Question

我读过B树和B *树之间的唯一区别是填充因子。 B树的最小填充因子是1/2，B *树的最小填充因子是2/3。

因此，对于B树，您拥有的最大键和子元素数是2 *度（节点中元素的最小数量）。如果我有3最小填充因子，节点可以拥有的最关键是6.逻辑给了我这样的：

keyHolder = new int[2 * degree - 1]; 
children = new BTreeNode[2 * degree]; 

这工作就好了，我的B树担任预期。所以，当我去修改我的B-Tree到一个B *树时，我认为最大数量的子和键必须是（3 *度）/ 2。这给了我这样的：

keyHolder = new int[((3 * degree)/2) - 1]; 
children = new BStarTreeNode[(3 * degree)/2]; 

问题：
不过，现在拆分子方法抛出一个数组越界异常，当我尝试从临时位置复制键：

temp.keyHolder[j] = node.keyHolder[j + degree]; 

问题：
我并不真正问为什么代码不起作用，而是我的逻辑有什么问题。如果两棵树之间的唯一区别仅仅是填充因子，那么您是否应该将一个转换为另一个树所需要做的唯一一件事是否改变给定节点的最大键和子元素数？其他一切，包括如何在根已满时将节点分开的方式应该保持不变。你只需要改变分割发生的最大限制吧？

感谢您提前提供任何帮助。

相关代码：
我把splitChild方法在以下情况下，它可以帮助：

public void splitChild(int i, BStarTreeNode node) { 
    BStarTreeNode temp = new BStarTreeNode(node.degree - 1, node.leaf); 
    temp.numKeys = degree - 1; 

    // Copy the degree-1 keys into temo from node 
    for (int j = 0; j < degree - 1; j++) { 
     temp.keyHolder[j] = node.keyHolder[j + degree]; 

    } 

    // If this node is not a leaf, copy the degree children 
    if (node.leaf == false) { 
     for (int j = 0; j < degree; j++) { 
      temp.children[j] = node.children[j + degree]; 
     } 
    } 

    // Reduce the number of keys in node 
    node.numKeys = degree - 1; 

// Since this node is going to have a new child, 
    // create space of new child 
    for (int j = numKeys; j >= i + 1; j--) { 
     children[j + 1] = children[j]; 
    } 
    // Link the new child to this node 
    children[i + 1] = temp; 

     //Find location of 
    // new key and move all greater keys one space ahead 
    for (int j = numKeys - 1; j >= i; j--) { 
     keyHolder[j + 1] = keyHolder[j]; 
    } 

    // Copy the middle key of node 
    keyHolder[i] = node.keyHolder[degree - 1]; 


// Increment count of keys in this node 
    numKeys = numKeys + 1; 
} 

我写的代码是从here。我只是用Java重写它。

Answer 1

每个节点的密钥最大数量不会改变。它仍然是2N。什么样的变化是你必须拆分和加入的条件。

当您拆分完整节点时，您必须从前一个节点和后继节点获取密钥，以便两个新节点满足n >= 2*N/3，反之，加入时必须将密钥分发回先前节点和后继节点，就像您将要只有一个节点的密钥太多。