Shulou(Shulou.com)06/01 Report--

This article introduces the relevant knowledge of "what is the basic data structure of Redis". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Integer set

When a collection contains only integers and there are not many elements in the set, Redis uses the integer collection intset. First, take a look at the data structure of intset:

Typedef struct intset {

/ / Encoding method

Uint32_t encoding

/ / the number of elements contained in the collection

Uint32_t length

/ / Save an array of elements

Int8_t contents [];} intset

In fact, the data structure of intset is easier to understand. A data saving element, the number of length saving elements, that is, the size of the contents, and the encoding used by encoding to save the data.

We can see from the code that the encoding types of encoding include:

# define INTSET_ENC_INT16 (sizeof (int16_t))

# define INTSET_ENC_INT32 (sizeof (int32_t))

# define INTSET_ENC_INT64 (sizeof (int64_t))

Actually, we can see that. The type of Redis encoding is the size of the data. As an in-memory database, this design is designed to save memory.

Since there are three data structures from small to large, when inserting data, use a small data structure to save memory as much as possible. If the inserted data is larger than the original data structure, expansion will be triggered.

There are three steps to expand capacity:

Modify the data type of the entire array and reallocate space based on the type of the new element

Replace the original data with a new data type, put it back to where it should be, and save the sequence.

Then insert a new element

The set of integers does not support degraded operations, and cannot be degraded once upgraded.

Jump table

Jump list is a kind of linked list, which is a data structure that uses space for time. The average jump table supports O (logN), the worst O (N) complexity lookup.

The jump table consists of a zskiplist and a number of zskiplistNode. Let's first look at their structure:

/ * ZSETs use a specialized version of Skiplists * / / * * Jump table node * /

Typedef struct zskiplistNode {

/ / member object

Robj * obj

/ / score

Double score

/ / back pointer

Struct zskiplistNode * backward

/ / layer

Struct zskiplistLevel {

/ / forward pointer

Struct zskiplistNode * forward

/ / Span

Unsigned int span;} level [];} zskiplistNode

/ * Jump Table * /

Typedef struct zskiplist {

/ / header node and footer node

Struct zskiplistNode * header, * tail

/ / number of nodes in the table

Unsigned long length

/ / the number of layers of the node with the largest number of layers in the table

Int level;} zskiplist

So according to this code, we can draw the following structure diagram:

In fact, the jump table is a data structure that uses space for time, and uses level as the index of the linked list.

Someone previously asked the author of Redis why he used a jump table instead of tree to build an index. The author's answer is:

Save memory.

Serving ZRANGE or ZREVRANGE is a typical linked list scenario. The performance of time complexity is similar to that of the balance tree.

The most important point is that the implementation of the jump table can easily reach the level of O (logN).

Compressed list

Compressed linked list Redis the author's introduction is a two-way linked list designed to save memory as much as possible.

The data structure given by the comments in a compressed list code is as follows:

Zlbytes represents the number of bytes of memory used by the entire compressed list

Zltail specifies the offset of the tail node of the compressed list

Zllen is the number of compressed list entry

Entry is the node of ziplist

Zlend marks the end of the compressed list

There is also a single pointer in this list:

Head offset of the start node of the ZIPLIST_ENTRY_HEAD list

Head offset of the end node of the ZIPLIST_ENTRY_TAIL list

Offset at the end of the tail node of the ZIPLIST_ENTRY_END list

Take a look at the structure of an entry:

/ * * Save the structure of ziplist node information * /

Typedef struct zlentry {

/ / prevrawlen: the length of the front node

/ / prevrawlensize: the size of bytes required to encode prevrawlen

Unsigned int prevrawlensize, prevrawlen

/ / len: the length of the current node value

/ / lensize: the size of bytes required to encode len

Unsigned int lensize, len

/ / the size of the current node header

/ / equals prevrawlensize + lensize

Unsigned int headersize

/ / the type of encoding used by the current node value

Unsigned char encoding

/ / pointer to the current node

Unsigned char * p;} zlentry

Explain these parameters in turn.

The length of the front node of the prevrawlen. Here is an extra size, which actually records the size of the prevrawlen. Redis does not directly use the default length of int in order to save memory, but is upgraded gradually.

Similarly, len records the length of the current node, and lensize records the length of len.

Headersize is the sum of the two size mentioned earlier.

Encoding is the data type of this node. Note here that the type of encoding includes only integers and strings.

The pointer to the p node does not need to be explained too much.

It should be noted that each node saves the length of the previous node. If a node is updated or deleted, the data after this node also needs to be modified. In a worst-case scenario, if each node is at the zero boundary point that needs to be expanded, the node after this node will have to modify the parameter size, causing a chain reaction. This is the worst time complexity of compressed linked list O (n ^ 2). However, all nodes are at a critical value, which can be said to be relatively small.

This is the end of the content of "what is the basic data structure of Redis". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.