Redis data structure

One 、redis Data structure of

1、String String type

  Redis Of String Can represent string 、 Integers 、 Floating point numbers are three types of values

Application scenarios ：

1. Normal assignment
2. Use incr、decr Command to increment and decrement statistics . Used to implement optimistic locks watch( thing )
3. setNx Implement distributed locks

The underlying data type ：

//  data structure 
struct sdshdr{
    // Record buf The number of bytes used in an array 
    int len;
    // Record  buf  The number of unused bytes in an array 
    int free;
    // A character array , To hold strings 
    char buf[];
}

• int： When stored as int Integer of type
• embstr： Encode simple dynamic strings . The length of a single string is less than 44 Bytes
• raw： Simple dynamic strings , Big string , When the length is greater than 44 Bytes

2、List List the type

  list Can be used to store ordered and repeatable data , It can quickly obtain the head and tail data , Maximum storage 2^32-1 Elements .

Underlying data structure ：

1、LinkList： It's a two-way list , The structure of a two-way linked list includes a head node 、 Then each node has a head pointer to the previous element and a tail pointer to the next element .

2、zipList： Compress the list

Compressed linked list has a zitail_offset The last one was recorded entry The offset , In this way, you can quickly locate the last element of the linked list and start flashback traversal .zipList Of entry Data structure of ：

typede struct entry{
    // Previous entry The length of 
    int<var> prelen;
    // Element type encoding 
    int<var> encoding;
    // Element content 
    optional byte[] content;
}

Compressed linked list and common LinkList The difference between , Compressing a linked list is not about compressing elements , But the space of the linked list is allocated continuously ListList The allocated memory space is randomly allocated like this zipList Compared with LinkList There will be no fragmentation of memory . And because of zipList The space of is continuous, so it is reduced pre Pointers and next The pointer , Each pointer needs to occupy 8 Bytes , Missing two pointers reduces 16 Bytes .

  because zipList Is a continuous space , And there's no pre、next Pointer so deleting a new element requires a copy of the element , And chain update operation . So when there are few elements list use zipList Storage , Use when there are many elements ListList.

3、quickList

  quickList yes linkList and zipList The combination of ,linkList Every node of is a zipLit, When zipList It will be created when a certain amount of elements in linkList Of another node zipList.

Application scenarios ：

1. Can be used to implement stack
2. Can be used to block queues
3. Can be used for various lists , Such as user list 、 List of goods 、 Comment list, etc .

Reference resources ：Redis Of the underlying data structure list - The world is full of dreams - Blog Garden (cnblogs.com)

3、set Collection types

  set The collection type is used to store unordered and non repeating data

Underlying data structure ：

1、intset： When the type of storage is integer and the number of elements is less than set-max-intset-entries When you use intset Store the data ,intset It uses an array to store data .

2、dict Dictionaries ： When the stored data is not int type , Or the amount of data exceeds set-max-intset-entries Use a dictionary to store , Dictionary key Just the value of the data ,value be equal to null.

Application scenarios ：

1.   Used to save data that cannot be repeated and does not need sorting , For example, the user information concerned
2. Use spop Returns a random element in the set , And delete it 、srandmember Returning a random element in the set does not delete . These two commands are used to realize the random lottery function

4、sortset Ordered set type

  Store ordered and inconsistent data .sortset All elements in will be associated with one score Score and sort by score , Scores can be repeated .

Underlying data structure ：

1、ziplist： When the amount of data is small and the elements are small integers or short strings

2、skiplist： Skip list

Application scenarios ：

1. Realize the function of leaderboard

5、hash type

  Redis hash It's a string Type of field and value Mapping table , It provides the mapping of fields and field values .

Underlying data structure ：

1、ziplist： When the number of hash table elements is relatively small , And the elements are small integers or short strings .

2、dict： When the number of hash table elements is relatively large or the elements are not small integers or short strings .

Application scenarios ：

1. Object storage

6、bitmap type

Through one bit Bit to indicate the value or state of an element , Among them key It's the corresponding element itself .bitmap The main data is key、 Offset offset、 value , Where the value can only be 0 and 1. Greatly saved memory space

Application scenarios ：

1. Record employees' clock in records ：key For the date , The offset is the user id, The value is 0 Indicates that you did not punch in ,1 Indicates that you have clocked in . perhaps key For the user id, The offset is date , The value is 0 Indicates that you did not punch in ,1 Indicates that you have clocked in .