浅谈 Redis 数据结构

Redis 数据库里面的每个键值对都是由对象组成的，其中数据库的键总是一个字符串对象（string object），数据库的值则可以使字符串对象、列表对象（list object）、哈希对象（hash object）、集合对象（set object）和有序集合对象（sorted object）这五种数据结构。下面我们一起来看下这些数据对象在 Redis 的内部是怎么实现的，以及 Redis 是怎么选择合适的数据结构进行存储等。

简单动态字符串

Redis 没有直接使用 C 语言传统的字符串标识，而是自己构建了一种名为简单动态字符串 SDS（simple dynamic string）的抽象类型，并将 SDS 作为 Redis 的默认字符串。

SDS 结构（如果没有特殊说明，代码采用的一律为 Redis 5.0 版本）

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
复制代码

• len 表示 SDS 的长度，使我们在获取字符串长度的时候可以在 O(1)情况下拿到，而不是像 C 那样需要遍历一遍字符串。
• alloc 可以用来计算 free 就是字符串已经分配的未使用的空间，有了这个值就可以引入预分配空间的算法了，而不需要使用者去考虑内存分配的问题。预分配在这个字符串对象内存小于 1M 的时候分配和 len 同样大小的内存，大于 1M 的时候分配 1M内存。
• buf 表示字符串数组

SDS 有五种长度，分别为sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64。其中从不使用sdshdr5，只是直接访问flags字节用的。

Redis 的字符串结构并没有抛弃 C字符串，这意味着它可以向下兼容 C 风格的字符串，可以重用 C 字符串函数。

链表

链表提供了高效的节点排重能力，以及顺序性的节点访问方式，而且可以通过增加节点来灵活地调整链表的长度。它是一种常用的数据结构，被内置在很多高级语言中。因为 C语言 并没有内置这种数据结构，所以 Redis 构建了自己的链表实现。

链表的节点

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;
复制代码

• prev 前置节点
• next 后置节点
• value 节点的值 多个 listNode 结构组成一个链表;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;
复制代码

• head 节点头指针
• tail 节点尾指针
• dup 用于复制链表节点所保存的值
• free 用于释放链表节点所保存的值
• match 用于对比链表节点所保存的值和另一个输入的值是否相等
• len 链表计数器

Redis 链表的特性;

• 双端；有 prev 和 next 获取某个节点的前置和后置都是 O(1)
• 无环；头结点的 prev 和尾节点的 next 都指向 NULL
• 链表计数器；获取链表的长度为 O(1)
• 多态；链表节点使用 void* 指针来保存节点的值，所以链表可以用于保存各种不同类型的值。

字典

字典中一个键（key）可以和一个值关联（value），这种关联的键和值我们称之为键值对。所以字典的每个键都是独一无二的，我们可以根据键在 O(1) 的时间复杂度下找到与之相关联的值。字典也是很多高级语言都内置的一种数据结构，但是 C语言并没有内置这种数据结构，因此 Redis 自己构建了字典的实现。

字典的内部是采用的哈希表结构：

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;
复制代码

• dictEntry 哈希表数组
• size 哈希表大小
• sizemask 哈希表大小掩码
• used 哈希表已有节点的数量

其中 table 是一个数组，数组中的每个元素都是指向 dictEntry 的指针。

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry
复制代码

• val 键
• union 值
• dictEntry 指向下个哈希表节点

哈希表在添加一个新的键值对的时候，程序会根据键值对的键计算出哈希索引值，然后根据索引值将包含键值对的哈希表节点放到哈希表数组的指定索引上。

当有两个或者以上的键被分配到哈希表数组的同一个索引上面时，会产生冲突。 Redis 的哈希表使用链地址法（separate chaining）来解决建冲突。

随着不断的执行，哈希表保存的键值对随之也会做多或者减少，为了让哈希表的负载因子维持在一个合理范围内，所以程序需要对哈希表的大小进行相应的扩展或者收缩。执行原理类似动态数组。当空间不够或者剩余的时候自动申请一块内存空间进行数据转移，在 Redis 中叫做 rehash。

跳跃表

跳跃表是一种有序的链性数据结构，通过维护层级 (level) 来达到快速访问节点的目的。平均查找复杂度为 O(logN)，最坏 O(N)。因为是链性结构，还支持顺序性操作。

关于 Redis 为什么采用跳跃表而不采用红黑树之前我写过一篇文章，所以就不在这细诉了，我觉得其主要原因不外乎两点，一是红黑树不易于实现，而且在频繁的添加修改之后，为了维持树的平衡还要进行左右旋转。二是红黑树查找虽然是 O(logN)，但是在进行区间查找中往往就做到不 O(logN) 了，甚至需要遍历整个树。跳表就不需要了，它只需要找到第一个节点然后根据链性结构的特点向下走就可以了。Redis 有序集合一般就是用的这种实现。

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

复制代码

zskiplistNode 为跳跃表节点:

• sds 元素
• score 分值
• backward 后退指针
• level 层级

zskiplist 为跳跃表:

• header 头结点
• tail 尾节点
• length 节点数量
• level 最大节点的层数

整数集合

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

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;
复制代码

• encoding 编码方式
• length 集合元素个数
• contents 保存集合数据的数组

当集合数据类型大于 int8_t 所表示的最大空间时，Redis 会自动为该集合升级。一旦升级，不支持降级。

压缩列表

压缩列表是一种为节约内存而开发的顺序性数据结构。常常被用作列表、哈希的底层实现。是由一系列特殊编码的连续内存块组成的。

总结

Redis 内部是由一系列对象组成的，字符串对象、列表对象、哈希表对象、集合对象有序集合对象。

字符串对象是唯一一个可以应用在上面所以对象中的，所以我们看到向一些 keys exprice 这种命令可以在针对所有 key 使用，因为所有 key 都是采用的字符串对象。 列表对象默认使用压缩列表为底层实现，当对象保存的元素数量大于 512 个或者是长度大于64字节的时候会转换为双端链表。

哈希对象也是优先使用压缩列表键值对在压缩列表中连续储存着，当对象保存的元素数量大于 512 个或者是长度大于64字节的时候会转换为哈希表。

集合对象可以采用整数集合或者哈希表，当对象保存的元素数量大于 512 个或者是有元素非整数的时候转换为哈希表。

有序集合默认采用压缩列表，当集合元素数量大于 128 个或者是元素成员长度大于 64 字节的时候转换为跳跃表。