3

我需要实现一个 B+ 树。

我需要创建以下方法:

  1. 插入(x) - 0(log_t(x))。
  2. 搜索 - 成功搜索 - O(log_t(x))。搜索不成功 - O(1) {具有很高的可能性}

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

我怎样才能在不影响运行时间的情况下找到这个中位数?

我想过:

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

我能做些什么?

关于搜索,Idea-wise:成功和不成功搜索之间的区别在于在叶子中搜索,但我仍然需要“运行”树的不同键以确定键是否在树中。那么它怎么可能是 O(1) 呢?

4

3 回答 3

4

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

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

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

鉴于这些知识 - 人们可以缓存指向中间元素的指针,并确保在删除/插入时对其进行维护。当您要求中位数时 - 只需从缓存中获取中位数 - O(1)


关于Unsuccessful search - O(1) {With a high likely-hood}- 这个尖叫布隆过滤器,这是一种概率集合实现,从不存在假阴性(从不说某些东西不在集合中),但有一些误报(说某些东西在缓存中,而实际上它不在't)。

于 2013-05-11T16:40:45.470 回答
2

您不需要 B+-树的中位数。您需要要拆分的节点中的中值键。您必须在该中位数处拆分以满足每个节点具有N/2 <= n <= N 个键的条件。节点中的中间键只是中间的一个,在n/2处,其中n是节点中实际键的数量。那就是您拆分节点的地方。O(1) 的计算:它不会损害运行时。

如果不叠加另一个数据结构,就无法从 B+-tree 获得 O(1) 搜索失败时间。

于 2013-05-12T00:45:51.247 回答
1

我已经发布了一个答案(并且已经删除了它),但我可能误解了,所以这里有另一种解释的答案......

如果您需要始终知道哪个项目是完整B+ 树容器中的中位数,该怎么办。

正如阿米特所说,您可以保留一个指向包含中位数的当前叶节点的指针(连同您的根指针)。您还可以在该叶节点中保留索引。因此,您可以通过直接跟踪正确的节点和项目来获得 O(1) 访问权限。

问题在于保持这一点。当然阿米特是正确的,对于每个插入,中位数也必须保持相同的项目,或者必须步进到之前或之后的那个。如果你有一个通过叶节点的链表,即使这意味着步进到相邻的叶节点,也可以有效地处理。

不过,我不相信,确定是否或采取哪种方式是微不足道的,除非在中值和插入恰好位于同一个叶节点中的特殊情况下。

如果您知道完整树的大小(您可以使用根指针轻松存储和维护),您至少可以确定插入前后中间项应该位于哪个索引。

但是,您需要知道前一个中值项的索引是否通过插入向上移动 - 插入点是在中值之前还是之后。除非插入点和中位数恰好在同一个节点中,否则这是一个问题。

矫枉过正的方式 - 扩充 B+ 树以支持计算项目的索引和搜索索引。这样做的诀窍是每个节点都保留其子树的叶节点中的项目总数。这可以推高一个级别,因此每个分支节点都有一个子树大小数组及其子节点指针数组。

这提供了两种解决方案。您可以在搜索时使用该信息来确定插入点的索引,或者(如果节点具有父指针)您可以使用它来重新确定插入后前一个中间项的索引。

【其实是三个。插入后,可以根据新的大小直接搜索新的中途索引,无需参考之前的中间链接。]

然而,就为增强而存储的数据而言,这被证明是矫枉过正的。您不需要知道插入点的索引或先前的中位数 - 您可以知道插入发生在中位数的哪一侧。如果您知道从根到中间项的路径,您应该能够在搜索插入点时跟踪您所在的那一侧。因此,您只需要增加足够的信息即可找到并维护该线索。

于 2013-05-11T23:43:43.993 回答