algorithm - 有效管理内存中的数据页

Question

我正在寻找一个合适的结构来处理以下问题:

应用程序正在接收(例如从 Web 服务器)具有可变大小数据的页面 Pi，例如页面 P1 可以包含 20 个元素，P2 3、P3 20、P4 20 等...

每个页面包含具有全局唯一递减 Id j 的元素 Tj，例如 P2=[T150, T149, T120]。在此示例中，P1 Tj 元素 ID 将严格低于 120，而 P3 元素 ID 将严格大于 150。

这意味着 Pi 中的 i 并不代表网络接收顺序，而是最终的页面顺序，当我们接收到页面时是未知的，并且在插入新页面时会发生变化。

这些页面可以按任何顺序接收。一组页面 P1..P10 的示例:

先 P3 然后 P2 然后 P1

然后 P6 然后 P5 然后 P4

然后 P10 然后 P9

然后是 P8，然后是 P7(注意 P10 和 P9 将是插入这些页面之前的第 8 页和第 9 页)。

我想找到一个允许我执行以下操作的结构:

在页面序列的中间、结尾或开头的任何位置插入新页面(例如在 P9 和 P6 之间插入 P8 和 P7)，因此根据内部 Tj 元素。但我正在寻找比 O(n) 更好的复杂性。

删除页面也很好。

有趣的部分是查询:我希望能够根据间隔进行查询:例如从第 15 个元素到第 25 个元素。在首先呈现的示例中，我将检索 P1 的最后 5 个元素 + P2 的 3 个 + P3 的两个第一个元素。当然，在这里，我也期待比 O(n) 更好的复杂性...

基本上，我想要实现的是在收到推文时有效地将它们存储在内存页面中( Twitter timeline)。我当然可以使用数组或链接列表，但这意味着 O(n) 插入和查询时间......当然我需要能够根据它们在列表中的“位置”来查询项目以显示它们在 ListView 中。

我想了一些解决方案，但没有一个是合适的:

首先，区间树，但它们允许插入和查询元素的“相同范围”，即插入“j”但查询“j”而不是“i”。不确定我是否可以根据“i”向它附加一种前缀总和。

我想的是使用 Fenwick 树来存储项目页数的累积总和，Pi 中的 i 是树中的“位置”，它表示与值 Tj 关联的键。但是 Fenwwick 树不适合插入新元素...我想知道是否可以用红黑树实现 Fenwick 树，但我不确定...

另一种解决方案可能是摆脱页面并在我猜的一种 B-tree 中直接插入元素。但是如果我想一次插入一个包含许多元素的页面，我有点担心速度。

我希望我的问题得到明确说明。关于可扩展的可能有效解决方案的任何想法？

编辑:我想查询的页面不是内部项目 ID(例如 T140、T150 或其他任何东西)，而是元素(即 Tweet)索引。例如，在我的第一个示例中，T120 将是​​第 21 个项目(因为页面 P1 有 20 个元素)。所以我希望能够查询一个区间 [20-29]，它应该返回元素 [T120, ...]。我不想直接搜索120。

Answer 1

您可以使用线程平衡二叉搜索树。然而在搜索中，而不是检查一个数字 x针对节点 n 中的单个数字，您将检查一个页面 px针对页面 pn .由于您的页面不重叠，这很简单。在 px 中获取 id您选择的 (x) 并根据 pn 的最小值和最大值检查它(pn_min，pn_max)。然后:

if pn_min <= x <= pn_max
    the page you are looking for
if x < pn_min
    go left
if x > pn_max
    go right

为了能够检索某个范围内的 id，您首先要在树中找到该范围的最小值( x )(使用普通搜索)。如果它不存在，则意味着您已经搜索到了一片叶子。调用 pn :

if x < pn_min
    start from pn
if x > pn_max
    start from pn->next

在哪里 pn->next是线程树中的下一个节点。现在你有了一个起始页面。只需浏览页面并检索 ID，直到达到范围的最大值。如果页面结束，请转到 next线程树中的页面并继续如上。

由于树是平衡的，这应该给你 O(logn)在搜索/插入/删除操作中，因为它是线程的，它应该给你 O(logn + k) (其中 k 是给定范围内的 id 数)在间隔查询中。

注意:您的树不需要在两个方向都有线程。 GNU's libavl似乎有你需要的工具，但如果它更简单，或者你必须自己编写，你可以只考虑右线程树。

编辑 : 根据 r 查询范围转至 s身份证。

稍作修改，您也可以实现这一点。该算法与查找一系列实际 id 相同，只是查找第一个元素不同。

让我们在每个节点上附加一个数字，表示该节点左侧插入了多少个 id。调用 pn_before .另外，请调用 pn_size作为 pn 中的 id 数.现在搜索 rth id( [rth, sth] ids 范围内的第一个)变为如下:

passed = 0
pn = root
while pn not leaf
    if passed + pn_before < rth <= passed + pn_before + pn_size
        the node you are looking for
    if rth <= passed + pn_before
        go left
    if rth > passed + pn_before + pn_size
        passed += pn_before + pn_size
        go right

解释什么是 passed ，想象下面的树

          __________ p3 {5, 6} before: 4___________
         /                                         \
  ______p2 {2, 3, 4} before: 1              _______p5 {9}: before 2_____
 /                                         /                            \
p1 {1} before: 0                          p4 {7, 8}: before 0           p6 ...

现在假设您正在寻找第 7 个元素(在此示例中也具有 id 7)。如果你查看根 ( p3)，你会看到它前面有 4 个 id，里面有 2 个 id。因此，第 3 个如果适用，你就走对了。现在在这个新树中，您知道您已经传递了 4+2 个 id，因此您必须寻找第 1 个元素，而不是寻找第 7 个元素。变量 passed帮助跟踪当您正确时跳过了哪些 id。

或者，您可以减少 pn_before和 pn_size来自 rth , 所以 rth实际上每次都会变小。是一样的(但记得备份 rth，因为你以后会需要它)

一旦你找到 rth 的位置元素，你继续之前的区间查询算法。

现在唯一剩下的问题是更新 pn_before .这很简单。由于每个子树的每个根只跟踪它的左子树，因此在插入/删除时，您需要向上到树的根并添加/删除 pn_before该节点的数量由刚刚插入/删除的 id 数量决定。记住只在你从左 child 开始的地方改变 parent 。如果你去找 parent 并且你在正确的 child 身上， parent 不需要跟踪你。请注意，在这种情况下，您不应停止，因为 parent 可能是其 parent 的左 child 。

在纸上做，你会明白的；)

另注:关注 pn_before当你重新平衡树时。

再次搜索 O(logn + k)在哪里 k是您正在查询的区间内的 id 数( s - r )。在插入/删除中向后退到根的额外步骤不会改变这些算法的顺序，因为向后的步骤也是 O(logn) .