Remember to like + follow yo.

preface

Redis has five basic data types, but do you know the underlying implementation of these five data types? In order to get Sorted, we need to start with the following basic data structures: simple dynamic strings (SDS), linked lists, dictionaries, skip lists, integer sets, and compressed lists. They are a fundamental part of the Redis data structure.

Five data structure underlying implementation

1. String

• If a string object holds an integer value that can be represented as long, the string object stores the integer value in the PTR property of the string object structure (converting void* to long) and sets the encoding of the string object to int.
• If the string object holds a string value and the string value is longer than 39 bytes, the string object holds the string value using a simple dynamic string (SDS) and sets the encoding of the object to RAW.
• If the string object holds a string value that is less than or equal to 39 bytes long, the string object will use embSTR encoding to hold the string value.

2. List

• List objects can be encoded as ziplist or LinkedList.
• The list object holds all string elements less than 64 bytes in length and less than 512 in ziplist encoding; Otherwise use linkedList;

3. Hash

• Hash objects can be encoded ziplist or Hashtable.
• The key and value string length of all key-value pairs stored in the hash object is less than 64 bytes and the number of key-value pairs saved is less than 512, using ziplist encoding; Otherwise, use hashtable;

4. Set

• The encoding of a collection object can be intSet or HashTable.
• All elements of the collection object are integer values and the number of stored elements is not more than 512, using intSet encoding; Otherwise, use hashtable;

5. Sorted Set

• The encoding for ordered collections can be ziplist or Skiplist
• The ordered collection holds less than 128 elements and all the stored element members are less than 64 bytes in length. Using Ziplist coding; Otherwise use Skiplist;

Let’s talk about each of these underlying data structures.

Simple Dynamic String (SDS)

Redis itself built an abstract type called Simple Dynamic String (SDS) and used SDS as the default string representation of Redis. Such as:

 set msg "hello world"  
Copy the code

Both key and value are realized by SDS. Structure of SDS:

