[redis notes] compressed list (ziplist)

Definition of compressed list ：

Compressed lists are developed to save memory , It is a sequential data structure composed of a series of special coded continuous memory blocks .

Structure of compressed list ：

Structure of compressed list nodes ：

 

 previous_entry_length: Record the length of the previous node in the compressed list

  according to previous_entry_length, The program can operate by pointer , Calculate the starting address of the previous node according to the starting address of the current node , So as to realize traversal from the end of the table to the header .

encoding:

Record node's content The type and length of data saved by attributes

 

 content:

Responsible for saving the value of the node , The node value can be an array of bytes or an integer , The type and length of the value are determined by the encoding Attribute decision .

Chain update ：

Add or remove nodes , If the length is greater than 254 byte , It may lead to previous_entry_length Size needs to be from 1 Bytes changed to 5 byte , This may cause subsequent nodes previous_entry_length Everything has changed , under these circumstances , Continuous space expansion operations are required .

explain ：

（1） The worst time complexity of space allocation O(N), The worst time complexity of chain update O(N Fang )

（2） The situation is rare and as long as the number of nodes is small , No impact on performance .