If Redis Sorted Set is implemented with Skip List, why ZPOPMIN time complexity is O(log n)?

Question

I already read this question and it isn't what I'm looking for.

As far as I know, deleting first m elements in a Skip List containing n elements takes O(m) or we can say O(1) if m is not significant. But why ZPOPMIN in Redis takes O(log n)?

Answer 1

I do not know about the exact implementation that Redis have. However, if the sorted set is implemented using Skip List, the deletion will take O(log n).

From the observation on how the skip lists are built, I think you might get the idea. This is not implemented using a simple single array which will take O(m) time to delete the first m elements. Instead, it uses multiple arrays (think this as a linked list) and stores the values cleverly to support the add/delete/search in O(log n) time.

If it was implemented using a single array, then you are right - the deletion should take O(m) time. However, this is not the case for the skip lists. I am trying to add a picture from where you can have an idea of how the lists are being built.

Hope that helps!

Update

Please keep in mind that skip list has levels. The maximum number of levels a skip list can have is O(log n). Let us consider deleting the first three elements here (i.e. 12, 17, 20). To remove 12 first, we have to modify the level 2 and level 1 as we have to point the - ∞ to 17 in both levels. Once the 12 is removed, then we remove the 17 and do the same here as well. For each deletion, we might have to iterate at most O(log n) levels as stated above about the maximum number of levels. I hope you get the idea.