The most important Redis data structures you must understand
Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker. It supports data structures such as strings, hashes, lists, sets, sorted sets with range queries, bitmaps, hyperloglogs and geospatial indexes with radius queries.
Redis Strings
The Redis String type is the simplest type of value you can associate with a redis key. It is also the base type of the complex types, because a List is a list of strings, a Set is a set of strings, and so forth.
Note that Redis stores everything in its string representation. Even functions like INCR work by first parsing it into INTEGER then performing the operation.
Redis Lists
From a very general point of view, a List is just a sequence of ordered elements: 10,20,1,2,3 is a list. But the properties of a List implemented using an Array are very different from the properties of a List implemented using a Linked List.
linked list example
Redis Lists are implemented with linked lists because for a database system it is crucial to be able to add elements to a very long list in a very fast way.
A linked list is a sequence of nodes that contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.
From the point of time complexity, Redis List supports constant time O(1) insertion and deletion of a single element near the head and tail, even with many millions of already inserted items. However accessing middle elements is very slow if it is a very big list, as it is an O(N) operation.
O(1) operations:
LLEN has constant time complexity, because It is common for data structures to incorporate a “length” variable which is adjusted every time the structure is modified in time complexity at most equal to the complexity of the modifying algorithm. This way, every time you want to know the length, the data structure simply reads the value of that variable.
O(N) operations:
Use Case:
Imagine your home page shows the latest photos published in a photo-sharing social network and you want to speed up access.
Every time a user posts a new photo, we add its ID into a list with LPUSH. When users visit the home page, we use LRANGE 0 9 in order to get the latest 10 posted items.
Another example is a social news feed system explained in the following post .
Redist Sets
Sets stores collections of unique, unsorted string elements. Add, remove, and test for the existence of members is very cheap - constant time regardless of the number of elements contained inside the Set.
If you have a collection of items and it is very important to check for the existence (SISMEMBER) or size of the collection (SCARD) in a very fast way. Set is your first choice. Another cool thing about sets is support for peeking (SRANDMEMBER) or popping random elements (SPOP).
O(1) operations:
O(N) operations:
O(…) operations:
- others: SINT
Use Case
Sets are good for expressing relations between objects. For instance, we can use sets in order to implement many-to-many relationships between posts and tags.
- Here are two problems that Redis set can answer easily:
- To get all the posts tagged by MySQL
> tag:MySQL:posts - To get all the posts tagged by multiple tags like MySQL, Java and Redis, we user
> SINTER tag:Java:posts tag:MySQL:posts tag:Redis:posts
Redis Hash
Redis Hashes are maps between string fields and string values, so they are the perfect data type to represent objects (e.g. A User with a number of fields like name, surname, age, and so forth):
Redis Hash Use Case
We can use Hash map to model a user from a SQL table
> HMSET user:139960061 login dr_josiah id 139960061 followers 176
OK> HGETALL user:139960061
1) "login"
2) "dr_josiah"
3) "id"
4) "139960061"
5) "followers"
6) "176"> HINCRBY user:139960061 followers 1
"177"
Redis Sorted Sets
Redis Sorted Sets are, similarly to Redis Sets, non-repeating collections of Strings. The difference is that every member of a Sorted Set is associated with a score, that is used in order to take the sorted set ordered, from the smallest to the greatest score.
With sorted sets you can add, remove, or update elements in a very fast way (in a time proportional to the logarithm of the number of elements). Since elements are taken in order and not ordered afterwards, you can also get ranges by score or by rank (position) in a very fast way. Accessing the middle of a sorted set is also very fast, so you can use Sorted Sets as a smart list of non repeating elements where you can quickly access everything you need: elements in order, fast existence test, fast access to elements in the middle!
- O(1) operations:
- others: ZCARD
- O(log(N)) operations:
- create: ZADD
- delete: ZREM , ZPOPMAX
- retrieve: ZRANGE , ZRANK
Redis Sorted Set Use Case
Many Q&A platforms like Stack Overflow and Quora use Redis Sorted Sets to rank the highest voted answers for each proposed question to ensure the best quality content is listed at the top of the page.
Comparison
Let's compare the three data structure in a table.
+-----------+--------------------+---------------+---------------
| structure | allow duplicate | is sorted | user case |
+-----------+--------------------+---------------+---------------
| list | YES | YES | news feed |
| set | NO | NO | tags |
| sorted set| NO | YES | scoreboard |
+-----------+--------------------+---------------+--------------+
