Redis has five basic data structures: String, list, Hash, set, and zset. They are the most widely used data structures in daily development, and if you know all five of them, you are about half the way to Redis.
string
Let’s start with string. String represents a mutable array of bytes, so we initialize the contents of the string, we get the length of the string, we get the substring, we overwrite the substring, we append the substring.
The string of Redis is a dynamic string that can be modified. Its internal structure is similar to That of ArrayList in Java, and it uses pre-allocation of redundant space to reduce frequent memory allocation. As shown in the figure, capacity is generally higher than len. If the string length is less than 1 MB, the existing space is doubled. If the string length is more than 1 MB, the existing space is expanded by 1 MB at a time. Note that the maximum length of the string is 512 MB.
Initialization strings need to provide “variable name” and “variable contents”
> set ireader beijing.zhangyue.keji.gufen.youxian.gongsi
OK
Copy the codeGet the content of the string provide “variable name”
> get ireader
"beijing.zhangyue.keji.gufen.youxian.gongsi"
Copy the codeGet the length of the string provide “variable name”
> strlen ireader
(integer) 42
Copy the codeGet substrings that provide “variable names” and start and end positions [start, end]
> getrange ireader 28 34
"youxian"
Copy the codeThe override substring provides the “variable name” as well as the starting position and the target substring
> setrange ireader 28 wooxian
(integer) 42 # return length
> get ireader
"beijing.zhangyue.keji.gufen.wooxian.gongsi"
Copy the codeAdditional substring
> append ireader .hao
(integer46),# return length
> get ireader
"beijing.zhangyue.keji.gufen.wooxian.gongsi.hao"
Copy the codeUnfortunately, strings do not provide string insertion and substring deletion.
Counter If the content of the string is an integer, you can also use the string as a counter.
> set ireader 42
OK
> get ireader
"42"
> incrby ireader 100
(integer) 142
> get ireader
"142"
> decrby ireader 100
(integer) 42
> get ireader
"42"
> incr ireader # equivalent to incrby iReader 1
(integer) 43
> decr ireader # equivalent to decrby iReader 1
(integer) 42
Copy the codeThe counter has a range. It cannot exceed long. Max and cannot be lower than long.min
> set ireader 9223372036854775807
OK
> incr ireader
(error) ERR increment or decrement would overflow
> set ireader -9223372036854775808
OK
> decr ireader
(error) ERR increment or decrement would overflow
Copy the codeExpired and deleted strings can be actively deleted using the DEL directive. Expired strings can be automatically deleted using the EXPIRE directive. This is passive deletion. You can use the TTL instruction to get the life of a string.
> expire ireader 60
(integer1)# 1 indicates success, and 0 indicates that the variable iReader does not exist
> ttl ireader
(integer) 50 Return -2 to indicate that the variable does not exist and -1 to indicate that no expiration time is set
> del ireader
(integer1)Delete successfully returns 1
> get ireader
(nil) # the variable ireader is gone
Copy the codelist
Redis names list data structures list rather than array because lists are stored in linked lists rather than arrays and because lists are bidirectional. Because it is a linked list, the random positioning performance is weak, and the head-to-tail insert and delete performance is better. If a list has a long list length, we must pay attention to the time complexity of linked list operations.
The positions of the negative subscript list elements use the natural numbers 0,1,2,…. N-1 means, you can also use negative numbers -1,-2… -n, -1 is the last to last, -2 is the second to last, so -n is the first element, and its subscript is 0.
Queue/stack lists can append and remove elements from the head and tail of the table, using a combination of rpush, RPOP, lpush, and LPOP instructions. Lists can be used as queues or stacks, either left or right
# Right in, left out
> rpush ireader go
(integer) 1
> rpush ireader java python
(integer) 3
> lpop ireader
"go"
> lpop ireader
"java"
> lpop ireader
"python"
# Left in right out
> lpush ireader go java python
(integer) 3
> rpop ireader
"go".# Right in, right out
> rpush ireader go java python
(integer) 3
> rpop ireader
"python".# Left in, left out
> lpush ireader go java python
(integer) 3
> lpop ireader
"python".Copy the codeIn everyday applications, lists are often used as asynchronous queues.
Length Use the llEN directive to get the length of the list
> rpush ireader go java python
(integer) 3
> llen ireader
(integer) 3
Copy the codeRandom reads can use the Lindex directive to access elements at specified positions, and the lrange directive to get a list of linked list child elements, providing start and end subscripts
> rpush ireader go java python
(integer) 3
> lindex ireader 1
"java"
> lrange ireader 0 2
1) "go"
2) "java"
3) "python"
> lrange ireader 0 -1 # -1 means last to last
1) "go"
2) "java"
3) "python"
Copy the codeIf you use lrange to obtain all elements, you need to provide end_index. If there is no negative subscript, you need to obtain the length of the llEN command first to obtain the value of end_index. If there is a negative subscript, use -1 instead of end_index to achieve the same effect.
Modify elements Use the lset directive to modify elements at the specified position.
> rpush ireader go java python
(integer) 3
> lset ireader 1 javascript
OK
> lrange ireader 0 -1
1) "go"
2) "javascript"
3) "python"
Copy the codeInsert elements Use the Linsert directive to insert elements in the middle of a list. Experienced programmers know that when inserting elements, it’s often unclear whether to insert before or after the specified position. So Antirez added the orientation parameters before/after to the linsert directive to indicate pre – and post-inserts. Surprisingly, linsert does not insert by specifying a location, but by specifying a value. This is because in a distributed environment, the elements of the list change frequently, meaning that the index of an element computed at one moment may not be the index you expect at the next moment.
> rpush ireader go java python
(integer) 3
> linsert ireader before java ruby
(integer) 4
> lrange ireader 0 -1
1) "go"
2) "ruby"
3) "java"
4) "python"
Copy the codeSo far, I have not found the application scenario specified to insert in the actual application.
Deleting a list of deleted elements is not done by specifying subscripts. You need to specify the maximum number of deleted elements and their values
> rpush ireader go java python
(integer) 3
> lrem ireader 1 java
(integer) 1
> lrange ireader 0 -1
1) "go"
2) "python"
Copy the codeFixed-length list In practical application scenarios, we sometimes encounter the requirement of “fixed-length list”. For example, if you want to display the list of winners in real time in the form of a revolving lamp, because there are too many winners, the number of winners can be displayed generally not more than 100, then the fixed-length list will be used here. The instruction for maintaining a fixed-length list is ltrim, which requires two arguments, start and end, to indicate that the subscript range of the list needs to be preserved. All elements outside the range are removed.
> rpush ireader go java python javascript ruby erlang rust cpp
(integer) 8
> ltrim ireader -3 -1
OK
> lrange ireader 0 -1
1) "erlang"
2) "rust"
3) "cpp"
Copy the codeIf the end of the specified argument corresponds to a true subscript less than start, the effect is equivalent to the del directive, because such an argument indicates that the subscript range of the list elements needs to be left blank.
A quick list
hash
Hash is equivalent to The Java language HashMap or the Python language dict. In terms of its implementation structure, it uses a two-dimensional structure. The first dimension is an array and the second dimension is a linked list. When searching for an element by key, the hashcode of the key is calculated first, and then the length of the array is modeled by hashcode to locate the header of the linked list, and then the linked list is traversed to obtain the corresponding value value. The function of the linked list is to string the elements that generate “hash collision”. Java language developers will be very familiar with this structure because it is no different from a HashMap. The length of the first dimension of the hash array is also 2 to the n.
Elements can be added one keyvalue pair at a time using hset or multiple keyvalue pairs at a time using hmset
> hset ireader go fast
(integer) 1
> hmset ireader java fast python slow
OK
Copy the codeFor obtaining elements, hget can be used to locate the value corresponding to a specific key, hmGET can be used to obtain the value corresponding to multiple keys, hgetall can be used to obtain all key-value pairs, and hkeys and HVALS can be used to obtain all key lists and value lists respectively. These operations are similar to the Java language’s Map interface.
> hmset ireader go fast java fast python slow
OK
> hget ireader go
"fast"
> hmget ireader go python
1) "fast"
2) "slow"
> hgetall ireader
1) "go"
2) "fast"
3) "java"
4) "fast"
5) "python"
6) "slow"
> hkeys ireader
1) "go"
2) "java"
3) "python"
> hvals ireader
1) "fast"
2) "fast"
3) "slow"
Copy the codeTo delete an element, you can use hdel to delete a specified key. Hdel supports simultaneous deletion of multiple keys
> hmset ireader go fast java fast python slow
OK
> hdel ireader go
(integer) 1
> hdel ireader java python
(integer2)Copy the codeGenerally, we use hget to determine whether the value corresponding to the key is empty until the corresponding element exists. However, if the string length of the value is extremely large, it would be a waste to determine whether the element exists in this way. In this case, we can use the hEXISTS instruction.
> hmset ireader go fast java fast python slow
OK
> hexists ireader go
(integer1)Copy the codeThe counter hash structure can also be used as a counter, acting as a separate counter for each internal key. If value is not an integer, the hincrby directive will fail to be called.
> hincrby ireader go 1
(integer) 1
> hincrby ireader python 4
(integer) 4
> hincrby ireader java 4
(integer) 4
> hgetall ireader
1) "go"
2) "1"
3) "python"
4) "4"
5) "java"
6) "4"
> hset ireader rust good
(integer) 1
> hincrby ireader rust 1
(error) ERR hash value is not an integer
Copy the codeCapacity expansion If hash elements are crowded (hash collisions are frequent), capacity expansion is required. To expand, you need to apply for a new array twice the size, and then rehash all the key-value pairs into a linked list (rehash) corresponding to the new array subscripts. If the hash structure is large, such as millions of key-value pairs, a full rehash process can take a long time. This can be a bit stressful in single-threaded Redis. So Redis uses a progressive Rehash scheme. It retains both the old and new hash structures, gradually migrating elements of the old structure into the new structure during subsequent scheduled tasks and read/write instructions to the hash structure. In this way, thread lag caused by capacity expansion can be avoided.
Redis’s hash structure expands as well as shrinks, and in this respect it is more powerful than Java’s HashMap, which only expands. The principle of scaling down is the same as scaling up, except that the new array is twice the size of the old one.
set
Java programmers know that the internal implementation of a HashSet uses a HashMap, except that all the values point to the same object. The same is true of Redis’s set structure, which also uses a hash structure internally, with all values pointing to the same internal value.
Adding elements You can add more than one element at a time
> sadd ireader go java python
(integer) 3
Copy the codeTo read elements, use smembers to list all elements, scard to get the length of the collection, and srandMember to get a random count of elements. If no count argument is provided, the default is 1
> sadd ireader go java python
(integer) 3
> smembers ireader
1) "java"
2) "python"
3) "go"
> scard ireader
(integer) 3
> srandmember ireader
"java"
Copy the codeRemove elements Use SREM to remove one to more elements, and use SPOP to remove a random element
> sadd ireader go java python rust erlang
(integer) 5
> srem ireader go java
(integer) 2
> spop ireader
"erlang"
Copy the codeChecking the presence of an element uses the sismember directive, which accepts only a single element
> sadd ireader go java python rust erlang
(integer) 5
> sismember ireader rust
(integer) 1
> sismember ireader javascript
(integer) 0
Copy the codesortedset
SortedSet(Zset) is a very special data structure provided by Redis. On the one hand, it is equivalent to the Java data structure Map
, which can assign a weight score to each element value. On the other hand, it is similar to TreeSet. Internal elements will be sorted according to the weight score, the ranking of each element can be obtained, and the list of elements can be obtained through the range of score.
The underlying implementation of ZSET uses two data structures, the first is hash and the second is skip list. The function of hash is to associate element value and weight score to ensure the uniqueness of element value. The corresponding score value can be found through element value. The purpose of the skip list is to sort the element value and get the list of elements according to the range of score.
Add elements The Zadd command allows you to add one or more value/score pairs, with score first
> zadd ireader 4.0 python
(integer1 > Zadd iReader 4.0 Java 1.0 go (integer2)Copy the codeLength The number of elements in zset can be obtained by the command zcard
> zcard ireader
(integer) 3
Copy the codeDeleting elements The zrem directive deletes elements in a Zset, more than one at a time
> zrem ireader go python
(integer2)Copy the codeCounters like hash structures, zsets can also be used as counters.
> zadd ireader 4.0 python 4.0 java 1.0 go
(integer) 3
> zincrby ireader 1.0 python
"5"
Copy the codeThe zscore command gets the weight of the specified element, the zrank command gets the forward rank of the specified element, and the zrevrank command gets the backward rank of the specified element. Positive is from small to large, negative is from large to small.
> zscore ireader python
"5"
> zrank ireader go # Lower rank = lower rank = lower rank
(integer) 0
> zrank ireader java
(integer) 1
> zrank ireader python
(integer) 2
> zrevrank ireader python
(integer) 0
Copy the codeThe corresponding element list can be obtained by specifying the ranking range parameter of zrange instruction, and the weight of the element can be obtained along with the withscores parameter. Get the list of elements by negative ranking using the Zrevrange directive. Positive is from small to large, negative is from large to small.
> zrange ireader 0 -1 Get all elements
1) "go"
2) "java"
3) "python"
> zrange ireader 0 -1 withscores
1) "go"
2) "1"
3) "java"
4) "4"
5) "python"
6) "5"
> zrevrange ireader 0 -1 withscores
1) "python"
2) "5"
3) "java"
4) "4"
5) "go"
6) "1"
Copy the codeObtain the list of elements by specifying the score range with the ZrangebyScore command. Get the list of inverted elements with the ZRevRangebyScore command. Positive is from small to large, negative is from large to small. The -INF argument indicates negative infinity and + INF indicates positive infinity.
> zrangebyscore ireader 0 5
1) "go"
2) "java"
3) "python"
> zrangebyscore ireader -inf +inf withscores
1) "go"
2) "1"
3) "java"
4) "4"
5) "python"
6) "5"
> zrevrangebyscore ireader +inf -inf withscores # Notice that the positive and negative are reversed
1) "python"
2) "5"
3) "java"
4) "4"
5) "go"
6) "1"
Copy the codeThe list of elements to remove by range can be either a ranked range or a score range to remove multiple elements at once
> zremrangebyrank ireader 0 1
(integer2)# delete 2 elements
> zadd ireader 4.0 java 1.0 go
(integer) 2
> zremrangebyscore ireader -inf 4
(integer) 2
> zrange ireader 0 -1
1) "python"
Copy the codeSkip list The sorting function inside Zset is implemented through the “skip list” data structure, which is very special and complex. This section should be prepared for in-depth readers.
Because zset is intended to support random inserts and deletions, it is not easy to represent using arrays. Let’s start with a normal linked list structure.
We need this list to sort by score. This means that when new elements need to be inserted, you need to locate the insertion point at a specific location so that the list can continue to be ordered. Binary search is usually used to find insertion points, but binary search objects must be arrays, only arrays can support fast location, linked lists can not do that, so what to do?
Think of a startup that starts with just a few people, everyone on the team is equal, all co-founders. As the company grows and the number of people increases, the cost of team communication increases. At this point, the team leader system will be introduced to divide the team. Each team will have a leader. When the meeting is divided into teams, several leaders will have their own meeting arrangements. As the company grew larger, it needed to add another level — departments, each of which would elect a representative from the group leader list as the head of the company. Ministers will also have their own high-level meetings.
Skip lists are similar to this hierarchy, with all the elements at the bottom being strung together. It then picks out a representation every few elements and strings together the representation using another level pointer. And then from those delegates, we pick the second-level delegates, and we string them together. The result is a pyramid structure.
Think of your hometown on the map of the world: Asia -> China -> Anhui Province -> Anqing city -> Chongyang County -> Tanggou Town -> Field village -> XXXX, also a similar structure.
Skip lists are “jumpy” because internal elements, such as the one in the middle, can “jump” between layers L0, L1 and L2 quickly.
To locate the insertion point, first locate the insertion point on the top layer, then dive to the next level to locate the insertion point, and then dive to the bottom layer to find the appropriate location and insert the new element. How, you may ask, does the newly inserted element have a chance to do more than one job?
The jump list uses a random strategy to determine which tier new elements can be added to. L0 has a 100% chance, L1 has a 50% chance, L2 has a 25% chance, L3 has a 12.5% chance, all the way up to L31. Most elements don’t make it past several layers, and very few make it to the top. The more elements in the list, the more levels you can go down, and the more likely you are to make it to the top.
That’s fair enough. It’s luck, not dad, that gets you to the center.
Check out the official account “Mudong” on wechat to read more exciting articles