java - 在 B+ 树中寻找中位数

Question

我需要实现一个 B+ 树。

我需要创建以下方法:

1. 插入(x) - 0(log_t(x))。
2. 搜索 - 成功搜索 - O(log_t(x))。搜索不成功 - O(1) {With a high likely-hood}

所以我开始实现 Insert(x) - 每次我有一个完整的叶子时，我想将它分成两个单独的叶子。一片叶子的键等于或低于中值键，第二片叶子将包含值高于中值的键。

如何在不影响运行时间的情况下找到这个中位数？

我想过:

1. 将每个内部节点和叶子表示为较小的 B+ 树，但只有当树完全平衡时，中位数才是根(或根中的元素之一)。
2. 将每个内部节点和叶子表示为双向链表。并在插入输入时尝试获取中值键，但有些输入无法使用它。
3. 表示为数组可能会给我中间部分，但是当我将它拆分时，我至少需要 O(n/2) 才能将键插入到新数组中。

我能做什么？

关于搜索，从理念上讲:成功搜索和不成功搜索的区别在于在树叶中搜索，但我仍然需要“运行”树的不同键以确定键是否在树中树。那怎么可能是O(1)呢？

Answer 1

在 B+ 树中，所有的值都存储在叶子中。

请注意，您可以从每个叶子添加一个指向下一个叶子的指针，除了标准 B+ 树之外，您还可以得到一个包含所有元素的有序链表。

现在，请注意，假设您知道此链表中的当前中位数是多少 - 在插入/删除时您可以廉价地计算出新的中位数(它可以是相同的节点、下一个节点或前一个节点，没有其他选择)。
请注意，修改此指针是O(1)(尽管插入/删除本身是O(logn)。

鉴于此知识 - 可以缓存指向中间元素的指针，并确保在删除/插入时维护它。当您请求中值时 - 只需从缓存中获取中值 - O(1)。

---

关于不成功的搜索 - O(1) {With a high likely-hood} - 这个尖叫 bloom filters ，它是一个概率集实现，从不存在假阴性(从不说某些东西不在集合中，而它在集合中)，但有一些假阳性(说某些东西在缓存中，但实际上它不在) .