c++ - 节省内存的 map<pair<int,int>, set<int>> 替代方案

Question

我有大量(15 亿)个整数对，其中每个整数对都与一个文档 ID 相关联。我现在的目标是搜索具有相同对的文档。

我的第一个想法是使用 HashMap ( std::map )，使用对值作为键，将文档 ID 作为关联值，即 map<pair<int,int>, unordered_set<int>>

例如:

Document1

 - pair1: (3, 9)
 - pair2: (5,13)

Document2

 - pair1: (4234, 13)
 - pair2: (5,13)

map<pair<int,int>, unordered_set<int>> hashMap
hashMap[{3, 9}].insert(1)
hashMap[{5, 13}].insert(1)

hashMap[{4234, 13}].insert(2)
hashMap[{5, 13}].insert(2)

会导致

Key(3,9) = Documents(1) 
Key(5,13) = Documents(1,2) 
Key(4234,13) = Documents(2)

我现在的问题是，这需要大量内存，超出了我可用的 24 GB RAM。因此，我需要一个具有良好插入和查找性能的替代方案，并且可以适合我的内存。理论上我正在使用 1500 Million * 3 (PairVal1, PairVal2, Document-ID) * 4 (bytes per Integer) = 18GB当不考虑管理费用时。那么对于我的问题有什么好的替代方案吗？

Answer 1

这可能是嵌入式数据库的工作，例如 SQLite、BerkeleyDB 或 Tokyo Cabinet。

如果您使用的数据量超过了 RAM，那么您确实需要可以从磁盘运行的东西。