c++ - 小数据大数据集多重索引: space inefficient?

Question

我根本不是数据库设计方面的专家，所以在尝试将其翻译成 CS 术语之前，我会用简单的语言表达我的需求:我正在尝试找到快速迭代大型子集的正确方法(比如 ~ 100Mo of double) 数据，在一个可能非常大的数据集中(比如几个 Go)。我的对象基本上由 4 个整数(键)和值组成，一个简单的结构(1 双 1 短)。因为我的键只能接受少量的值(几百个)，所以我认为将我的数据保存为树是有意义的(1 键深度，值是叶子，至少在我天真的观点中很像 XML 的 XPath) .

我希望能够根据键值/这些键值的函数遍历叶子的子集。要过滤的组合键会有所不同。我认为这称为横向搜索？
因此，为了避免比较 n 次相同的键，理想情况下我需要数据结构由键的每个排列索引(12 种可能性: !4/!2 )。这似乎是 boost::multi_index 的用途，但是，除非我忽略了 smth，否则这样做的方式实际上是构建这 12 个树结构，将指向我的值节点的指针存储为树叶。考虑到我的值与键相比较小，我想这将是非常低效的空间。

对于我应该使用的设计/数据结构的任何建议，或关于这些主题的简明教育 Material 的指针，我们将不胜感激。

Answer 1

使用 Boost.MultiIndex，您不需要多达 12 个索引(顺便说一句，4 个元素的排列数是 4!=24，而不是 12)来涵盖包含 4 个键的特定子集的所有查询:谢谢使用composite keys , 稍微巧妙一点，6 个索引就足够了。

巧合的是，几年前我在我的博客中提供了一个示例，展示了如何以几乎完全符合您的特定场景的方式执行此操作:

Multiattribute querying with Boost.MultiIndex

我们提供了源代码，希望您只需稍作修改即可使用以满足您的需要。同一博客中的一系列文章也提供了该构造的理论依据:

• A combinatory theorem
• Generating permutation covers: part I
• Generating permutation covers: part II
• Multicolumn querying

这背后的数学原理并不简单，您可能想要安全地忽略它:不过，如果您在理解它时需要帮助，请不要犹豫，对博客文章发表评论。

这个容器使用了多少内存？在典型的 32 位计算机中，对象的大小为 4*sizeof(int)+sizeof(double)+sizeof(short)+padding，通常产生 32 字节(在 Win32 上使用 Visual Studio 检查)。为此 Boost.MultiIndex 添加了每个索引 3 个字(12 字节)的开销，因此对于容器的每个元素，您都有

32+6*12 = 104 字节 + 填充。

再次，我在 Win32 上使用 Visual Studio 检查，得到的大小是每个元素 128 字节。如果您有 10 亿 (10^9) 个元素，那么 32 位是不够的:转到 64 位操作系统很可能会使对象的大小增加一倍，因此所需的内存将达到 256 GB，这是相当强大的beast(不知道你用的是不是这么大的东西。)