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

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

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

这是次优的,原因有两个:

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