Struct SDSHDR {// Record the number of bytes used in the buF array // is equal to the length of the string held by the SDS int len; // Record the number of unused bytes in the buF array. // A byte array to hold the string char buf[]; };Copy the code

• The value of the free property is 0, which means that this SDS has not allocated any unused space.
• The len attribute has a value of 5, which means that the SDS holds a five-byte string.
• The buf property is an array of type char. The first five bytes of the array hold ‘R’, ‘e’, ‘d’, ‘I’, and ‘s’ respectively. The last byte holds the null character ‘\0’.

SDS and C language string is similar, but has more advantages: 1. SDS to obtain the length of string time complexity O(1) : because SDS through len field to store the length, when using directly read can be; C language to obtain the length of the string requires traversing the entire string, time complexity O(N). 2. SDS can prevent buffer overflow: when SDS API needs to modify SDS, it will first check whether SDS space is enough. If not, SDS will automatically expand, So buffer overflow will not be caused. The C language does not have this function. 3. SDS can reduce the number of memory reallocation times when modifying strings: – Space pre-allocation: When SDS expands, it not only increases the required space size, but also allocates some unused space. The rules of allocation are as follows: if the length of SDS after allocation is less than 1MB, then the unused space equal to the size of SDS after allocation will be allocated. Simply put, after SDS dynamic allocation is 16KB, 16KB more unused space will be allocated. If less than 1MB, 1MB of unused space is allocated for a long time. – Lazy space free: Lazy space free is used to optimize the string shortening operation of SDS: when the SDS API needs to shorten the string saved by SDS, it does not immediately reallocate memory to reclaim the extra bytes, but instead uses free to record unused space.

Second, the linked list

The linked list provides efficient node rearrangement and sequential node access, and the length of the linked list can be flexibly adjusted by adding and deleting nodes. Linked List is widely used in Redis. For example, the linked List is one of the bottom implementation of List. When a List contains a large number of elements, or the elements in the List are long strings, Redis will use the linked List as the bottom implementation of List. In addition to being used as the underlying implementation of lists, linked lists are also used for publishing and subscribing, slow queries, monitors, etc. The Redis server itself also uses linked lists to store the status information of multiple clients and to build client-side output buffers. Each linked listNode is represented using an adlist.h/listNode structure:

Typedef struct listNode {// struct listNode *prev; Struct listNode *next; Void *value; } listNode;Copy the code

Multiple ListNodes can form a double-ended list using prev and next Pointers, as shown in the figure below.While it is possible to use only multiple listNode structures to form lists, it is much easier to use adlist.h/list to hold lists:

Typedef struct list {// listNode *head; // listNode *tail; Unsigned long len; Void *(*dup)(void * PTR); Void (*free)(void * PTR); Int (*match)(void * PTR, void *key); } list;Copy the code

The list structure provides the head pointer, tail pointer, and len length counter for the list, while the dUP, free, and match members are the type-specific functions needed to implement polymorphic lists:

• The dUP function is used to copy the values stored by the linked list node.
• The free function frees the value held by the linked list node;
• The match function is used to compare the value held by the linked list node to another input value.

Here is a list with a single list structure and three ListNodes: The features of Redis’s linked list implementation can be summarized as follows:

• Double-ended: Linked list nodes have prev and next Pointers, and the complexity of obtaining the pre-node and post-node of a node is O(1).
• Acyclic: The prev pointer on the head node and the next pointer on the tail node point to NULL, and access to the linked list ends at NULL.
• With head and tail Pointers: Through the head and tail Pointers of the list structure, the complexity of the program to obtain the head and tail nodes of the linked list is O(1).
• List length counter: The program uses the len attribute of the list structure to count the list nodes held by the list. The complexity of obtaining the number of nodes in the list is O(1).
• Polymorphic: Linked list nodes use void* Pointers to hold node values, and you can set type-specific functions for node values through the DUP, free, and match attributes of the list structure, so linked lists can be used to hold various types of values.

Third, the dictionary

A dictionary, also known as a Symbol table, associative array, or map, is an abstract data structure used to hold key-value pairs. Key is unique. Java-like Map. Dictionaries are mainly used in Redis for:

• The bottom layer of Redis database is implemented with a dictionary. The operation of adding, deleting, modifying and checking the database is built on the operation of the dictionary, such as:

> set msg "hello world"
OK
Copy the code

Create a key-value pair with key “MSG” and value “hello world” in the dictionary representing the database.

• Dictionaries are also one of the underlying implementations of hash keys: Redis uses dictionaries as the underlying implementation of hash keys when a hash key contains many key-value comparisons, or when the elements in key-value pairs are long strings.

Redis dictionary uses hash table as the underlying implementation, a hash table can have multiple hash table nodes, and each hash table node stores a key value pair in the dictionary. The next three sections introduce Redis hash tables, hash table nodes, and dictionary implementations respectively.

Hash table

The hash tables used by the Redis dictionary are defined by the dict.h/dictht structure:

Typedef struct dictht {// dictEntry **table; // Hash table size unsigned long size; // Always equal to size-1 unsigned long sizemask; // The number of existing nodes in the hash table unsigned long used; } dictht;Copy the code

The table property is an array in which each element is a pointer to dict.h/dictEntry structures, each of which holds a key-value pair.

The size property records the size of the hash table, which is the size of the table array, while the Used property records the number of nodes (key-value pairs) that the hash table currently has.

The sizemask attribute always equals size-1. This attribute, along with the hash value, determines which index of the table array a key should be placed on.

The following figure shows an empty hash table of size 4 (without any key-value pairs).

Hash node

Hash table nodes are represented by dictEntry structures, each of which holds a key-value pair:

Typedef struct dictEntry {// key void *key; // value union {void *val; uint64_t u64; int64_t s64; } v; Struct dictEntry *next; struct dictEntry *next; } dictEntry;Copy the code

The key property holds the keys in the key-value pair, while the V property holds the values in the key-value pair, which can be a pointer, a Uint64_t integer, or an Int64_t integer.

The next property is a pointer to another hash table node that can concatenate multiple key-value pairs of the same hash value at once to solve the collision problem.

For example, the figure below shows how two keys k1 and k0 with the same index value can be joined together using the next pointer.

The dictionary

Dictionaries in Redis are represented by dict.h/dict structures:

Typedef struct dict {// type specific function dictType *type; // Private data void * privData; // Dictht ht[2]; // Rehash index // If rehash is not in progress, the value is -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */ } dict;Copy the code

The type and privData attributes are set for creating polymorphic dictionaries for different types of key-value pairs:

• The Type attribute is a pointer to the dictType structure. Each dictType structure preserves a cluster of functions for manipulating key value pairs of a specific type. Redis will set different type-specific functions for dictionaries with different uses.
• The privData attribute holds the optional parameters that need to be passed to those type-specific functions.

The HT attribute is an array of two items, each item in the array is a Dictht hash table. In general, dictionaries only use ht[0] hash tables, and HT [1] hash tables are only used for rehashing HT [0] hash tables.

In addition to HT [1], another attribute related to rehash is rehashidx: It records the current progress of the rehash and has a value of -1 if no rehash is currently in progress.

The following figure shows a dictionary in its normal state (without rehash) :

The hash algorithm

When a new key-value pair is inserted into a dictionary, the index value needs to be computed. Redis calculates the index value by:

Hash = dict->type->hashFunction(key); Ht [x] can be HT [0] or HT [1] index = hash & dict->ht[x].sizemask;Copy the code

Hash & (len-1); Redis sizemask (size-1).

What about hash conflicts

When Hash conflicts occur, Redis uses the chained address method to resolve the conflicts. The chained address method is to form a linked list of the conflicting nodes and place them in the index position, while Redis uses the header interpolation method. There are three other ways to resolve hash conflicts: open addressing (linear probe rehash, quadratic probe rehash, pseudo-random probe rehash), rehash, and setting up a public overflow zone. We’ll look at four separate ways to resolve hash conflicts later.

rehash

As operations continue, key pairs in the hash table may increase or decrease. To keep the hash table load factor within a range, you need to expand or shrink the hash table. This process is called rehash. The rehash process is as follows:

1. Allocate space for the dictionary HT [1] hash table, the size of which depends on the operation to be performed and the number of key-value pairs ht[0] currently contains (i.e., the value of ht[0]. Used) :
   • If an extension operation is performed, then the size of ht[1] is the first one greater than or equal to ht[0]. Used * 2 of 2^n (2 to the NTH power);
   • If the shrink operation is performed, then ht[1] has the size of the first 2^n greater than or equal to ht[0]. Used.
2. Rehash all key-value pairs saved in HT [0] onto HT [1] : Rehash means to recalculate the hash and index values of the key and then place the key-value pairs into the specified position in the HT [1] hash table.
3. When all key-value pairs contained in HT [0] are migrated to HT [1] (HT [0] becomes empty), release HT [0], set HT [1] to HT [0], and create a new blank hash table in HT [1] in preparation for the next rehash

When any of the following conditions are met, the program automatically begins to perform an extension operation on the hash table:

The server is not running BGSAVE or BGREWRITEAOF, and the hash table load factor is greater than or equal to 1. The server is running the BGSAVE or BGREWRITEAOF command, and the hash table load factor is greater than or equal to 5. Where, the load factor of the hash table can be determined by the formula:

# load factor = number of nodes saved in hash table/size of hash table load_factor = ht[0]. Used/HT [0].sizeCopy the code

That’s calculated.

For example, for a hash table of size 4 with four key-value pairs, the load factor for the hash table is:

For example, for a hash table of size 512 with 256 key-value pairs, the load factor of the hash table is:

Load_factor = 256/512 = 0.5 Depending on whether the BGSAVE command or BGREWRITEAOF command is being executed, the load factor required by the server to perform the extension operation is different, This is because to execute the BGSAVE or BGREWRITEAOF command, Redis creates a child of the current server process, and most operating systems use copy-on-write techniques to optimize the use of child processes, so while the child process exists, The server maximizes memory savings by increasing the load factor required to perform an extension operation to minimize hash table extension operations while the child process is still alive.

On the other hand, when the load factor of the hash table is less than 0.1, the program automatically starts to shrink the hash table.

Progressive rehash

Rehash migrates all key/value pairs from HT [0] to HT [1], but this is done not once, but increments. The reason for this is that a one-time migration when the data volume is large causes the server to customize the service over time. To avoid this, progressive rehashing occurs. Here are the detailed steps for progressive rehash of a hash table:

1. Allocate space for HT [1] so that the dictionary holds both HT [0] and HT [1] hash tables.
2. Maintain an index counter variable, rehashidx, in the dictionary and set its value to 0 to indicate that rehash work has officially begun.
3. Each time a dictionary is added, deleted, found, or updated during rehash, the program rehashes to HT [1] all key/value pairs on the REhashidx index of the HT [0] hash table, in addition to the specified operation. When the rehash is complete, the program increments the value of the rehashidx property by one.
4. As the dictionary operation continues, eventually at some point in time all key-value pairs of HT [0] are rehashed to HT [1], at which point the program sets the value of the rehashidx property to -1 to indicate that the rehash operation is complete.

The benefit of progressive Rehash is that it takes a dial-and-conquer approach, spreading the computation required for rehash key and value pairs over every add, delete, find, and update operation to the dictionary, thereby avoiding the massive computation that comes with centralized Rehash. During rehash, dictionary deletions and searches are performed simultaneously on HT [0] and HT [1]. Key pairs will be saved to HT [1], not ht[0]. This ensures that the key value of HT [0] will only be decreased. Ht [0] will eventually become empty with the rehash operation.

The features of Redis’s dictionary implementation can be summarized as follows:

• Dictionaries are widely used to implement various Redis features, including databases and hash keys.
• Dictionaries in Redis use hash tables as the underlying implementation, with each dictionary having two hash tables, one for normal use and one for rehash only.
• When dictionaries are used as the underlying implementation of a database, or a hash key, Redis uses the MurmurHash2 algorithm to calculate the hash value of the key.
• Hash tables use the chained address method to resolve key conflicts. Multiple key-value pairs assigned to the same index are joined into a one-way linked list.
• To expand or shrink a hash table, the program needs to rehash all the key-value pairs contained in the existing hash table into the new hash table, and the rehash process is not done once, but gradually.

Skip lists

A skiplist is an ordered data structure that enables fast access to nodes by maintaining multiple Pointers to other nodes in each node. Skip lists support node lookup with average O(\log N) worst O(N) complexity, and batch processing of nodes through sequential operations.

In most cases, skip lists can be as efficient as balanced trees, and because skip lists are much easier to implement than balanced trees, many programs use skip lists instead of balanced trees.

Redis uses skip lists as one of the underlying implementations of ordered set keys: If an ordered set contains a large number of elements, or if the members of the elements in the ordered set are long strings, Redis uses skip lists as the underlying implementation of ordered set keys.

Redis uses skip lists in only two places, one for ordered collection keys and the other for internal data structures in cluster nodes, but there is no other use for skip lists in Redis.

H /zskiplistNode and Redis. H /zskiplist. The zskiplistNode structure is used to represent the skip table node. The Zskiplist structure is used to store information about skip table nodes, such as the number of nodes, Pointers to the top and bottom of the table, and so on.The figure above shows an example of a jump representation. The zskiplist structure at the far left of the image contains the following properties:

• Header: Points to the table header node of the skip table.
• Tail: Refers to the end-of-table node of a skip table.
• Level: Records the level of the node with the largest level in the current skip table (the level of the top node is not counted).
• Length: Records the length of the skip table, that is, the number of nodes currently contained in the skip table (the head node is not counted).

Located to the right of the ZSkiplist structure are the four zskiplistNode structures that contain the following properties:

• Level: Each layer of a node is marked with words such as L1, L2, and L3. L1 represents the first layer, L2 represents the second layer, and so on. Each layer has two properties: a forward pointer and a span. The forward pointer is used to access other nodes at the end of the table, while the span records the distance between the node to which the forward pointer points and the current node. In the picture above, the arrow with the number on the line represents the forward pointer, and that number is the span. When the program traverses from the top of the table to the end of the table, access follows the forward pointer of the layer.
• Backward pointer: THE backward pointer of a node is marked with the word BW and points to the previous node of the current node. The back pointer is used when the program traverses from the end of the table to the beginning of the table.
• Score: 1.0, 2.0 and 3.0 in each node are the points saved by the node. In a skip list, the nodes are arranged in ascending order of the points they hold.
• Member objects (OBJ) : O1, O2, and O3 in each node are the member objects held by the node.

Note that a header node is constructed the same as any other node: it also has a back pointer, a score, and a member object, but none of these attributes are used, so the figure omits these parts and shows only the layers of the header node.

The zskiplistNode and Zskiplist structures are covered in more detail in the rest of this section.

1. Skip list node

The implementation of skiplist nodes is defined by the redis. H /zskiplistNode structure:

Typedef struct zskiplistNode {// backward pointer struct zskiplistNode *backward; // double score; // member object robj *obj; Struct zskiplistNode *forward; struct zskiplistNode *forward; // span unsigned int span; } level[]; } zskiplistNode;Copy the code

The level array of layer skip list nodes can contain multiple elements, each of which contains a pointer to another node. Programs can access other nodes faster through these layers. In general, the more layers there are, the faster the access to other nodes will be.

Each time a new skip list node is created, the program randomly generates a value between 1 and 32 as the size of the level array, which is the “height” of the layer, according to the power law (larger numbers are less likely to occur).

The figure below shows three nodes of level 1, level 3, and level 5, respectively. Because the array index of C language always starts at 0, the first level of the node is level[0], and the second level is Level [1], and so on.

Span the span of the span layer (level[I].span attribute) is used to record the distance between two nodes:

The greater the span between two nodes, the farther apart they are. All forward Pointers to NULL have a span of 0 because they are not connected to any node. At first glance, it’s easy to think that span is related to traversal, but that’s not the case — traversal is done using only the forward pointer, and span is actually used to calculate ranks: In the process of finding a node, the span of all layers visited along the way is accumulated and the result is the rank of the target node in the skip list.

As an example, the figure below shows the number of layers experienced by a node with a score of 3.0 and a member object of O3 in the skip list: The search process only goes through one layer, and the span of the layers is 3, so the target node ranks 3 in the skip list.

A backward pointer a backward pointer (attribute) of a node is used to access a node from the end of the table to the head: unlike a forward pointer, where you can skip multiple nodes at once, since there is only one backward pointer per node, you can only go back to the previous node at a time.

The dotted line below shows how to traverse all nodes in a skip list from the end of the table to the beginning of the table: The program first accesses the tail node of the skip table through the tail pointer, then the penultimate node through the back pointer, then the penultimate node along the back pointer, and then encounters a NULL back pointer and the access ends.

Points and members

The score attribute of a node is a floating-point number of type double, and all nodes in a skip list are sorted by score from smallest to largest.

The node’s member object (the obj property) is a pointer to a string object that holds an SDS value.

In the same skip list, each node must hold unique member objects, but multiple nodes can hold the same points: Nodes with the same score are sorted by the size of their member objects in lexicographical order, with nodes with smaller member objects coming first (near the head of the table) and nodes with larger member objects coming second (near the bottom of the table).

For example, in the skip table shown in the following figure, the three skip table nodes all save the same score 10086.0, but the node that saves member object O1 is ranked ahead of the node that saves member object O2 and O3, and the node that saves member object O2 is ranked ahead of the node that saves member object O3. Therefore, the order of o1, O2, and O3 in the dictionary is o1 <= O2 <= O3.

2. Jump table

Although it is possible to form a skip list only with multiple skip list nodes, as shown in the figure below.However, by using a Zskiplist structure to hold these nodes, the program can more easily process the entire skiplist, such as quickly accessing the top and bottom of the skiplist, or quickly obtaining information about the number of skiplist nodes (that is, the length of the skiplist), as shown in the figure below.The zskiplist structure is defined as follows:

Typedef struct zskiplist {// struct zskiplistNode *header, *tail; // The number of nodes in the table unsigned long length; Int level; int level; } zskiplist;Copy the code

The header and tail Pointers point to the head and tail nodes of the skip table, respectively. By using these two Pointers, the complexity of the program to locate the head and tail nodes is O(1).

By using the length attribute to record the number of nodes, the program can return the length of the skip list within O(1) complexity.

The level attribute is used to obtain the number of layers of the node with the highest middle height in the skip table in O(1) complexity. Note that the height of the top node is not counted.

Summary of skip lists:

• Skip lists are one of the underlying implementations of ordered collections and have no other use in Redis.
• Redis’ skiplist implementation consists of zskiplist and zskiplistNode structures, where Zskiplist is used to store skiplist information (such as head node, tail node, length), and zskiplistNode is used to represent skiplist nodes.
• The height of each skip list node is a random number between 1 and 32.
• In the same skip list, multiple nodes can contain the same score, but the member objects of each node must be unique.
• The nodes in the skip list are sorted by the size of the points, and when the points are the same, the nodes are sorted by the size of the member objects.

Set of integers

The set of integers (intSet) is one of the underlying implementations of the set key: Redis uses the set of integers as the underlying implementation of the set key when a set contains only integer numeric elements and the set has a small number of elements.

For example, if we create a set key that contains only five elements, and all elements in the set are integer values, the underlying implementation of the set key would be a set of integers:

redis> SADD numbers 1 3 5 7 9
(integer) 5

redis> OBJECT ENCODING numbers
"intset"
Copy the code

Intset is an abstract data structure Redis uses to store integer values. It can store integer values of type INT16_t, int32_t, or int64_t without repeating elements in the set.

Each intset.h/intset structure represents a collection of integers:

// uint32_t encoding; // Uint32_t length; Int8_t contents[]; } intset;Copy the code

Contents array is a low-level implementation of the contents array: each element of the contents array is an item of the contents array, and each item is arranged in order of value from smallest to largest in the array, and the array contains no duplicates.

The Length property records the number of elements in the integer collection, which is the length of the contents array.

While the intset structure declares the contents property as an array of type INT8_T, the contents array does not actually hold any values of type INT8_T — the true type of the contents array depends on the value of the encoding property: If the encoding property has the value INTSET_ENC_INT16, then contents is an array of type INT16_T, and each item in the array is an integer value of type int16_T (minimum: -32,768, Maximum is 32,767). The following figure shows a collection of integers containing five integer values of type INT16_T.

Whenever a new element is added to the integer set, and the new element is of a longer type than all existing elements in the integer set, the integer set needs to be upgraded before the new element can be added to the integer set.

Upgrading the collection of integers and adding new elements is done in three steps:

• Expands the size of the underlying array of integers based on the type of the new element and allocates space for the new element.
• All the existing elements of the underlying array are converted to the same type as the new element, and the converted elements are placed in the correct bit, and in the process of placing the elements, the ordered nature of the underlying array remains unchanged.
• Adds a new element to the underlying array.

Integer collections do not degrade, and once an array has been upgraded, the encoding remains the same.

Summary of integer sets:

• The collection of integers is one of the underlying implementations of the collection key.
• The underlying implementation of a collection of integers is an array, which holds the collection elements in an ordered, non-repetitive fashion. The program changes the type of the array as needed, depending on the type of the newly added element.
• The upgrade operation brings operational flexibility to integer collections and saves as much memory as possible.
• Integer sets only support upgrade operations, not degrade operations.

Compress lists

Ziplist is one of the underlying implementations of list keys and hash keys.

When a list key contains only a small number of list items, and each item is either a small integer value or a short string length, Redis uses compressed lists for the underlying implementation of the list key.

For example, executing the following command creates a list key for a compressed list implementation:

redis> RPUSH lst 1 3 5 10086 "hello" "world"
(integer) 6

redis> OBJECT ENCODING lst
"ziplist"
Copy the code

Because the list keys contain small integer values like 1, 3, 5, 10086, and short strings like “Hello” and “world”.

In addition, when a hash key contains only a small number of key-value pairs, and the keys and values of each pair are either small integer values or short strings, Redis uses a compressed list for the underlying implementation of the hash key.

For example, to create a hash key for a compressed list implementation, execute the following command:

redis> HMSET profile "name" "Jack" "age" 28 "job" "Programmer"
OK

redis> OBJECT ENCODING profile
"ziplist"
Copy the code

Because all the keys and values contained in hash keys are small integer values or short strings. Structure of a compressed list: A compressed list is a sequential data structure composed of a series of specially encoded contiguous memory blocks developed by Redis to save memory.

A compressed list can contain any number of entries, each of which can hold either a byte array or an integer value.

The following figure shows the components of a compressed list.The following table records the type, length, and purpose of each component. Table 7-1 lists the type, length, and purpose of each component.

attribute	type	The length of the	use
zlbytes	uint32_t	4 bytes	Record the number of bytes of memory occupied by the entire compressed list: used when reallocating memory to the compressed list, or calculating the location of Zlend.
zltail	uint32_t	4 bytes	Records the number of bytes from the end of the compression list to the start of the compression list: With this offset, the program can determine the end of the table without traversing the entire compression list.
zllen	uint16_t	2 –	When the value of this attribute is smaller than UINT16_MAX (65535), the value of this attribute is the number of nodes that the compressed list contains; When this value is equal to UINT16_MAX, the true number of nodes needs to be computed by traversing the entire compressed list.
entryX	List node	indefinite	The length of each node contained in the compressed list is determined by the contents stored in the node.
zlend	uint8_t	1 byte	The special value 0xFF (decimal 255) is used to mark the end of the compressed list.

Structure of compressed list nodes:Each compressed list node consists of previous_entry_LENGTH, Encoding, and Content, as shown in the following figure.

• The node’s previous_entry_length property records, in bytes, the length of the previous node in the compressed list.
• The encoding property of the node records the type and length of the data held by the node’s Content property:
• The content property of a node holds the value of the node, which can be a byte array or an integer. The type and length of the value are determined by the encoding property of the node.

Summary of compressed lists:

• Compressed lists are sequential data structures developed to save memory.
• Compressed lists are used as one of the underlying implementations of list keys and hash keys.
• A compressed list can contain multiple nodes, each of which can hold a byte array or integer value.
• Adding a new node to the compressed list, or removing a node from the compressed list, can cause a cascading update operation, but this operation is infrequent.

The last

If you feel good, please click the like to follow and forward, thank you very much.