Redis的五种数据结构分别是字符串STRING、列表LIST、哈希HASH、集合SET、有序集合ZSET。在Redis中，将这五种数据类型引申为对象类型。通过这五种不同类型的对象，Redis可以在执行命令之前，根据对象的类型来判断一个对象是否可以执行给定的命令。

redis> SET msg "hello world"
OK

redis> TYPE msg
string

对不同类型的对象执行以上命令，结果如下表所示：

而这几种对象则是基于简单动态字符串（SDS）、双端链表、字典、压缩列表、整数集合构建的一套对象系统。
**

简单动态字符串SDS

Redis没有直接使用C语言的传统字符串表示，而是自己构建了一个名为简单动态字符串的抽象数据类型。

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

一个示例：

SDS仍遵循C字符串以空字符结尾的惯例，但并不计入len属性里，系统额外分配1字节的空间。
与C语言传统的字符串相比，升级后的抽象数据类型有很多优点：

1. 常数复杂度获取字符串长度。因为SDS结构中自带len属性，无需再对字符串进行遍历。
2. 杜绝缓冲区溢出。根据free属性可以判断要写入字符串的长度是否超过剩余空间的大小。
3. 接2，根据free属性的大小对字符串缓冲区进行空间预分配和惰性空间释放。前者是在对一个SDS进行修改时额外分配使用空间（如果SDS的长度小于1MB分配2*len+1byte的空间，大于等于1MB时分配len+1MB+1byte），后者是当缩短字符串的长度时，程序不会立即进行内存重分配，而是归入free。
4. 二进制安全。C字符串必须符合某种编码且除了末尾之外不等含有空字符，导致其只能保存文本数据，不能保存图片、视频等二进制数据。而SDS的buf属性实质上是字节数组，用来保存二进制数据而不是字符。

链表

链表就是我们熟悉的那个链表啦，不过Redis对链表又进行了进一步的封装。

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;

这样可以轻易的获取这个双端链表的头节点、尾节点和长度，并且*void指针保证了保存的节点值可以是不同的类型。

字典

字典是哈希键的底层实现之一。哈希表的结构如下：

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    // union，C语言中的共用体。原理是内存覆盖，只同时存在一个成员
    // 内存大小就是那一个成员占用空间大小
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

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

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash索引
    // 当rehash不在进行时，值为-1
    in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

一个普通状态下的字典：

哈希算法

当要将一个新的键值添加到字典时，需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值将新键值对的哈希表节点放到哈希表数组的指定索引上面。

#使用字典设置的哈希函数，计算键key的哈希值
hash = dict->type->hashFunction(key);

#使用哈希表的sizemask属性和哈希值，计算出索引值
#根据情况不同，ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

注：Redis使用MurmurHash2算法来计算哈希值。（murmur：低语、呜咽的意思）

渐进式rehash

其实我们看上图会发现一个字典下的 ht[1] 好像在打酱油，啥都没干，其实在一个字典在正常使用的时候它确实没啥用。但随着操作的执行，哈希表保存的键值对会逐渐地增多或减少。为了让负载因子维持在一个合理的范围内，程序需要对哈希表的大小进行相应的拓展或收缩。

# 负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

当以下条件任意一个条件被满足时，程序会自动对哈希表进行拓展操作：

1. 服务目前没有执行BGSAVE或者BGREWRITEAOF命令时，并且负载因子大于等于1。
2. 服务目前正在执行BGSAVE或者BGREWRITEAOF命令时，并且负载因子大于等于5。

大致分为3步：

1. 为 ht[1] 哈希表分配空间。根据拓展或者收缩分配合适的空间。
2. 将保存在 ht[0] 的所有键值对rehash到 ht[1] 上。此过程会重新计算键的哈希值和索引值。
3. 当2完成后，释放 ht[0]，将 ht[1] 设置为 ht[0]，并新建一个 ht[1] 空白哈希表。

