Austin's SWE Notes 😭

    Sorted Set

    Sorted set is a datastructure in redis which is like a set and a hash map combined.

    • Every elements in the sorted set is unique
    • Each element also given an index (ranking) to sort

    [!note]
    It's somewhat like a Priority Queue as well, however priority queue is an array and this one is a set

    In sorted set, when the score are the same, they will be ordered in lexicographically (alphabetically) order

    Use case

    Leader Board: maintain the list of high score players

    Rate Limiter: helpful when building Sliding window log rate limiter or Sliding window counter algorithm

    Syntax

    ZADD key score member

    For example

    > zadd hackers 1940 "Alan Kay"
(integer) 1
> zadd hackers 1957 "Sophie Wilson"
(integer) 1
> zadd hackers 1953 "Richard Stallman"
(integer) 1
> zadd hackers 1949 "Anita Borg"
(integer) 1
> zadd hackers 1965 "Yukihiro Matsumoto"
(integer) 1
> zadd hackers 1914 "Hedy Lamarr"
(integer) 1
> zadd hackers 1916 "Claude Shannon"
(integer) 1
> zadd hackers 1969 "Linus Torvalds"
(integer) 1
> zadd hackers 1912 "Alan Turing"
(integer) 1

    Which will return

    > zrange hackers 0 -1
1) "Alan Turing"
2) "Hedy Lamarr"
3) "Claude Shannon"
4) "Alan Kay"
5) "Anita Borg"
6) "Richard Stallman"
7) "Sophie Wilson"
8) "Yukihiro Matsumoto"
9) "Linus Torvalds"

    [!note]
    Sorted set is implemented using dual-ported datastructure containing both a Skip List and a hash table. Therefore, everytime we add an element into Redis sorted set will be $O(logn)$ complexity.

    ← Parameterised Test
    Decorator →