Redis underlying data structure ----quicklist

quickList Introduce

stay redis3.0 before ,List The underlying data structure of an object is Double linked list perhaps Compress the list stay 3.2 When ,List The bottom layer of the object is changed to quicklist Data structure implementation .
quickList Linked list is Double linked list + Compress the list Combine ,quicklist It's a linked list , The elements in the linked list are compressed lists .

quicklist Data structure of

typedef struct quicklist {
    
    //quicklist The chain head of 
    quicklistNode *head;      
    //quicklist The end of the list 
    quicklistNode *tail; 
    // Total number of elements in all compressed lists 
    unsigned long count;
    // The number of nodes in the list  quicklistNode
    unsigned long len;       
    ...
} quicklist;

quicklistNode Structure definition of

typedef struct quicklistNode {
    
    // Pointer to the previous node 
    struct quicklistNode *prev;     // Previous quicklistNode
    // Pointer to the back node 
    struct quicklistNode *next;     // After a quicklistNode
    //quicklistNode Compressed list pointing to 
    unsigned char *zl;              
    // The byte size of the compressed list 
    unsigned int sz;                
    // Number of elements in the compressed list 
    unsigned int count : 16;        //ziplist The number of elements in  
    ....
} quicklistNode;

You can see node Nodes have pointers to forward and back nodes , And the element of the node does not store the simple element value , Instead, a compressed linked list is saved , So there is a pointer to the compressed linked list *zl
Data structure chart

In the quicklist When adding an element , Not like an ordinary linked list , Directly create a linked list node . Instead, it will check whether the compressed linked list at the insertion position can accommodate the element , If it can accommodate , Then save it directly to quicklistNode Structure , If it can't hold , To create a new one Node structure .
quicklist Can control quicklistNode The size of the compressed list or the number of elements in the structure , To avoid the risk of potential chain updates , But it has not been completely lifted .