我需要实现一个优先级队列超过 100M 记录的应用程序。我的问题是我无法将所有这些数据保存在内存中，因此我需要将其存储在磁盘上。是否有任何缓存解决方案可以将所有这些信息存储到磁盘？
我认为您可以通过使用 B 树进行一些小的修改来解决这个问题。
B 树专门设计用于在磁盘上存储已排序的元素，从而最大限度地减少定位任何元素所需的磁盘读取次数。因为它们按排序顺序存储它们的元素，所以您可以通过正常执行插入并通过获取树中最左边的元素（即最左边叶节点的第一个元素）找到最小元素来将它们用作优先级队列。
在一棵d阶B树中，可以使用O(logd n)次磁盘读写找到最小元素，其中n是元素总数。插入和删除也只需要 O(logd n) 次磁盘读写。
但是，您可以通过将指针存储到 B 树中最左边的叶节点来显着加快速度。该节点将存储最小键加上接近最小值的其他键。如果你有这个指针，你可以通过获取节点中的第一个元素来查找单个磁盘读取中的最小值。这也加快了 extract-min 操作：您可以直接从该节点删除密钥，而无需搜索它。可能需要一些 B 树重新平衡操作才能完成这项工作，尽管您可以证明这些操作很少发生，以至于执行删除的 amortized 工作仅为 O(1)。
换句话说，使用指针指向最左边叶子的 B 树在磁盘读写方面具有以下时间复杂度：
希望这有帮助！
您可以对 templatetypedef 提到的 B-tree 方法进行的一个标准改进是使用 B-epsilon 树，其中对主枢轴之前的任何内容的更新都是严格的。
对于 epsilon = 1/2，这意味着每个 B 树节点仅包含 sqrt(B) 个枢轴，但也包含最多 B - sqrt(B) 个要插入的元素的缓冲区，这些元素被分成块大小大致为 sqrt(B)。每当一个块溢出时，它被批量插入到相应的子节点。由于树的深度加倍，这使得随机访问点搜索使用两倍的磁盘读取的缺点，但它使插入操作更快，因为它们需要 O(log B / sqrt B) 磁盘访问分摊，并且 O(log B）磁盘访问最坏的情况。
由于对于优先级队列，您不太关心随机访问，并且您有一个指向前导节点的指针，您可能需要 B-epsilon 树来加速对非前导节点的插入。当然，如果您添加标准 B+ 树优化，您还可以按排序顺序快速迭代插入值。
（实际实现可能会进一步添加启发式改进，例如记住它刷新插入到的每个节点的最后一个子节点，以便在它已经在缓存中的情况下直接插入到该子节点，以加快您批量处理的常见情况向同一叶节点插入一系列值）