c++ - B+ 树，其中键是其子节点的总和

Question

我一直在尝试使B+ Tree每个键都是相应子键的总和。然后叶子将包含一个字符串，其键将是字符串长度。我基本上是在尝试制作B+ Tree 绳索。

这就是我的意思（这棵树的顺序为 4）：

我可以看到的 1 个直接问题是键没有排序，我认为这是对B+ trees. （5、7、10 是，但这只是巧合）。但是，我不确定如何制作它以便对键进行排序，同时保持它的Rope类似性质（未排序）。

或者我什至需要对每个节点键进行排序？树的结构是否像这样有效，插入和搜索的最坏情况时间复杂度是否仍然是常规的B+ Tree？

我的另一个问题是关于插入。如果我在索引 11 处插入一个新的文本块“abc”，就在“n”之后（假设我没有realloc“n”缓冲区），那么我要做的就是：

0. 检测溢出
1. 将 3 和 2 带入另一个节点。（第一个节点中的 m / 2 个节点）
2. 将 1（即“n”）向上移动到根中。
3. 第二个节点将仅包含 3 (abc) 和 1 (g)（第二个节点中的 m / 2 个节点）

我感到困惑的部分是＃2。由于我无法将实际数据移动到非叶节点中，我该怎么办？

另外，我注意到我使用的树最多有 4 个键，最多也有 4 个孩子。但是，在常规B+ Tree中，您最多只能有 3 个键。这会影响什么吗？

任何帮助将不胜感激。

Answer 1

只要您可以对节点应用顺序（在这种情况下，顺序只是容器内的文本位置），就不需要对树进行排序。

您移动的是节点长度，这是您用作密钥的唯一数据。假设您有以下内容（一级树（代表节点长度的值）：

4, 9, 2, 7

并且您想在 2 之前插入一个长度为 8 的节点，您最终可能会得到一棵树：

  21, 9
4, 9, 8 2, 7

或者

  13, 17
4, 9  8, 2, 7

我会注意到，在实现绳索时我使用了红黑树而不是 B+ 树，因为它在提供足够好的平衡的同时更容易实现。