All data structures in Redis are key-value, and the key string is unique. The difference between different data structures is that the value structure is different. Let’s look at the basic data types in Redis

  • Redis basic data structure
  • String (string)
  • The list (list)
  • Set (set)
  • Zset (Ordered set)
  • Hash (hash)

string

Redis is a dynamic string that can be modified. The internal structure implements ArrayList, which dynamically expands and preallocates redundant space to reduce frequent memory allocation. More than the actual string length is typically allocated.

Capacity expansion mechanism: If the character string is smaller than 1 MB, the existing space is doubled. If the character string exceeds 1 MB, only 1 MB is added each time. The maximum character string capacity is 512 MB

Common application scenarios: Cache user information, which is serialized into A JSON string and stored in Redis cache, and then deserialized into the required user information.

Operation (on the Redis client) : key-value pair Command: Save value: set key name Value value: get key name

Command: Save value: mset Key name 1 v1 Key name 2 v2… Value: mget Key name 1 Key name 2

Expire and set command expire command: expire key name timeout Default expiration practice unit is second atomic storage + expiration: set key name timeout value value

Setnx: setnx: setnx: setnx: setnx: setnx: setnx: setnx

Incr key name incrby key name step (decrement if negative)

List (list)

The list structure of Redis is linked list, insert and delete, and the time complexity is O(1). The time complexity of index positioning is O(n).

And when the list pops up an element, the data structure is deleted and the memory is reclaimed

Usage scenario: Asynchronous queuing is often used with a left-in, right-out data structure. Tasks that need to be deferred are pushed into a Redis list, from which another thread polls data for processing

Rpush: rpush key name v1 v2… View length: llen Books Retrieve data: LPOP Books

Rpush: v1, v2… Pull out the data: RPOP Books

Ltrim Key name Start End Retain the values in the start-end range. You can use ltrim to create a list with a fixed length. If index is negative, -1 is the last value, and so on

Quick linked list Redis list at the bottom of a QuickList structure with fewer elements: continuous memory storage structure: Ziplist compressed list with more data: Combine the linked list and Ziplist to form a Quicklist, and connect multiple Ziplists with bidirectional Pointers. Advantages: Hanging two Pointers to each element wastes space and increases memory fragmentation

Hash (dictionary)

Redis hash is the Java equivalent of HashMap, an unordered dictionary

Internal structure implementation: data plus linked list

When the array of the first hash is collided, the elements are linked together

Comparison with Java HashMap: The dictionary value of Redis can only be string. The rehash method is different from that of Java HashMap. When the dictionary is very large, rehash is a time-consuming operation, requiring all rehash at one time.

Progressive rehash: The old and new hash structures are retained in the rehash. The two hash structures are queried at the same time, and then the old hash is gradually migrated to the new hash structure in subsequent scheduled tasks and hash operation instructions. When the relocation is complete, the new hash structure takes over

After the hash removes the last element, the data structure is automatically deleted and the memory is reclaimed

The hash structure can also be used to store user information. String stores user information by serializing the entire object. Each field of the hash structure can be stored separately.

Disadvantages of hash: The storage cost of hash is higher than that of a string

Command: Setting value: hset Key name Property Property Value: hGEtall key name #entries(), hGET key name Property name (take specific property values) Length: hlen key name

The value of a hash attribute is similar to that of string. You can increment the value automatically. Hincrby Key name Attribute Name Step Incr Key name Attribute name

Set

The collection of Redis is analogous to the Java HashSet, whose internal key-value pairs are unordered and unique

Internal implementation: special dictionary, each value of the dictionary is NULL

When the last element in the collection is removed, the data structure is automatically deleted and the memory is reclaimed

Usage scenario (de-duplication) : The user who wins the lottery is saved. By de-duplication, the user cannot win the lottery twice

Value: sadd key name value (multiple values) Value: smembers Key name Spop key name Whether a value exists: sismember key name Value Length: scard key name

Zset (Ordered set)

The unique data structure of Redis is similar to the combination of SortedSet and HashMap in Java. Set ensures the uniqueness of value, and Score represents the weight of value and is sorted according to this weight

Internal implementation: skip list

After the last value of the zset is removed, the data structure is deleted and the memory is reclaimed

Application scenario (ranking related) : Fan list: value indicates ID, score indicates attention time Student transcript: value indicates ID, score indicates score

Command setting value: zadd Key name weight value Listed by weight: zrange key name start end (start end indicates the sorting range. 0-1 indicates all types.) zrevrange key name start end Length in reverse order: Score: zscore key name value Displays the rank of a value. Zrank Key name value Displays the value of a weight range. Zrangebyscore key name start end (start end indicates the weight range) zrangebyscore key name -inf end withscores (-∞ to end, and return the weight) delete: zrem key name value

Jump lists

Zset internal implementation: Hash + jump list

A simple list to find elements of time complexity is O (N), even if the elements in the singly linked lists are ordered, and array can use binary search method to find the elements, in the face of an orderly, to find the time complexity of O (logn), and in order to let the chain table lookup efficiency faster, has emerged can “binary search” list: jump list.

Skip lists are ordered data structures in which each node maintains multiple Pointers to other nodes for quick lookups.

When zset in Redis contains a large number of elements, or element members are long strings, the advantages of skip lists are obvious

Skip lists can be understood as multi-layer lists

  • The structure consists of several layers, each of which is an ordered linked list
  • The lowest level (level 1) list contains all the elements
  • The search times of skip list are approximate to the number of layers, and the time complexity is O(logn). Insert and delete are also O(logn).
  • Skip lists are randomised data structures (layers determined by flipping a coin)
  • The space complexity of skip lists is order logn.

How do you make ordered list lookups faster? Because the elements are in order, we can add more paths to speed up the search. Path: An ordered list with one more layer decides whether to proceed to the next layer by comparing the elements of the previous layer with the elements of the search (binary search).

How do you maintain this list? Insert and delete When you insert or delete, the node tree of the skip table changes, meaning that the number of layers of the skip table changes dynamically

How many layers should the newly inserted element span? Take strategy: flip a coin, insert a node of a layer, flip the coin once, if the condition is not met, count the number of times, this number is the number of layers of newly inserted elements.

How do you delete an element by simply deleting it across the domain hierarchy

Skip list vs binary search tree Search, add, delete binary search tree is also approximately O(logn), but there is an extreme case, when the data is ordered, it is a layer of ordered linked list, the search, add, delete complexity becomes O(n)

When a red-black tree adds or deletes nodes, the structure of the red-black tree is adjusted to keep the balance of the red-black tree, while the leapfrog determines the cross-domain level through a random number. Therefore, the maintenance cost of the red-black tree is higher when adding or deleting nodes

General rules for container-type data structures

List /set/zset/hash

1. Create if not exists If the container is not already created, create a new one

Dorp if no elements if there are no elements in the container, the data structure of the container is deleted to free the memory

Expiration time

All of Redis’s underlying data structures can be set to expire at the object dimension. Redis automatically deletes the corresponding object after expiration, not an element value in the object.

For string specificity: when you set an expiration time to a string and then modify the string, the expiration time disappears