简单动态字符串

Redis 只会使用 C 字符串作为字面量，在大多数情况下，Redis 使用 SDS（Simple Dynamic String，简单动态字符串）作为字符串表示。

SDS 的定义如下：

每个 sds.h/sdshdr 结构表示一个SDS 值。

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

SDS 遵循 C 字符串以 ‘\0’ 结尾的惯例，这个一字节空间不算在 len 属性中，这个空间分配以及添加到末尾的操作是由 SDS 函数自动完成的，所以这个空字符对于使用者来说是透明的。这种做法的好处是可以重用一部分操作 C 字符串的函数。

比起 C 字符串，SDS 具有以下优点：

常数时间获取字符串长度（通过 len）。
杜绝缓冲区溢出（扩容时一般采取 free 等于 len 的方式，free 不超过 1MB）。
减少修改字符串长度时所需的内存重新分配次数（空间预分配和惰性释放）。
二进制安全(存在 len 属性)。
兼容部分 C 字符串函数。

链表

链表节点表示：

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);				// 节点值释放函数
    void *(*match)(void *ptr, void *key);	// 节点值对比函数
}list;

链表被广泛用于实现 Redis 的各种功能，比如列表键、发布与订阅、慢查询、监视器等。
头节点的前置指针和尾节点的后置指针都指向 NULL，链表实现为双端无环链表。
获取头节点、尾节点、链表长度的时间复杂度为 O(1)，获取某个节点的前置节点和后置节点的复杂度也为 O(1)。
通过为链表设置不同的类型特定函数，Redis 的链表可以用于保存各种类型不同的值。

字典

Redis 字典所使用的哈希表由 d.ct.h/dictht 结构定义：

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

哈希表节点使用 dictEntry 结构表示，dictEntry 结构保存着一个键值对。

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    }
    struct dictEntry *next;
}dictEntry;

Redis 字典由 dict.h/dict 结构表示：

typedef struct dict {
    dicyType *type;		// 类型特定函数
    void *privdata;		// 私有数据
    dictht ht[2];		// 两个哈希表
    int rehashidx;		// rehash 索引。没有进行 rehash 时值为 -1
}

rehash 的操作步骤

为 ht[1] 分配空间，这个哈希表的空间大小取决于要执行的操作与 ht[0] 包含的键值对数量（即 ht[0].used）。
将保存到 ht[0] 的所有键值对 rehash 到 ht[1] 中。
当所有键值对迁移完成后，释放 ht[0]，将 ht[1] 设为 ht[0]，并在 ht[1] 新建一个空白哈希表，为下一次 rehash 做准备。

渐进式 rehash 的步骤

为 ht[1] 分配空间。
将变量 rehashidx 的值设为 0，表示 rehash 开始。
在 rehash 期间，每次对字典进行添加、删除、更新或查找时，还会将 ht[0] 上 rehashidx 索引上的所有键值对迁移到 ht[1]，完成后，rehashidx 加一。
最终 ht[0] 的所有键值对会全部迁移到 hash[1]，这时设置 rehashidx 为 -1，表示 rehash 操作已完成。

总结

字典被广泛用于实现 Redis 的各种功能，其中包括数据库和哈希键。
Redis 中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，另一个仅在进行 rehash 时使用。
Redis 采用 MurmurHash2 算法来计算键的哈希值。
哈希表使用链地址法来解决哈希冲突，被分配到同一索引上的多个键值对会连接成一个单向链表。
在进行扩容或缩容时，会进行 rehash。rehash 过程不是一次性完成的，而是渐进式完成的，避免对服务器性能造成影响。

跳表

跳表节点定义：

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

zskiplist 结构如下：

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

跳表是有序集合的底层实现之一。
Redis 的跳表实现由 zskiplist 和 zskiplistNode 两个结构完成，其中 zskiplist 用于表示跳表信息（如头结点、尾节点、长度），而 zskiplistNode 用于表示跳表节点。
跳表节点层高是 1 到 32 之间的随机数。
在同一个跳表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。
跳表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。