1

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

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

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

4

3 回答 3

2

看起来是时候切换到 B 树（可能是 B+ 或 B*）了——这种结构在数据库中用于管理索引。看看这里——这是对内部带有 btree 的类 std 关联容器的替代品......但是 btree 可用于将索引保存在内存和磁盘上......

于 2013-02-18T15:29:37.430 回答
2

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

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

其中map非常大，而单个集合非常小。这里有几个开销来源：

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

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

map但是，您可以通过将 s与sets 组合使用这样的数据结构来减少开销而不会丢失功能：

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

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

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 s associate with the key, while a call toupper_bound(std::make_pair(key, INT_MAX))` 的开始迭代器，将为您提供相应的结束迭代器，因此您可以轻松地迭代与给定键关联的所有值。

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

于 2013-02-18T16:26:03.330 回答
1

对于如此大规模的数据集，您应该真正使用适当的数据库服务器，例如SQL 服务器。这些服务器旨在处理缓存的大规模数据集。SQL 服务器将数据保存到诸如 HDD 之类的永久缓存中，同时通过缓存经常访问的页面等来保持良好的读/写性能。

于 2013-02-18T15:28:22.977 回答