Redis数据结构

Redis一共有六种数据结构，分别是简单动态字符串、链表、字典、跳表、整数集合、压缩列表。

简单动态字符串（SDS）

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

SDS的数据结构：

struct sdshdr {
    // 记录buf数据中已使用字节的数量
    // 等于SDS所保存字符串的长度
    int len;

    // 记录buf数组中未使用字节的数量
    int free;;

    // 字节数组，用于保存字符串
    char buf[];
}

Redis基础（一）数据结构与数据类型-LMLPHP

比起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基础（一）数据结构与数据类型-LMLPHP

链表被广泛用于实现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基础（一）数据结构与数据类型-LMLPHP

字典被广泛用于实现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;

Redis基础（一）数据结构与数据类型-LMLPHP

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

整数集合（intset）

整数集合（intset）是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。

整数集合的数据结构：

typedef struct intset {
    // 编码方式
    uint32_t encoding;

    // 集合包含的元素数量
    uint32_t length;

    // 保存元素的数组
    int8_t contents[];
} intset;

Redis基础（一）数据结构与数据类型-LMLPHP

整数集合是集合键的底层实现之一。
整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。
升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。
整数集合只支持升级操作，不支持降级操作。

压缩列表（ziplist）

压缩列表（ziplist）是列表键和哈希键的底层实现之一。当一个列表链只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。

Redis基础（一）数据结构与数据类型-LMLPHP

压缩列表是一种为节约内存而开发的顺序型数据结构。
压缩列表被用作列表键和哈希键的底层实现之一。
压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。

Redis数据类型

Redis中，键的数据类型是字符串，但提供了丰富的数据存储方式，方便开发者使用，值的数据类型有很多，常用的数据类型有五种，分别是字符串（string）、列表（list）、字典（hash）、集合（set）、有序集合（sortedset）。

字符串（string）

“字符串（string）”这种数据结构类型非常简单，对应到数据结构里，就是Redis里的简单动态字符串（SDS）。

列表（list）

列表这种数据类型支持存储一组数据。这种数据类型对应两种实现方法，一种是压缩列表（ziplist），另一种是双向循环链表。

当列表中存储的数据量比较小的时候，列表就可以采用压缩列表的方式实现。具体需要同时满足下面两个条件：

列表中保存的单个数据（有可能是字符串类型的）小于64字节；
列表中数据个数少于512。

字典（hash）

字典类型用来存储一组数据对。每个数据对又包含键值两部分。字典类型也有两种实现方式。一种是压缩列表，另一种是散列表。

同样，只有当存储的数据量比较小的情况下，Redis才使用压缩列表来实现字典类型。具体需要满足两个条件：

字典中保存的键和值的大小都要小于64字节；
字典中键值对的个数要小于512个。

集合（set）

集合这种数据类型用来存储一组不重复的数据。有两种实现方式：一种是基于有序数组，另一种是基于散列表。

当要存储的数据，同时满足下面这样两个条件的时候，Redis就采用有序数组，来实现集合这种数据类型。

存储的数据都是整数；
存储的数据元素个数不超过512个。

有序集合（sortedset）

有序集合用来存储一组数据，并且每个数据会附带一个得分。通过得分的大小，我们将数据组织成跳表这种数据结构，以支持快速地按照得分值、得分区间获得数据。

有序集合也有两种实现方式：跳表和压缩列表。使用压缩列表来实现有序集合的前提：

所有数据的大小都要小于64字节；
元素个数要小于128个。

大杂草

Redis基础（一）数据结构与数据类型

Redis数据结构

简单动态字符串（SDS）

链表（list）

字典（dict）

跳表（skiplist）

整数集合（intset）

压缩列表（ziplist）

Redis数据类型

字符串（string）

列表（list）

集合（set）

有序集合（sortedset）

参考资料