Redis ZRANGEBYSCORE 奇怪的行为

Question

我使用的是redis 2.6。我遇到过奇怪的ZRANGEBYSCORE功能行为。我有一个长度约为几百万个元素的排序集。像这样的东西：

10 marry 
15 john 
25 bob 
...

因此与查询进行比较：

ZRANGEBYSCORE longset 25 50 LIMIT 0 20  works like a charm, it takes milliseconds
ZRANGEBYSCORE longset 25 50             this one hangs up for a minutes!! 

我感兴趣的所有元素都在该集合的前一百个中。我认为不需要扫描权重大于“50”的元素，因为它是排序集。

请解释一下redis如何扫描排序集以及为什么这两个查询之间有如此大的差异。

Answer 1

在我看来，Redis 最好的事情之一是您可以在文档中检查每个命令的时间复杂度。zrangebyscore的文档指定：

时间复杂度：O(log(N)+M)，其中 N 是排序集中的元素数量，M 是返回的元素数量。如果M是常数（例如总是要求前10个带有LIMIT的元素），你可以认为它是O(log(N))。

[...]

请记住，如果offset很大，则需要先遍历排序集以查找offset元素，然后才能返回要返回的元素，这可能会增加O(N)时间复杂度。

这意味着，如果您知道只需要一定数量的项目，并指定 a LIMIT offset count，如果offsetis (close to) 0，则可以考虑O(log(N))，但如果返回的项目数量很高（或偏移量很高），可以认为是O(N)。