如何將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，反之，加入時必須將密鑰分發回先前節點和後繼節點，就像您將要只有一個節點的密鑰太多。