1, the introduction of

All data structures in Redis use a unique string key to obtain the corresponding value data. Redis has five basic data structures, which are:

  • String (string)
  • List (list)
  • Hash (dictionary)
  • Set
  • Zset (Ordered set)

List, set, Hash, and zset are container data structures that share the following two general rules:

  • Create if not exists: Creates a container if it does not exist
  • Drop if no elements: If there are no elements in the container, the container is immediately dropped to free the memory

This article describes the list of the five basic data structures of Redis.

2. Introduction to list

2.1 Internal structure of a list

Redis’s list is the equivalent of the LinkedList in the Java language, which is a bidirectional LinkedList data structure (but a clever one, described below) that supports sequential traversal. Linked list structure inserts and deletes quickly, time complexity O(1), query slow, time complexity O(n). \

PNG structure diagram of list

2.2 Application Scenarios of list

Redis is also used for asynchronous queues due to the nature of two-way lists. In actual development, the task structure that needs to be deferred is serialized into a string and placed in the queue of Redis, and another thread retrieves data from the list for subsequent processing. The flow is similar to the figure below:

List is used for asynchronous queue schema.png


​

3. The list instruction

3.1 Right In and Left Out – Queue

Queues are FIFO data structures (such as the order of queuing for tickets) and are often used for similar functions of message queues, such as message queuing, asynchronous processing and other scenarios. This ensures the order in which elements are accessed. Lpush -> adds elements from the left side

Lpush key value [value…

Rpush -> adds elements from the right

Rpush key value [value…]

Llen -> Get the length of the list

llen key

Lpop -> Pop the element from the left

lpop key

127.0.0.1:6379> rpush code Java C Python # Add elements to the list (integer) 3 127.0.0.1:6379> llen code # Obtain the list length (integer) 3 127.0.0.1:6379> lPOP code "c" 127.0.0.1:6379> lpop code "python" 127.0.0.1:6379> llen code (integer) 0 127.0.0.1:6379> lPOP code (nil)Copy the code

3.2 Right in, Right out — stack

The stack is a first in, last out (FILO) data structure in structure (for example, when a cartridge is pressed into a bullet, the order in which the bullets are fired is the stack), and this data structure is generally used for reverse output. Lpush -> adds elements from the left side

Lpush key value [value…

Rpush -> adds elements from the right

Rpush key value [value…]

Rpop -> Pop the element from the right

rpop code

127.0.0.1:6379> rpush code Java C Python (integer) 3 127.0.0.1:6379> rPOP code # Pop the last added element "python" 127.0.0.1:6379> rPOP Code "c" 127.0.0.1:6379> rpop code "Java" 127.0.0.1:6379> rpop code (nil)Copy the code

3.3 slow operation

List is a linked list data structure, and its traversal is a slow operation, so the traversal performance will increase with the increase of traversal range. Note that the list index runs negative, -1 for the first to last index, -2 for the second to last index, and so on. Lindex -> iterate to get the value at the specified index of the list

lindex key ind

Lrange -> get all values from index start to stop

lrange key start stop

Ltrim -> truncate all values from start to stop, other values will be deleted

ltrim key start stop

127.0.0.1:6379> rpush code Java c python (integer) 3 127.0.0.1:6379> lindex code 0 "Java" 127.0.0.1:6379> 127.0.0.1:6379> lindex code 1 # fetch data from index 1 "c" 127.0.0.1:6379> lindex code 2 # fetch data from index 2 "python" 127.0.0.1:6379> lrange code 0-1 # fetch data from index 1 "c" 127.0.0.1:6379> lrange code 0-1 127.0.0.1:6379> ltrim code 0-1 # truncate and factoring data from 0 to -1 == factoring all data from 0 to -1 127.0.0.1:6379> lrange code 0 -1 1) "Java" 2) "c" 3) "python" 127.0.0.1:6379> ltrim code 1 -1 Java OK 127.0.0.1:6379> lrange code 0-1 1) "c" 2) "python"Copy the code

4. List in depth

The Redis underlying store list is not a simple LinkedList, but a quicklist — a “quicklist.” Quicklist is a quicklist, and I’m still learning about it. Quicklist is a bidirectional list of ziplists; And what is this ziplist? Ziplist refers to a contiguous memory storage space. Redis uses contiguous memory for list storage when the number of elements is small. This reduces the memory consumption caused by adding prev and next Pointers to each element, and most importantly, reduces memory fragmentation.

4.1 Schematic diagram of common linked list structure

Each node element holds a prev-> pointer to the previous node and a next-> pointer to the next node (reference). This structure supports sequential traversal, but it also carries a large memory overhead. A larger percentage of memory will be referenced. \

Common linked list structure.png

4.2 Ziplist schematic diagram

A ziplist is a contiguous block of memory addresses that can be accessed through address order without holding prev and next Pointers between them. \

Ziplist memory diagram. PNG

4.3 QuickList Schematic diagram

Quicklist is a bidirectional linked list composed of multiple Ziplists. \

Quicklist schematic. PNG