1

背景：

我读过许多 DBMS 使用预写日志记录，通过将更新存储为一组写操作来保持事务的原子性和持久性。我想要完成的是创建一个具有改进并发性的 dbms 模型，方法是允许在写入挂起时对“旧”数据进行读取。

问题：

是否有一种数据结构可以让我有效地（理想情况下 O(1) 摊销，最多 O(log(n)）查找数组元素（或内存位置，如果你愿意的话），它可能被也可能不会被覆盖写动作，参考某个时间点？这将是大约 1TB 的数据总量。

这是一些 ascii 艺术，可以使这一点更清晰。破折号是数据，版本 0 是最旧的版本。箭头表示写操作。

^ ___________________________________快照 2
 | 五 | | 五                         
 | -- --- | | -------- 版本 2
 | | | __________________快照 1
 | 五 | | 五                    
T| -------- | | --------- 版本 1
我| | | ___________快照 0
米| VVVV                 
E|------------------------------------- 版本 0
 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~>
  空间/地址

解决方案的尝试：

令 N 为数据大小，M 为版本数，P 为每个版本的平均更新次数。

  • 朴素算法（搜索每个更新）是 O(M*P)。
  • 将数据划分为桶，仅更新整个桶，并搜索桶的位掩码将是 O(N/B*M)，其中 B 是桶大小，也好不了多少。
  • 乍一看，Bloom 过滤器似乎是一个不错的选择，除了它需要比每个内存位置的简单位掩码更多的数据（这无论如何都会很糟糕，因为它需要 M*N/8 字节来存储。）
  • 一个标准的哈希表也浮现在脑海中，但关键是什么？

实际上，既然我已经把这一切都写完了，我已经想到了一个使用二叉搜索树的解决方案。我稍后会提交它作为答案，但它在空间和时间上仍然是 O(M*log2(P))，这并不理想。见下文。

4

1 回答 1

0

以下是我能想出的最佳解决方案，尽管它仍然不是最理想的。

这个想法是将每个区域放入二叉搜索树中，每个版本一棵树，其中每个内部节点包含一个内存位置，每个叶节点是Hit或Miss（可能是查找信息），具体取决于那里是否存在更新的数据。这是为每个版本构建的 O(P*log(P))，以及查找的 O(M*log(P))。

这是次优的，原因有两个：

  • 树是平衡的，但实际上Misses 比 s 更有可能，因此将节点放在树的更高位置或按节点大小排列节点是Hit有意义的。Miss想到了某种霍夫曼编码，但霍夫曼算法不保留搜索树不变量。
  • 它需要 M 树（因此 O(M*log(P)) 查找）。也许有一些方法可以组合树木。
于 2013-06-17T21:58:23.857 回答