Redis 的 ZSet 取数据的时间复杂度？

https://www.nowcoder.com/discuss/694309108597448704

正确答案：Redis 的 ZSet（有序集合）取数据的时间复杂度是 O(log(N) + M)，其中 N 是集合中元素的数量，M 是要返回的元素数量。

解答思路：Redis 的 ZSet 是基于跳表（Skip List）实现的，跳表是一种随机化的数据结构，能够在 O(log(N)) 的时间复杂度内进行查找、插入和删除操作。当我们从 ZSet 中取数据时，通常会用到 ZRANGE 命令来获取特定范围的元素。在执行这个操作时，Redis 首先会通过跳表定位到指定的区间起始位置，这一步的时间复杂度是 O(log(N))。

一旦找到了起始位置，接下来的步骤是遍历跳表中的元素，直到达到指定的数量 M，因此这一部分的复杂度是 O(M)。因此，总体时间复杂度为 O(log(N) + M)。

问题考点的深度知识讲解：为了更深入地理解 ZSet 的实现原理，我们需要了解跳表的基本结构和特点。跳表是由多个层级的链表组成，底层链表包含所有的元素，而每一层的链表都是从底层链表中随机抽取的元素，形成高层的索引。通过这种方式，跳表能够快速地跳过大量元素，从而提高查找效率。

具体来说，跳表的查找过程如下：

从最高层链表的头开始，逐层向右查找，直到找到第一个大于或等于目标值的元素。
如果当前层的元素小于目标值，则向下移动到下一层，继续查找。
一直重复这个过程，直到找到目标元素或达到底层链表。

这种结构的随机性使得跳表在平均情况下能保持 O(log(N)) 的时间复杂度，而在最坏情况下仍然能够保证 O(N) 的时间复杂度，不过这种情况较少出现。

伪代码示例：

function ZRANGE(zset, start, stop):
node = zset.head
for level from highest to lowest:
while node.next[level] exists and node.next[level].score < start:
node = node.next[level]
result = []
node = node.next[0] // move to the first element in the range
while node exists and node.score <= stop:
result.append(node.value)
node = node.next[0] // move to the next element
return result

通过这个伪代码，我们可以看到 ZSet 的 ZRANGE 操作是如何通过跳表高效地找到范围内的元素并返回的。这种设计不仅保证了高效的查找时间，还能支持其他操作，比如 ZADD 和 ZREM，保持集合的有序性。