What is the basic data structure of Redis?

Integer set

If a set contains only a few integer elements, Redis will use the integer set intset. First look at the data structure of intset:

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

In fact, the data structure of intset is relatively easy to understand. A data storage element, length stores the number of elements, which is the size of contents, and encoding is the encoding method used to store data.

We can know from the code that the encoding type of encoding includes:

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

In fact, we can see it. The type of Redis encoding refers to the size of the data. As an in-memory database, this design is adopted to save memory.

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

There are three steps for expansion:

1. According to the type of the new element, modify the data type of the entire array and reallocate the space

2. Convert the original data to the new data type, re-place it where it should be, and preserve the order

3. Then insert the new element

Integer collections do not support downgrade operations. Once upgraded, they cannot be downgraded.

Jump list

The skip list is a type of linked list, a data structure that uses space to exchange time. The skip list supports O(logN) average search and worst-case O(N) complexity search.

The skip list is composed of a zskiplist and multiple zskiplistNode. Let’s take a look at their structure first:

/* ZSETs use a specialized version of Skiplists *//*
 * 跳跃表节点
 */

typedef struct zskiplistNode {
    // 成员对象
    robj *obj;
    // 分值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];

    } zskiplistNode;
        
/*
 * 跳跃表
 */

typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;

} zskiplist;

So based on this code we can draw the following structure diagram:

In fact, the jump table is a utilization space The time-changing data structure uses level as the index of the linked list.

Someone asked the author of Redis before why he uses jump tables instead of trees to build indexes? The author's answer is:

1. Save memory.

2. When using ZRANGE or ZREVRANGE, it involves a typical linked list operation scenario. The performance of time complexity is similar to that of balanced trees.

3. The most important point is that the implementation of the jump table is very simple and can reach the O(logN) level.

Compressed List

Compressed Linked List The author of Redis introduces it as a doubly linked list designed to save memory as much as possible.

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

zlbytes represents the data structure used by the entire compressed list The number of memory bytes

zltail specifies the offset of the tail node of the compression list

zllen is the number of entries in the compression list

entry is the node of ziplist

zlend Marks the end of the compressed list

There is also a single pointer in this list:

ZIPLIST_ENTRY_HEAD Head offset of the start node of the list

ZIPLIST_ENTRY_TAIL Head offset of the end node of the list

ZIPLIST_ENTRY_ENDThe offset of the end of the tail node of the list

Look at the structure of an entry again:

/*
 * 保存 ziplist 节点信息的结构
 */

typedef struct zlentry {
    // prevrawlen ：前置节点的长度
    // prevrawlensize ：编码 prevrawlen 所需的字节大小
    unsigned int prevrawlensize, prevrawlen;
    // len ：当前节点值的长度
    // lensize ：编码 len 所需的字节大小  
    unsigned int lensize, len;
    // 当前节点 header 的大小
    // 等于 prevrawlensize + lensize
    unsigned int headersize;
    // 当前节点值所使用的编码类型
    unsigned char encoding;
    // 指向当前节点的指针
    unsigned char *p;

} zlentry;

Explain these parameters in turn.

prevrawlen The length of the preceding node, there is an extra size here, which actually records the size of prevrawlen. In order to save memory, Redis does not directly use the default int length, but gradually upgrades it.
Similarly len records the length of the current node, lensize records the length of len.
headersize is the sum of the two sizes mentioned above.
encoding is the data type of this node. Note here that encoding types only include integers and strings.
p Node pointer, no need to explain too much.

One thing to note is 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. The worst case scenario is that if every Each node is at the zero point that needs to be expanded, which will cause the nodes after this node to modify the size parameter, triggering a chain reaction. At this time, the worst time complexity of compressing the linked list is O(n^2). However, all nodes are at critical values, so the probability can be said to be relatively small.

The above is the detailed content of What is the basic data structure of Redis?. For more information, please follow other related articles on the PHP Chinese website!