SortedSet Big O question

[Ohad]

Hi,
How come getting the first/last member of a sorted-set takes O(log(N)
+1) and not just O(1)?
It seems like you already pay(ZADD- O(log(N))) when you inset an
element to the set..

Do I miss anything?

[Pieter Noordhuis]

Hi,

Sorted sets are backed by a skiplist, which has O(log(N))
search/insert/delete operations. I think you refer to retrieving the
first element with "ZRANGE key 0 0", where the lookup will indeed be
O(1). It is a common practice, however, to specify the amortized (or:
average) complexity for retrieving elements starting at any index,
which comes down to O(log(N)) for sorted sets. The +N term in the
ZRANGE complexity is determined by the number of elements in the reply
(thus unrelated to skiplist complexity).

Does this answer your question?

Cheers,
Pieter

> --
> You received this message because you are subscribed to the Google Groups "Redis DB" group.
> To post to this group, send email to redi...@googlegroups.com.
> To unsubscribe from this group, send email to redis-db+u...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/redis-db?hl=en.
>
>

[Ohad]

Yes thanks,
I wish I could maintain some sort of a pointer for that SortedSet and
after ZRANGE key 0 0 I could get ZRANGE key 1 1 in O(1) as well...

[Josiah Carlson]

For what purpose would having a pointer help you? The round-trip
latency between your client and server will cover up any O(log(n))
operation costs.

Are you looking to not retrieve duplicate items or not to skip items
while your zset is being manipulated? There are methods to solve that
particular problem on the most part, depending on the kinds of
manipulations you are performing, your scores, etc.

What is your real intent by pulling down zrange key 0 0, zrange key 1
1, zrange key 2 2, etc.?

- Josiah