3

我需要实现一个具有超过 100M 记录的优先级队列的应用程序。我的问题是我无法将所有这些数据保存在内存中，因此我需要将其存储在磁盘上。有没有可以将所有这些信息存储到磁盘的缓存解决方案？

4

1 回答 1

1

我认为您可以通过使用 B-tree 进行一些小的修改来解决这个问题。

B-trees 专门设计用于以最小化定位任何元素所需的磁盘读取次数的方式将排序的元素存储在磁盘上。因为它们按排序顺序存储元素，所以您可以将它们用作优先队列，方法是正常执行插入并通过获取树中最左边的元素（即最左边叶节点的第一个元素）来查找最小元素。

在 d 阶的 B 树中，您可以使用 O(log d n) 磁盘读取和写入来找到最小元素，其中 n 是元素的总数。插入和删除也只需要 O(log d n) 磁盘读取和写入。

但是，您可以通过存储指向 B 树中最左侧叶节点的指针来显着加快此速度。该节点将存储最小密钥以及接近最小值的其他密钥。如果你有这个指针，你可以通过获取节点中的第一个元素来查找单个磁盘读取中的最小值。这也加快了 extract-min 操作：您可以直接从该节点删除密钥，而无需搜索它。完成这项工作可能需要一些 B-tree 重新平衡操作，尽管您可以证明这些操作很少发生，以至于执行删除的摊销工作仅为 O(1)。

换句话说，使用带有指向最左边叶子的指针的 B 树在磁盘读取和写入方面具有以下时间复杂度：

  • 查找最小值：O(1)
  • 插入：O（log d n）
  • extract-min: O(1)摊销

希望这可以帮助！

于 2014-05-31T18:54:13.150 回答