google-app-engine - 用于锯齿形合并连接的大O？

Question

zig-zag 合并连接算法的 Big 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

阅读Performance索引选择文章部分:

The actual performance depends on the shape of the data. Specifically, the average number of entities considered for each result returned is O(S/R). This indicates that poor performance is likely when many entities match each scan, but few entities match the query as a whole (R is small and S is large).

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