如果Redis Sorted Set是用Skip List实现的，为什么ZPOPMIN的时间复杂度是O(log n)？
If Redis Sorted Set is implemented with Skip List, why ZPOPMIN time complexity is O(log n)?
我已经阅读了 ，这不是我要找的。
据我所知，删除包含 n 元素的跳过列表中的第一个 m 元素需要 O(m) 或者我们可以说 O(1) 如果 m 并不重要。但是为什么Redis中的ZPOPMIN需要O(log n)呢？
我不知道 Redis 的确切实现。但是如果sorted set是用Skip List实现的，则删除需要O(log n)。
通过观察跳过列表的构建方式，我想您可能会明白。这不是使用简单的单个数组实现的，它需要 O(m) 时间来删除第一个 m 元素。相反，它使用多个数组（将其视为链表）并巧妙地存储值以支持 O(log n) 时间内的 add/delete/search。
如果它是使用单个数组实现的，那么您是对的 - 删除应该花费 O(m) 时间。但是，跳过列表不是这种情况。我正在尝试添加一张图片，您可以从中了解列表的构建方式。
希望对您有所帮助！
更新
请记住跳表是有等级的。跳跃列表的最大级别数为 O(log n)。让我们考虑在这里删除前三个元素（即 12、17、20）。要首先删除 12，我们必须修改 level 2 和 level 1，因为我们必须在两个级别中将 - ∞ 指向 17。删除 12 后，我们将删除 17 并在此处执行相同操作。对于每次删除，我们可能必须迭代至多 O(log n) 层，如上所述关于最大层数。我希望你明白了。
我已经阅读了
据我所知，删除包含 n 元素的跳过列表中的第一个 m 元素需要 O(m) 或者我们可以说 O(1) 如果 m 并不重要。但是为什么Redis中的ZPOPMIN需要O(log n)呢？
我不知道 Redis 的确切实现。但是如果sorted set是用Skip List实现的，则删除需要O(log n)。
通过观察跳过列表的构建方式，我想您可能会明白。这不是使用简单的单个数组实现的，它需要 O(m) 时间来删除第一个 m 元素。相反，它使用多个数组（将其视为链表）并巧妙地存储值以支持 O(log n) 时间内的 add/delete/search。
如果它是使用单个数组实现的，那么您是对的 - 删除应该花费 O(m) 时间。但是，跳过列表不是这种情况。我正在尝试添加一张图片，您可以从中了解列表的构建方式。
希望对您有所帮助！
更新
请记住跳表是有等级的。跳跃列表的最大级别数为 O(log n)。让我们考虑在这里删除前三个元素（即 12、17、20）。要首先删除 12，我们必须修改 level 2 和 level 1，因为我们必须在两个级别中将 - ∞ 指向 17。删除 12 后，我们将删除 17 并在此处执行相同操作。对于每次删除，我们可能必须迭代至多 O(log n) 层，如上所述关于最大层数。我希望你明白了。