Redis一共有六种数据结构，分别是简单动态字符串、链表、字典、跳表、整数集合、压缩列表。
简单动态字符串（SDS）Redis只会使用C字符串作为字面量，在大多数情况下，Redis使用SDS（Simple Dynamic String，简单动态字符串）作为字符串表示。
SDS的数据结构：
struct sdshdr { // 记录buf数据中已使用字节的数量 // 等于SDS所保存字符串的长度 int len; // 记录buf数组中未使用字节的数量 int free;; // 字节数组，用于保存字符串 char buf[]; }
比起C字符串，SDS具有以下优点：
常数复杂度获取字符串长度
杜绝缓冲区溢出
减少修改字符串时带来的内存重分配次数
二进行安全
兼容部分C字符串函数
链表（list）链表的数据结构：
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;
链表被广泛用于实现Redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等。
每个链表节点由一个listNode结构来表示，每个节点都有一个指向前置节点和后置节点的指针，所以Redis的链表实现是双端链表。
每个链表使用一个list结构来表示，这个结构带有表头节点指针、表尾节点指针，以及链表长度等信息。
因为链表表头节点的前置节点和表尾节点的后置节点都指向NULL，所以Redis的链表实现是无环链表。
通过为链表设置不同的类型特定函数，Redis的链表可以用于保存各种不同类型的值。
字典（dict）字典的数据结构：
typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值 unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used; }dictht; typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_tu64; int64_ts64; }v; // 指向下一个哈希表节点，形成键表 struct dictEntry *next; }dictEntry; typedef struct dict { // 类型特定函数 dictType *type; // 私有数据 void *privdate; // 哈希表 dictht ht[2]; // rehash索引 // 当rehash不在进行时，值为-1 in trehashidx; /* rehashing not in progress if rehashidx == -1 */ }dict; typedef struct dictType { // 计算哈希值的函数 unsigned int (*hashFunction)(const void *key); // 复制键的函数 void *(*keyDup)(void *privdata, const void *key); // 复制值的函数 void *(*valDup)(void *privdata, const void *obj); // 对比键的函数 int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 销毁键的函数 void (*keyDestructor)(void *privdata, void *key); // 销毁值的函数 void (*valDestructor)(void *privdata, void *obj); }dictType;
字典被广泛用于实现Redis的各种功能，其中包括数据库和哈希键。
Redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，另一个仅在进行rehash时使用。
当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。
哈希表使用键地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表。
在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性地完成的，而是渐进式地完成的。
跳表（skiplist）跳表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳表查询的时间复杂度O(logN)、最坏情况是O(N)，还可以通过顺序操作来指处理节点。
跳表的数据结构：
typedef struct zskiplistNode { // 层 struct zskiplistLevel { // 前进指针 struct zskiplistNode * forward; // 跨度 unsigned int span; } level[]; // 后退指针 struct zskiplistNode *backward; // 分值 double score; // 成员对象 robj *obj; } zskiplistNode; typedef struct zskiplist { // 表头节点和表尾节点 struct zskiplistNode *header, *tail; // 表中节点数量 unsigned long length; // 表中层数最大的节点的层数 int level; } zskiplist;
跳表是有序集合的底层实现之一。