背景:
我读过许多 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)),这并不理想。见下文。