3

我正在尝试查看是否可以将特定算法转换为 RavenDB/CouchDB 使用的那种 map-reduce 索引，即“预先计算的”map-reduce（这意味着索引在插入和更新时刷新，而不是在执行实际查询）。

假设我们有一个典型的在线商店，有 50,000 种产品，按类别分组。每个产品都有一个“属性值”的集合，例如“[Red, Round, Metal]”。

由于我们的网站上有很多产品，而且每个类别中可能有很多项目，我们希望为用户提供另一种方式来“过滤”他当前看到的产品。

例如，如果一个类别是“低于 20 美元”，那么这个类别中有一大堆产品。但是我们的用户只需要看到低于 20 美元和红色的产品。不幸的是，“低于 20 美元”类别中没有子类别“红色”。

我们的算法将获取当前的产品列表，并生成一个“有趣的”属性和属性值列表，即，给定一个产品列表，它会输出如下内容：

Color
   Red (40)
   Blue (32)
   Yellow (17)
Material
   Metal (37)
   Plastic (36)
   Wood (23)
Shape
   Square (56)
   Round (17)
   Cylinder (12)

这种算法是否可以通过某种方式预先计算 à la RavenDB/CouchDB map-reduce 索引？如果不是，为什么是这样（这样我将来可以识别那种算法），如果是，怎么做？

提供了一个C# 4.0 Visual Studio 测试解决方案，它演示了潜在的数据结构和示例数据，以及尝试使用 map-reduce 实现（这似乎不是可预计算的）。

4

2 回答 2

2

一般情况：总是可以使用 CouchDB 样式的 map-reduce 视图，但不一定实用。

最后，它主要是基于计数的论点：如果您需要针对 500,000 种产品的任何子集提出问题，那么您的数据库必须能够为2500,000个不同的可能问题中的每一个提供不同的答案，它使用如果您必须为它们中的每一个发出一个 B 树叶子（并且您需要发出数据，除非这些查询中的大多数的答案是零、假、空集或类似的空值），则内存量会令人望而却步。

CouchDB 通过范围查询的存在提供了第一个小优化（这意味着在理想情况下，它可以使用尽可能少的 N B-tree 叶子来回答 N 2 个问题）。但是，在您的示例中，这只会将叶子数量减少到 2 250,000（这是理论上的下限）。

CouchDB 通过键前缀查询提供了第二个小优化，这意味着您可以将 [A]、[A,B] 和 [A,B,C] 查询压缩为单个 [A,B,C] 键。所以，而不是你的 2 250,000种可能性，而是“仅仅” 2 249,999 ...

因此，虽然您可以想出一个发射策略来回答任何子集的问题，但它会占用比我们星球上实际可用的更多的存储空间。在一般情况下，要回答 N 个不同的问题，您至少需要发出sqrt(N/2)B 树的叶子，因此计算您的问题并确定叶子数量的下限是否可以接受。

仅适用于类别和子类别：如果您放弃任意产品列表并只提出“给我类别 A 中由属性 B 和 C 过滤的重要属性”形式的问题，那么您的排放数量将下降到：

 AvgCategories * AvgAttr * 2 ^ (AvgAttr - 1) * 500,000

您基本上为每个产品发出了产品[Category,Attr,Attr,...]所有类别的键以及产品属性的所有组合，这使您可以按类别 + 属性进行查询。如果每个产品平均有 1 个类别和 3 个属性，那么这将产生大约 600 万个条目，这是可以接受的。

于 2010-11-26T12:29:05.723 回答
0

这应该很容易在 CouchDB 之类的东西中实现。让索引的映射阶段为对象具有的每个属性输出一个键值对，值简单地为“1”。然后，让 reduce 阶段对所有输入值求和并输出总和。最终结果将是您描述的表单的索引。

于 2010-11-25T23:29:24.023 回答