1

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

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

任何关于我应该使用的设计/数据结构的建议，或者关于这些主题的简明教育材料的指针都将非常感激。

4

3 回答 3

4

使用 Boost.MultiIndex，您不需要多达 12 个索引（顺便说一句，4 个元素的排列数是 4！=24，而不是 12）来涵盖包含 4 个键的特定子集的所有查询：感谢使用的组合键，并且有一点独创性，6个索引就足够了。

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

使用 Boost.MultiIndex 进行多属性查询

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

这背后的数学原理并非微不足道，您可能希望安全地忽略它：但是，如果您需要帮助理解它，请不要犹豫对博客文章发表评论。

这个容器使用了多少内存？在典型的 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，这是相当强大的野兽（不知道你用的是不是这么大的东西。）

于 2011-07-22T20:01:38.223 回答
1

B-Tree 索引和位图索引是使用的两个主要索引，但它们不是唯一的。你应该探索它们。让你开始的东西。

评估何时使用 B-Tree 以及何时使用 Bitmap 的文章

于 2011-07-22T15:50:11.947 回答
0

老实说，这取决于访问它的算法。如果这个结构需要常驻，并且你能负担得起内存消耗，那就去做吧。multi_index 很好，但如果它在标题中，它会破坏你的编译时间。

如果您只需要一次遍历，那么构建结构将是一种浪费。像next_permutation这样的东西可能是一个不错的起点。

于 2011-07-22T15:56:20.470 回答