我需要实现一个 B+ 树。
我需要创建以下方法：
所以我开始实现 Insert(x) - 每次我有一个完整的叶子时，我都想把它分成两个分开的叶子。一个叶子的键等于或低于中值键，第二个叶子将包含值高于中值的键。
我怎样才能在不影响运行时间的情况下找到这个中位数？
我想过：
我能做些什么？
关于搜索，Idea-wise：成功和不成功搜索之间的区别在于在叶子中搜索，但我仍然需要“运行”树的不同键以确定键是否在树中。那么它怎么可能是 O(1) 呢？
在 B+ 树中，所有值都存储在叶子中。
请注意，您可以将每个叶子的指针添加到下一个叶子，并且除了标准 B+ 树之外，您还可以获得一个包含所有元素的有序链表。
现在，请注意，假设您知道此链表中的当前中位数是什么 -在插入/删除时，您可以廉价地计算新的中位数（它可以是同一个节点、下一个节点或前一个节点，没有其他选择）。
请注意，修改此指针是O(1)（尽管插入/删除本身是O(logn).
鉴于这些知识 - 人们可以缓存指向中间元素的指针，并确保在删除/插入时对其进行维护。当您要求中位数时 - 只需从缓存中获取中位数 - O(1)。
关于Unsuccessful search - O(1) {With a high likely-hood}- 这个尖叫布隆过滤器，这是一种概率集合实现，从不存在假阴性（从不说某些东西不在集合中），但有一些误报（说某些东西在缓存中，而实际上它不在't）。
您不需要 B+-树的中位数。您需要要拆分的节点中的中值键。您必须在该中位数处拆分以满足每个节点具有N/2 <= n <= N 个键的条件。节点中的中间键只是中间的一个，在n/2处，其中n是节点中实际键的数量。那就是您拆分节点的地方。O(1) 的计算：它不会损害运行时。
如果不叠加另一个数据结构，就无法从 B+-tree 获得 O(1) 搜索失败时间。
我已经发布了一个答案（并且已经删除了它），但我可能误解了，所以这里有另一种解释的答案......
如果您需要始终知道哪个项目是完整B+ 树容器中的中位数，该怎么办。
正如阿米特所说，您可以保留一个指向包含中位数的当前叶节点的指针（连同您的根指针）。您还可以在该叶节点中保留索引。因此，您可以通过直接跟踪正确的节点和项目来获得 O(1) 访问权限。
问题在于保持这一点。当然阿米特是正确的，对于每个插入，中位数也必须保持相同的项目，或者必须步进到之前或之后的那个。如果你有一个通过叶节点的链表，即使这意味着步进到相邻的叶节点，也可以有效地处理。
不过，我不相信，确定是否或采取哪种方式是微不足道的，除非在中值和插入恰好位于同一个叶节点中的特殊情况下。
如果您知道完整树的大小（您可以使用根指针轻松存储和维护），您至少可以确定插入前后中间项应该位于哪个索引。
但是，您需要知道前一个中值项的索引是否通过插入向上移动 - 插入点是在中值之前还是之后。除非插入点和中位数恰好在同一个节点中，否则这是一个问题。
矫枉过正的方式 - 扩充 B+ 树以支持计算项目的索引和搜索索引。这样做的诀窍是每个节点都保留其子树的叶节点中的项目总数。这可以推高一个级别，因此每个分支节点都有一个子树大小数组及其子节点指针数组。
这提供了两种解决方案。您可以在搜索时使用该信息来确定插入点的索引，或者（如果节点具有父指针）您可以使用它来重新确定插入后前一个中间项的索引。
【其实是三个。插入后，可以根据新的大小直接搜索新的中途索引，无需参考之前的中间链接。]
然而，就为增强而存储的数据而言，这被证明是矫枉过正的。您不需要知道插入点的索引或先前的中位数 - 您可以知道插入发生在中位数的哪一侧。如果您知道从根到中间项的路径，您应该能够在搜索插入点时跟踪您所在的那一侧。因此，您只需要增加足够的信息即可找到并维护该线索。