优先级队列可以存储在磁盘上吗？
我需要实现一个具有超过 100M 记录的优先级队列的应用程序。我的问题是我无法将所有这些数据保存在内存中，所以我需要将其存储在磁盘上。是否有任何缓存解决方案可以将所有这些信息存储到磁盘？
I need to implement a application which has a priority queue which has more than 100M records. My problem is I am not able to keep all this data in memory, so I need to store it on disk. Is there any cache solution where I can store all this information to disk?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为您可以通过使用 B 树并进行一些小的修改来解决这个问题。
B 树专门设计用于在磁盘上存储排序元素，从而最大限度地减少定位任何元素所需的磁盘读取次数。因为它们按排序顺序存储元素，所以您可以通过正常执行插入并通过获取树中最左边的元素（即最左边叶节点的第一个元素）查找最小元素来将它们用作优先级队列。
在 d 阶 B 树中，您可以使用 O(logd n) 次磁盘读写来找到最小元素，其中 n 是元素总数。插入和删除也只需要 O(logd n) 次磁盘读写。
但是，您可以通过存储指向 B 树中最左边叶节点的指针来显着加快速度。该节点将存储最小密钥以及接近最小值的其他密钥。如果你有这个指针，你可以通过获取节点中的第一个元素来查找单个磁盘读取中的最小值。这也加速了 extract-min 操作：您可以直接从该节点删除密钥，而无需搜索它。完成这项工作可能需要一些 B 树重新平衡操作，尽管您可以证明这些操作很少发生，以至于执行删除的摊销工作仅为 O(1)。
换句话说，使用带有指向最左边叶子的指针的 B 树在磁盘读写方面具有以下时间复杂度：
希望这有帮助！
I think that you can solve this by using a B-tree with a few minor modifications.
B-trees are specifically designed to store sorted elements on-disk in a way that minimizes the number of disk reads necessary to locate any element. Because they store their elements in sorted order, you can use them as priority queues by performing insertions as normal and finding the minimum element by taking the leftmost element in the tree (i.e. the first element of the leftmost leaf node).
In a B-tree of order d, you can find the minimum element using O(logd n) disk reads and writes, where n is the total number of elements. Insertions and deletions will also only require O(logd n) disk reads and writes.
However, you can significantly speed this up by storing a pointer to the leftmost leaf node in the B-tree. This node will store the minimum key plus other keys close to the minimum. If you have this pointer, you can look up the minimum value in a single disk read by taking the first element in the node. This also speeds up the extract-min operation: you can delete the key directly from that node without having to search for it. There may be some B-tree rebalancing operations necessary to make this work, though you can show that these operations happen so infrequently that the amortized work to do a deletion is only O(1).
In other words, using a B-tree with a pointer to the leftmost leaf has the following time complexities in terms of disk reads and writes:
Hope this helps!
您可以对 templatetypedef 提到的 B 树方法进行一项相当接近最佳的标准改进，即使用 B-epsilon 树，其中对引导枢轴之前的任何内容的更新都是严格的。
对于 epsilon = 1/2，这意味着每个 B 树节点仅保存 sqrt(B) 枢轴，但还保存最多 B - sqrt(B) 个要插入的元素的缓冲区，这些元素被分成大致为大小为 sqrt(B)。每当一个块溢出时，它就会被批量插入到相应的子节点中。这样做的缺点是，由于树的深度加倍，随机访问点搜索使用的磁盘读取次数是原来的两倍，但它使插入操作更快，因为它们需要摊销 O(log B / sqrt B) 磁盘访问次数，并且 O(log B B) 磁盘访问最坏情况。
由于对于优先级队列，您不太关心随机访问，并且您有一个指向引导节点的指针，因此您可能需要 B-epsilon 树来加速对非引导节点的插入。当然，如果添加标准 B+ 树优化，您还可以按排序顺序快速迭代插入的值。
（实际的实现可能会进一步添加启发式改进，例如记住刷新插入的每个节点的最后一个子节点，以便在子节点已经在缓存中的情况下直接插入到该子节点，还可以加快批量插入的常见情况如果分摊写入的延迟峰值不是问题，另一个有时会派上用场的技巧是使用两个标准 B 树，其中一个大小为 sqrt(N) 用于缓存插入，另一个大小为 sqrt(N) 用于缓存插入。其他大小为 N 的数据用于读取，因为 RAM 大小通常小于磁盘大小的 sqrt，在这种情况下，较小的 B 树可以用自适应基数 trie 或类似的东西替换。）
One standard improvement you can make to the B-tree approach mentioned by templatetypedef that is fairly close to optimal is to use a B-epsilon tree where updates to anything ahead of the lead pivot are strict.
For epsilon = 1/2, this means that each B tree node holds only sqrt(B) pivots but also holds a buffer of up to B - sqrt(B) elements-to-be-inserted that are split into chunks that are roughly of size sqrt(B). Whenever a chunk overflows, it is bulk-inserted to the corresponding child node. This has the downside of making random access point searches use twice as many disk reads since the depth of the tree is doubled, but it makes insert operations faster because they take O(log B / sqrt B) disk accesses amortized, and O(log B) disk accesses worst case.
Since for a priority queue you do not care as much about random access and you had a pointer to the lead node, you probably want a B-epsilon tree to speed up inserts to non-leading nodes. And of course, if you add the standard B+ tree optimization you also get fast iteration of the inserted values in sorted order.
(practical implementations may further add heuristic improvements like remembering the last child from each node that it flushed inserts to so that you insert directly to that child in cases where it is already in cache, to also speed up the common case where you are bulk inserting a range of values to the same leaf node. Another trick that sometimes comes in handy if latency spikes from amortized writes are not a problem is to have two standard B-trees, with one being of size sqrt(N) to cache inserts and the other of size N to do reads, since RAM size is typically smaller than the sqrt of the size of disk, in this case the smaller B-tree can be replaced by an adaptative radix trie or something similar.)