Ordered Set

An ordered set is same as the sorted set data structure in Redis.  An ordered set can be implemented using a number of data structure.  Like the sorted set in Redis is implemented using Skip List. It can be implemented using AVL tree, Red-Black Tree, Splay Tree.

An ordered set is a common data structure that supports O(log N) lookups, insertions and removals.

Complexities of various operations on an ordered set are as follows:

  • O(log N) insertion and removal.
  • O(log N) check if contains a value.
  • O(N) enumeration in sorted order.
  • O(log N) to find the element in the set closest to some value.
  • O(log N) to find k-th largest element in the set. This operation requires a simple augmentation of the the ordered set with partial counts.
  • O(log N) to count the number of elements in the set whose values fall into a given range, in O(log N) time. Also requires a simple augmentation of the ordered set.

With respect to Redis –

Sorted sets are the only other data structures in Redis, besides lists, to maintain ordered elements. You can do a number of cool stuff with sorted sets. For instance, you can have all kinds of Top Something lists in your web application. Top users by score, top posts by page views, top whatever, but a single Redis instance will support tons of insertion and get-top-elements operations per second.
Sorted sets, like regular sets, can be used to describe relations, but they also allow you to paginate the list of items and to remember the ordering. For instance, if I remember friends of user X with a sorted set I can easily remember them in order of accepted friendship.

Sorted sets are like more powerful lists where inserting, removing, or getting ranges from the the middle of the list is always fast. But they use more memory, and are O(log(N)) data structures.

Sorted sets are good for priority queues.
Priority queue are generally implemented using Heap. 

 

 

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s