Redis ZRANGEBYLEX 命令复杂度

Question

根据 ZRANGEBYLEX command 的文档部分, 有以下信息。如果将键存储在零分的有序集中，则可以按字典顺序检索后面的键。 ZRANGEBYLEX 操作复杂度为 O(log(N)+M)，其中 N 是元素总数，M 是结果集大小。文档有一些关于字符串比较的信息，但没有说明将存储元素的结构。

但经过一些实验和阅读之后source code ，这可能是 ZRANGEBYLEX 操作具有线性时间搜索的原因，此时 ziplist 中的每个元素都将与请求匹配。如果是这样，复杂度将比上面描述的更大——大约 O(N)，因为 ziplist 中的每个元素都将被扫描。

用gdb调试后，很明显ZRANGEBYLEX命令在genericZrangebylexCommand中实现了功能。控制流在 eptr = zzlFirstInLexRange(zl,&range); 处继续，因此元素检索的主要工作将在 zzlFirstInLexRange 处执行。功能。所有命名和后续控制流都考虑使用ziplist结构，所有与输入操作数的比较都是逐个元素顺序进行的。
在 redis 存储中插入众所周知的键后通过分析检查内存，似乎 ZSET 元素确实存储在 ziplist 中 - 与 gauge 逐字节比较确认一下。

那么问题 - 文档怎么会出错并在出现线性复杂度的地方传播对数复杂度？或者 ZRANGEBYLEX 命令的工作方式略有不同？提前致谢。

Answer 1

how can documentation be wrong and propagate logarithmic complexity where linear one appears?

该文档多次出错，但这是一项持续的开源工作，您可以通过存储库 (https://github.com/antirez/redis-doc) 为之做出贡献。

Or maybe ZRANGEBYLEX command works slightly different?

从某种意义上说，您的结论是正确的，因为当使用 Ziplist 对其进行编码时，排序集搜索操作(无论是否按字典顺序)都表现出线性时间复杂度。

但是。

Ziplists 是一种更喜欢 CPU 而不是内存的优化，这意味着它适用于小集合(即低 N 值)。它通过配置进行控制(参见 zset-max-ziplist-entries 和 zset-max-ziplist-value 指令)，一旦数据增长超过指定阈值ziplist 编码转换为 skip list .

因为 ziplist 很小(小 N)，它们的复杂度可以假设为常数，即 O(1)。另一方面，由于它们的性质，跳跃列表表现出对数搜索时间。 IMO 这意味着文档的完整性保持不变，因为它提供了最坏情况下的复杂性。