Redis- Hash objects

There are two types of data structures underlying hash, one is ziplist, the other is Hashtable. We have explained both of these two data structures before. Ziplist is the structure mentioned above, and Hashtable is the redis structure explained before. To use ziplist code:

• The hash object holds both key and value strings of less than 64 bytes
• The hash object can store less than 512 key/value pairs. The ziplist storage structure is as follows

As can be seen from the figure above, when the amount of data is relatively small, all keys and values will be stored in Ziplist as one element in order to form an order.

The structure of a HashTable store

What is the difference between a set key value of a string and a hash

1. Expiration time. Hash has no expiration time
2. There is a problem with the constant increment of set. One attribute in dict is Dictht HT [2], which is mainly used for > expansion. If key is continuously added, the overall redis memory needs to be expanded, and the expansion needs to be doubled based on the original memory, resulting in large memory consumption

Redis- Collection object (Set)

A set is an unordered, automatic deduplication set data type. The underlying data structure of a set is stored in two types of data, one is hashTable, the other is inset.

The key of the hashtable is the value of the element in the set, and the value is null

Inset can be understood as an array. The following two conditions must be met to use an inset data structure:

• The number of elements must be at least 512

  set-max-inset-entries 512

Copy the code

• Elements can be represented as integers

The underlying structure of intSet

typedef struct intset {

    

    // Encoding type

    uint32_t encoding;



    // The number of elements the collection contains

    uint32_t length;



    // Hold an array of elements

    int8_t contents[];



} intset;

Copy the code

Binary search is usually used to query, and the actual query complexity is log(n).

Redis- Ordered Set Object (Zset)

Zset is an ordered (finite score sort, element lexicographic order if score is the same), automatically deduplicated set data type, and its underlying implementation is dict + skiplist. When data is relatively small, it is stored with Ziplist coding structure.

Ziplist storage is used when the following two conditions are met:

• The ordered collection holds less than the default 128 elements
• Ordered collections hold all elements shorter than the default 64 bytes

Ziplist storage mode

When Ziplist was used as the underlying storage structure for Zset, each collection element was stored in two compressed list nodes next to each other, the first node holding the element’s members and the second element holding the element’s score

Dict + skiplist storage

The underlying storage structure of zset includes ziplist or skiplist. Ziplist is used when the following conditions are met, and skiplist is used when the following conditions are met:

Ordered sets hold less than the number of elements 128 ordered sets hold less than 64 bytes of all elements

The data structure of the hop table

First of all, what is a skip watchAs you can see, we improve efficiency by ranking from the highest level to the lowest level, with logn time complexity (similar to binary lookup).

Dict + Skiplist’s final storage structure is as follows

Let’s take a look at the data structures of several key skiplist objects based on the figure above

zset

  / *

* Ordered set

* /

typedef struct zset {



    // dictionary, keys are members, values are points

    // This is used to support O(1) complexity

    dict *dict;



    // Skip list, sort members by point value

    // Used to support the O(log N) average complexity of locating members by point value operations

    // And scope operations

    zskiplist *zsl;



} zset;

Copy the code

It can be seen that the first is a dict structure, where the main key is the set element, and the value is the corresponding score value. Zkiplist acts as a skip list, sorting by score value to locate members conveniently

zskiplist

  / *

* jump table

* /

typedef struct zskiplist {



    // Table header and table tail nodes

    struct zskiplistNode *header, *tail;



    // The number of nodes in the table

    unsigned long length;



    // The number of layers of the node with the largest middle level in the table

    int level;



} zskiplist;

Copy the code

zskiplistNode

  / *

* Skip list nodes

* /

typedef struct zskiplistNode {



    // Member objects

    robj *obj;



    / / score

    double score;



    // Back up the pointer

    struct zskiplistNode *backward;



    / / layer

    struct zskiplistLevel {



        // Forward pointer

        struct zskiplistNode *forward;



        / / span

        unsigned int span;



    } level[];



} zskiplistNode;

Copy the code

The robj pointer in zskiplistNode points to a specific element. Note that this pointer points to the same element as the key pointer in the dict, where a backward hind pointer is convenient for backtracking

conclusion

This section mainly explains the basic principles of hash, set and zset in Redis. There are two types of hash, namely ziplist and hashtable, and two types of hashtable and inset, respectively, are used inset. Inset can also be understood as an array. Zset base is ziplist and Dict + Skiplist respectively, we can see in saving memory, improve query efficiency reflected in the excellent design, these can be our future design and development of valuable experience, the next section we will lead you to learn Redis in data security and performance assurance features, class!