google-app-engine - 用于之字形合并连接的大 O？

Question

zig-zag 合并连接算法的大 O 是多少？

GAE 的 Big Table 使用它，他们在这些视频中进行了介绍：

• http://www.youtube.com/watch?v=AgaL6NGpkB8
• http://www.bestechvideos.com/tag/zigzag-merge-join

我问的原因是，如果我正确理解了这个例子，对于包含非常多匹配项的集合，Big O 将接近 O(n)，其中只有一个匹配项，但不是两者都匹配（或本示例中的所有三个匹配项）。

Answer 1

阅读索引选择文章的性能部分：

实际性能取决于数据的形状。具体来说，为每个返回的结果考虑的平均实体数为 O(S/R)。这表明当许多实体与每次扫描匹配，但很少有实体与整个查询匹配（R 小而 S 大）时，性能可能会很差。

正如文章指出的那样，这只影响正常的索引。如果你想要 O(log n) 速度，你应该定义一个复合索引。