Redis中数据结构的底层实现分析

# Redis中数据结构的底层实现分析

## 引言

Redis作为高性能的键值存储系统，其卓越的性能表现很大程度上得益于精心设计的数据结构实现。本文将深入分析Redis核心数据结构的底层实现机制，包括简单动态字符串(SDS)、链表、字典、跳跃表、整数集合和压缩列表等。通过剖析这些数据结构的实现原理，我们可以更好地理解Redis如何在高性能、低内存占用和丰富功能之间取得平衡。

## 一、简单动态字符串(SDS)

### 1.1 SDS结构定义
Redis没有直接使用C语言传统的字符串表示，而是构建了名为简单动态字符串(Simple Dynamic String, SDS)的抽象类型：

```c
struct sdshdr {
    int len;     // 记录buf数组中已使用字节的数量
    int free;    // 记录buf数组中未使用字节的数量
    char buf[];  // 字节数组，用于保存字符串
};

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;    // 1字节
    uint8_t alloc;   // 1字节
    unsigned char flags; // 1字节
    char buf[];
};
// 类似还有sdshdr16、sdshdr32、sdshdr64

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

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;

typedef struct dictht {
    dictEntry **table;      // 哈希表数组
    unsigned long size;     // 哈希表大小
    unsigned long sizemask; // 哈希表大小掩码，用于计算索引值
    unsigned long used;    // 哈希表已有节点数量
} dictht;

typedef struct dictEntry {
    void *key;              // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;                    // 值
    struct dictEntry *next; // 指向下个哈希表节点
} dictEntry;

typedef struct dict {
    dictType *type;     // 类型特定函数
    void *privdata;     // 私有数据
    dictht ht[2];       // 哈希表(两个，用于rehash)
    int rehashidx;      // rehash索引，-1表示未进行
} dict;

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;

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

+--------+--------+--------+--------+--------+--------+--------+--------+
| zlbytes | zltail | zllen  | entry1 | entry2 |  ...   | entryN | zlend  |
+--------+--------+--------+--------+--------+--------+--------+--------+

typedef struct redisObject {
    unsigned type:4;        // 类型(字符串/列表/哈希等)
    unsigned encoding:4;    // 编码(底层实现方式)
    unsigned lru:LRU_BITS;  // LRU时间或LFU计数
    int refcount;           // 引用计数
    void *ptr;              // 指向底层实现数据结构的指针
} robj;