如何在B树中实现非抢占式分裂插入？

Question

我正在致力于为 B 树实现非抢占式分裂插入功能。下面是我的 B 树节点的结构：

#define KEYS_NUMBER     4                   // Max number of keys in a node
#define MIN_KEYS        (KEYS_NUMBER / 2)   // Min number of keys in a node
#define CHILDREN_NUMBER (KEYS_NUMBER + 1)   // Max number of children in a node

typedef struct node {
    bool leaf;
    int n;
    int keys[KEYS_NUMBER];
    struct node *children[CHILDREN_NUMBER];
} Node;

我的 insertNonFull 和 insertKey 函数有以下代码：

void insertNonFull(Node *node, int key) {
    int i = node->n - 1;

    if (node->leaf) {
        while (i >= 0 && (key < node->keys[i])) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->n = node->n + 1;
    } else {
        while (i >= 0 && key < node->keys[i]) {
            i--;
        }
        i++;
        if (node->children[i]->n == KEYS_NUMBER) {
            splitChild(node, i, node->children[i]);
            if (key > node->keys[i]) {
                i++;
            }
        }
        insertNonFull(node->children[i], key);
    }
}

void insertKey(Node **tree, int key) {
    Node *r = *tree;

    if (r->n == KEYS_NUMBER) {
        Node *s = createNode();
        *tree = s;
        s->leaf = false;
        s->n = 0;
        s->children[0] = r;
        splitChild(s, 0, r);
        insertNonFull(s, key);
    } else {
        insertNonFull(r, key);
    }
}

当我添加键15时，插入前后的B树结构如下：

插入第 15 把钥匙之前：

[3, 6, 9, 12]
    [1, 2]
    [4, 5]
    [7, 8]
    [10, 11]
    [13, 14]

插入第15把钥匙后：

[9]
    [3, 6]
        [1, 2]
        [4, 5]
        [7, 8]
    [12]
        [10, 11]
        [13, 14, 15]

我们可以看到根节点过早分裂了。如何优化我的插入函数以防止这种过早分裂并实现以下结果？

[3, 6, 9, 12]
    [1, 2]
    [4, 5]
    [7, 8]
    [10, 11]
    [13, 14, 15]

关于如何调整我的 insertNonFull 和 insertKey 函数来实现此目的有什么建议吗？

Answer 1

插入是在叶子节点完成的。如果此操作导致节点满，则将节点分成两个，并提升中间元素。这会级联到树上。

在我看来，文献对实现细节非常模糊，具体来说，它是如何变得“过度”以及如何进行这种“促销”的。我能想到 4 种方法。

无论需要与否，先发制人地贪婪地分割树上的所有完整节点。由于其简单性，这是一种非常流行的方法。然而，正如您所注意到的，结果是一棵非最优且稍微不平衡的树（尽管对于高 B 来说它变得不那么明显。）
按字面意思执行这些步骤。向每个节点添加一个父指针（双链接）和一个额外的临时满数据以帮助转换。每次拓扑发生变化时更新指针。这比需要的更慢且更昂贵。
使用
```
log n
```
额外空间进行插入。
我们几乎独立地知道每个节点如何在插入的键上分裂，除了从子节点填充的 1
```
hole
```
之外。这意味着我们可以直接跳到最终的拓扑，并按照我们喜欢的任何顺序进行新节点的分配和升级；具体来说，是从树上下来而不是向上。这也是有利的，因为人们仅移动存储器一次。（不过，这种情况很多。）

选择最后一种方法，在从根下降到叶子时，我们需要跟踪未满的最低高度节点。如果路径完全充满钥匙，则需要增加高度。然后你就知道需要多少个额外的节点来完成插入。

例如，将 9 添加到完整的 3 树中需要 4 个额外的节点来增加高度。最低的未满是新根。

回溯到最低的未满节点并重新下降，在现有的满子（子 1）节点、来自最低未满（父）节点的一个条目和新分配的节点之间拆分数据和