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

Question

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

因此，对于 B-Tree，您拥有的键和 children 的最大数量是 2*degree（节点中元素的最小数量）。如果我的最小填充因子为 3，那么一个节点最多可以有 6 个键。这个逻辑给了我这个：

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

效果很好，我的 B-Tree 按预期工作。所以，当我去修改我的 B-Tree 成一个 B* 树时，我认为 children 和 keys 的最大数量必须是 (3 * degree)/2。这给了我这个：

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

问题：
但是，现在当我尝试从此处的临时文件复制键时，split child 方法抛出数组越界异常：

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

问题：
我并不是真的在问为什么代码不起作用，而是我的逻辑有什么问题。如果两棵树之间的唯一区别只是填充因子，那么将一棵树转换成另一棵树所需要做的唯一事情不应该是更改给定节点的最大键数和 children 吗？其他所有内容，包括根已满后如何拆分节点，都应保持不变。您只需要更改拆分发生的最大限制对吗？

提前感谢您的帮助。

相关代码：
我将 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，反之，加入时，必须将密钥分发回前、后节点，因为只有一个节点会有太多密钥。

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

How do you convert a B-Tree to a B* tree? / Minimum Fill Logic

java

algorithm

tree