在rehash之前，rehasidx参数的值为0。每次进行操作都会对其加1，并在rehash完成之后设置为-1，表示操作完成。
在rehash过程中，字典中键值对的删除（delete）、查找（find）、更新（update）会在两个表上进行，保证一致性。而新添加的元素只会对 ht[1] 进行操作。

跳跃表

跳跃表是有序集合键的底层实现之一。它的结构是：

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

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

一个跳跃表：

对部分参数进行一下说明：

• level：距离跳跃表内，层数最大的节点的层数（不包括表头节点层数）。
• length：跳跃表的长度，也即是节点数量（不包括表头结点）。
• 层（level）：节点中L1、L2、L3就表示层。每层中有两个属性：前进指针和跨度。前进指针用于访问位于表位方向的其他节点，而跨度记录了前进指针所指向节点和当前节点的距离。
• backword：后退指针，用户从表位到表头的遍历。
• 分值（score）：一个double类型浮点数，用于记录每个节点保存的分值，从小到大排列。
• 成员对象（obj）：节点保存的成员对象。每个节点的成员对象都是唯一的。

整数集合

整数集合是集合键的底层实现。结构如下：

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

一个包含了五个 int16_t 类型整数值的整数集合：

encoding属性是一个可变参数，可以选择INTSE_ENC_INT16、INTSE_ENC_INT32、INTSE_ENC_INT64。选择一整类型作为存储类型。如果要添加一个新元素到整数集合且此新元素比所有的类型都长时，需要对整数集合进行升级操作。

升级

如果我们有一个 INT16 类型的整数集合，集合里的元素为1、2、3。如果此时向集合里添加一个65535，则就需要将集合升级到 INT32 位。需要先将空间升级到 32*4=128位。再将每一位数据移到它应该在的位上。元素移动顺序应该是从后往前，并在最后将新元素写入。

降级

整数集合不支持降级操作，一旦对数组进行升级就只能保持升级后状态。

压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一。它的结构是这样的：
压缩列表结构.png
压缩列表各个属性的详细说明：

一个示例：

• zlbytes属性值为 0x50（十进制80），表示压缩列表总长为80。
• zltail属性值为 0x3c （十进制60）。
• zllen属性值为 0x3 （十进制3），表示由3个节点。

压缩列表节点构成

previous_entry_length

此属性以字节为单位，记录了压缩列表前一个节点的长度。长度为1字节或5字节。

• 如果前一字节的长度小于254字节，那么此属性的长度为1字节：前一节点的长度就保存在这一字节里。
• 如果是大于等于254字节，那么此属性就是5字节：一字节会被设置为0xFE（十进制254），之后的字节保存前一节点的长度。

encoding

节点的encoding属性记录节点content属性所保存数据的类型及长度。

• 一字节长、两字节长或者5字节长，值的最高位为00、01、或10，content保存的是字节数组。
• 一字节长，最高位是11，content保存的是整数值。

content

content属性保存节点的值。值可以是一个字节数组或者整数。值的类型和长度由encoding决定。
content.png

连锁更新

当我们向压缩列表里添加新节点的时候，可能会出现一种情况：有一个压缩列表，e1 至 eN 的长度都介于250到253在字节之间。如果我们将一个长度等于254的节点new设置为压缩列表的表头节点，但是 e1 的 previous_entry_length 属性仅为一字节，它就没办法保存新节点new的长度
所以程序需要对压缩列表执行空间重分配操作，将 e1 的 previous_entry_length 属性从原来的1字节扩展为5字节。
但是，麻烦事来了。e1 原本小于254字节，进行拓展之后大于254字节。但是 e2 的 previous_entry_length 属性还是1字节。因此还需要对e2 的 previous_entry_length 属性进行拓展。正如 e1 拓展引起 e2 拓展一样，e2 拓展又会引起 e3 拓展......就这样，这个压缩列表里所有的节点都需要进行拓展。这就称为连锁更新。

总结

博客会不定时更新，如果你想看更多内容，可以关注公众号。