我试图弄清楚当节点溢出时到底会发生什么。信息：在我的 b+ 树中，每个块有 4 个指针和 3 个数据部分。问题：我知道当发生溢出时，在我的情况下，我们分成 2 个节点，每个节点有 2 个键，并将父节点插入中间值，而不从子节点中删除（与 b 树不同）。
但是我遇到了这样的情况：
|21|30|50|
|10|20|-| |21|22|25| |30|40|-| |50|60|80|
我想先插入密钥 23 我拆分 |21|22|25| 进入：|21|22|-| 和 |23|25|-| 现在我需要将密钥 23 插入到父 |21|30|50| 女巫导致另一个分裂。|21|23|-| 和 |30|50|-| 但是 30 之前的指针指向哪里？这个指针和 23 之后的指针是否都指向 |23|25|-| ?
插入 23 时：
基本上，该插入将使树的深度增加 1
以下是应该如何处理指针。这是插入之前的 B+ 树。（一些填充用于使指针更容易看到）
[21 30 50]
/ \ \ \
[10|20|-] => [21|22|25] => [30|40|-] => [50|60|80]
插入 23 后，您将拥有 2 个节点。重要的是要知道左拆分应该始终是同一个实例，而右拆分应该是一个新节点。这将使处理指针更容易一些。
所以分裂应该是这样的。
old fresh
[21|22|-] => [23|25|-]
由于左节点是同一个实例，21根处的键具有正确的右指针。这是分裂根之前和分裂叶之后节点的样子。我们正处于过程的中间。
[21 30 50]
/ \ \ \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
23只应21在根目录旁边添加一个带有密钥的新项目。由于 root 没有空间，它也会分裂。中间键是 23（右拆分的第一项）。
[21 30] [ 50 ]
/ \ \ * \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
因为 root 是分裂的，所以我们必须将我们的中间键添加到左或右分裂，并找到一个新的中间键来提升。注意右拆分处的空指针。因为那个节点是新鲜的，它必须尽快初始化！
（根从正确的方向拆分，这意味着如果有奇数数量的项目，则较少的项目位于右节点中。但一般来说，你拆分的方式并不重要。）
我们的中间键是 23。所以让我们添加 23。
[21 23 30] [ 50 ]
/ \ \ \ * \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
好的！如果这里没有拆分，我们的插入到此就完成了。但既然在这个层面有分裂，就必须找到新的中键来推动。也不要忘记新节点的空指针。
（在分裂叶子的情况下，您必须将键值保留在叶子上并提升中间键的副本，但在分裂内部节点的情况下，您可以安全地向上移动和提升键。）
这里新的中间键是 30。让我们从左节点弹出它。
30
\
[30|40|-]
（如何选择中间键很重要。总是从底部拆分获取中间键的节点，应该为新的中间键删除一个项目。如果该节点是左节点，则从中删除最后一项，否则删除第一项。）
[21 23] 30 [ 50 ]
/ \ \ \ * \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
请注意，30 不在任何拆分内。这是我们必须处理的中间键。始终将中间键的右节点放在新节点的左侧。
[21 23] 30 [50]
/ \ \ * / \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
然后中间键的右指针将指向右拆分的新节点。最后中间键被提升，新的根在左边分裂和右边分裂和中间键的键被创建。
[ 30 ]
/ \
[21 23] [50]
/ \ \ / \
[10|20|-] => [21|22|-] => [23|25|-] => [30|40|-] => [50|60|80]
恭喜！你已经完成了插入。它在纸上看起来很容易，但我不得不承认它在编码时有点挑战。
有几种方法可以key-node在内存中表示这些项目。我的方法是每个key-node项目都有一个带键的右指针。所以每个内部节点都有key-nodes数组。这样，键和节点指针总是保持在一起。最左边的孩子由一个单独的左指针处理，这个指针保存在每个内部节点上并且永远不会为空（在完成操作之后）。
在B+树中，叶子节点和非叶子节点有不同的结构。因此，它们的溢出机制也不同。你所说的对于叶子节点的溢出是正确的（它是在没有从儿子那里删除父密钥的情况下完成的）。但是当非叶子节点溢出并被分裂时，子节点不保留父键（父键从子节点中删除）。
您必须了解会发生什么的问题是由于您使用的表示模型不好。您应该有一个与指针相关联的数据值，并且该数据值是指针所引用的子树中的最小值这一不变量。
所以这就是你应该如何表示插入之前的 b 树节点。
10|21|30|50| <--- root node
10|20| 21|22|25| 30|40| 50|60|80| <--- leaf nodes
在此表示中，根节点中值 10 之后的指针指向第一个值为 10 的叶节点，依此类推。
当您插入 23 时，它会插入到第一个值为 21 的叶节点中。这会产生以下树，无需拆分。
10|21|30|50| <--- root node
10|20| 21|22|23|25| 30|40| 50|60|80| <--- leaf nodes
当插入产生你描述的效果的 24 时，你得到的是以下
10|30| <--- new root node
10|21|24| 30|50| <--- intermediate nodes
10|20| 21|22|23| 24|25| 30|40| 50|60|80| <--- leaf nodes
如您所见，不再有歧义。叶节点被分裂，关键指针对 24| 必须插入根节点。既然已经满了，就不得不拆了。现在有 5 个值，您将得到一个具有 3 个值的节点和一个具有 2 个值的节点。您可以自由选择是左节点还是右节点获取三个值。重要的是保留了基本不变量。节点中的每个键值都是其关联指针所引用的子树中的最小元素。必须添加一个新的根节点，并且它的键值指针集现在应该很明显了。没有歧义。
这也表明许多优化策略是可能的。我们可以将值 21 移动到未满的左叶节点中，而不是拆分根节点。第一个值为 10 的那个。这避免了拆分根节点的需要并保持 b-tree 高度不变，并产生更好的 b-tree 填充。因此，您可以最大限度地减少空间和搜索时间。但这意味着可以有效地检查横向平衡是否可行。仍然需要更改根节点中的键值。等等
如您所见，b-tree 中的值 10 在非叶节点中并不是真正需要的，并且在 b-tree 表示（即wikipedia）中经常省略它，但这可能会让人感到困惑，并且可能是您在哪里的原因。:)
根据我所学到的，最后一个节点的一个节点小于 n/2 是可以的。因此，在您的示例中，顶部节点将变为：
|23|
/ \
|21|22|-| |25|-|-|
我觉得有点道理。如果你考虑一下，你有 5 个离开节点，所以你需要来自上层的 5 个指针。这种安排是您可以拥有 5 个指针的唯一方法，所有其他组合都会溢出节点或创建额外的指针。
如果节点是 |21|22|-| 和 |23|25|-|，则根节点将是 |23|-|-|。然后，在正确的节点中有 23 是没有意义的，因为无论如何，正确的节点中的任何内容都必须等于或大于 23！