c++ - 用于存储大量索引的数据结构，每个索引指向一个集合

Question

我在 C++ (std::map) 中使用红黑树实现，但目前，我发现我的 unsigned long long int 索引变得越来越大，以进行更大的实验。我打算使用 700,000,000 个索引，每个索引存储一个 std::set，其中包含更多的 int 元素(大约 1-10 个)。我们有 128 GB RAM，但我发现我们开始用光它了；事实上，如果可能的话，我想在我的实验中甚至下降到 1,000,000,000 个指数。

我对此进行了一些思考，并考虑将几张 map 放在一起形成一片森林。基本上，在 map 达到某个大小阈值后(或者可能在开始抛出 bad_alloc 时)，将其保存到磁盘，将其从内存中清除，然后创建另一个 map 并继续这样做，直到我获得所有索引。然而，在加载部分，这将是非常低效的，因为我们一次只能在 RAM 中保存一张 map 。更糟糕的是，我们需要检查所有 map 的一致性。

那么在这种情况下，我应该寻找哪些数据结构？

Answer 1

根据你的描述，我认为你有这个:

typedef std::map<long long, std::set<int>> MyMap;

其中 map 很大，而各个集合很小。这里有几个开销来源:

• map 中的各个条目，每个条目都是一个单独的分配；
• set 中的各个条目，同上；
• 描述每个集的结构，独立于它们的内容。

使用标准库组件，不可能消除所有这些开销；关联容器的语义很好地要求每个条目的单独分配，而红黑树的使用需要为每个条目添加几个指针(理论上，只需要两个指针，但如果没有，迭代器的有效实现是困难的父指针。)

但是，您可以通过使用如下数据结构将 map 与 set 组合起来，从而在不损失功能的情况下减少开销:

typedef std::set<std::pair<long long, int>> MyMap;

您仍然可以回答所有相同的问题，尽管其中一些不太方便。请记住，std::pair 的默认比较器按字典顺序排序，因此具有相同 first 值的所有元素将是连续的。因此，例如，您可以使用以下方法查询给定索引是否具有与其关联的任何 int:

it = theMap.lower_bound(std::make_pair(index, INT_MIN));
if (it != theMap.end() && it->first == index) {
  // there is at least one int associated with index
}

对 lower_bound 的相同调用将为您提供一个与键关联的 int 的开始迭代器，而对 upper_bound(std::make_pair(key, INT_MAX))` 将为您提供相应的结束迭代器，因此您可以轻松地迭代与给定键关联的所有值。

这可能仍然不足以在 128GB 中存储 7 亿个索引和相关的整数集，除非平均集合大小非常小。下一步必须是某种形式的 b 树，它不在标准库中。 B 树通过将多个条目组合到一个集群中来避免单独的条目开销；这应该足以满足您的需求。