Redis基本数据结构

Redis 有 5 种基础数据结构：string(字符串)、list(列表)、hash(字典)、set(集合) 和 zset(有序集合)，这 5 种是 Redis 相关知识中最基础、最重要的！

引

每种数据结构都有自己底层的内部编码实现，而且是多种实现，这样Redis会在合适的场景选择合适的内部编码。

可以看到每种数据结构都有两种以上的内部编码实现，例如string数据结构就包含了raw、int和embstr三种内部编码。

同时，有些内部编码可以作为多种外部数据结构的内部实现，例如ziplist就是hash、list和zset共有的内部编码。——JavaGuide

Redis 文档、在线 Redis 命令练习

正文

String 字符串

Redis 中的字符串是可变字符串，底层实现类似于 Java 中的 ArrayList ，有一个字符数组：

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
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[];
};

同样的一组结构 Redis 使用泛型定义了好多次，当字符串比较短的时候，len 和 alloc 可以使用 byte 和 short 来表示，这是为了对内存做极致的优化，不同长度的字符串使用不同的结构体来表示。

PS：Redis 规定了字符串的长度不得超过 512 MB。

常用操作

• SET key value插入相同 key 的键值对会覆盖旧的
• GET key获取对应的 value
• EXISTS key是否存在、DEL key删除键值对
• MSET key1 value1 key2 value2 ...批量 SET
• MGET key1 key2 ...批量GET
• EXPIRE key time time秒后过期删除
• SETEX key time value等价于 SET + EXPIRE
• SETNX key value如果 key 存在则 SET 失败
• INCR key [n]为一个整数 Value 自增，默认自增 1，可以传参自增 n
• GETSET key value2为 key 设置新的 value2 并返回旧的value
• 。。。

value 可以是任何种类的字符串、二进制数据、JSON 化的对象、甚至是图片。。

List 列表

底层采用 压缩列表ziplist 或 linkedlist 结构，linkedlist 实现类似于 Java 的 LinkedList ，采用双向链表实现，保证了插入/删除的速度，但索引定位时间是个 O(n)：

/* Node, List, and Iterator are the only data structures used currently. */

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

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;

常用操作

• LPUSH listname value / RPUSH listname value 分别向 list 的表头和表尾添加新元素
• LRANGE listname start end 取出 [start,end] 索引范围内的元素，索引负数表示倒数
• LINDEX listname index 类似于 Java 链表操作的get(int index)

list 还实现了队列，先进先出的特点可以用于消息队列、异步处理。。可以确保元素的访问顺序：

> RPUSH books python java golang
(integer) 3
> LPOP books
"python"
> LPOP books
"java"
> LPOP books
"golang"
> LPOP books
(nil)

list 还实现了栈，确保了先进后出的特点：

> RPUSH books python java golang
> RPOP books
"golang"
> RPOP books
"java"
> RPOP books
"python"
> RPOP books
(nil)

Hash 字典

采用 ziplist(压缩列表) 或 hashtable 实现，其中 hashtable 类似于 Java8 之前的 HashMap，采用数组 + 链表的拉链法解决 hash 冲突：

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 结构
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

table 是一个数组，数组中的每个元素都是一个 dictEntry 结构的指针，这个 dictEntry 保存着一个键值对：

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

字典结构的内部包含两个 hashtable ，通常情况下只有一个 hashtable 是有值的，但是在字典扩容/缩容的时候，需要分配新的 hashtable ，然后进行 渐进式搬迁。

渐进式 rehash

字典扩容需要申请新的数组，将旧数组中的所有链表元素重新计算插入位置，并搬迁到新的数组中，是一个 O(n) 时间的操作，Redis 作为单线程应用，很难去承受这个耗时的操作，所以 Redis 采用了 渐进式 rehash 逐步搬迁的方式：

渐进式 rehash 在 rehash 的时候，同时保留新旧两个 hash 结构，查询会分别去两个 hash 结构中进行，然后再后续的定时任务以及 hash 操作指令中，循序渐进的把旧字典中的内容迁移到新字典中，当全部迁移完毕才会用新的 hash 结构取代旧的。

何时扩容？

一般当 hash 表中的元素个数等于第一维数组的长度时，开始扩容，扩容到原数组大小的 2 倍。如果 Redis 正在进行 bgsave(持久化)，Redis 尽量不去扩容，但是如果元素个数达到了第一维数组长度的 5 倍，会强制扩容。

顺便提一下，当 hash 表中的元素个数少于数组长度的 10% ，会进行缩容操作，且不会考虑 bgsave。

常用操作

• HSET hashname key value向 hashname 字典中插入键值对，如果 key 不存在成功插入返回 1 ，key 存在成功更新(覆盖)返回 0
• HGET hashname key从 hashname 字典中取出 key 的 value，HGETALL hashname取出 hashname 字典中所有键值对(key value 间隔出现)
• HMSET hashname key1 value1 key2 value2 ...成功批量 SET 返回 OK

SET 集合

功能上类似于 Java 中的 HashSet ，内部的键值对是无序、唯一的，实现是 intset+hashtable，hashtable 就是一个标准拉链法解决冲突的哈希表，但是这个表中所有的 value 都是 null 。inset 就是一个数组：

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

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

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

} intset;

当集合中元素全部都是整形、且数量不超过 512 个的时候用 intset 存储实现，否则就是用 hashtable 存储实现。

常用操作

• SADD setname key1 key2 ...添加一个或多个 key ，相同的 key 会被忽略
• SMEMBERS setname拿到集合中所有 key ，是无序的
• SISMEMBER setname key key 是否存在
• SCARD setname 获取 key 的个数
• SPOP setname弹出一个

ZSET 有序列表

有序列表的底层实现，当集合中元素个数小于 128 个、且所有元素小于 64 字节时，仍然采用 ziplist 实现，每个 key 和其对应的 score 紧挨着。

否则采用 skiplist跳表 实现，效果类似于 Java 中 SortedSet 和 HashMap 的集合体，一方面是一个 Set 保证了内部 key 的唯一性，另一方面每个 key 都有可以映射到一个 double 类型的 score 值，用来代表排序的权重。

“跳表”数据结构，比较复杂：

想象你是一家创业公司的老板，刚开始只有几个人，大家都平起平坐。后来随着公司的发展，人数越来越多，团队沟通成本逐渐增加，渐渐地引入了组长制，对团队进行划分，于是有一些人又是员工又有组长的身份。

再后来，公司规模进一步扩大，公司需要再进入一个层级：部门。于是每个部门又会从组长中推举一位选出部长。

跳跃表就类似于这样的机制，最下面一层所有的元素都会串起来，都是员工，然后每隔几个元素就会挑选出一个代表，再把这几个代表使用另外一级指针串起来。然后再在这些代表里面挑出二级代表，再串起来。最终形成了一个金字塔的结构。

想一下你目前所在的地理位置：亚洲 > 中国 > 某省 > 某市 > ….，就是这样一个结构！

​ ——JavaGuide

推荐阅读：redis zset底层数据结构

常用操作

• ZADD zsetname score key添加元素，并且元素有一个对应的权重值 socre
• ZREM zsetname key删除 key
• ZRANGE zsetname start end按照 score 递增排序，列出[start,end]索引区间里的 key，索引是负数代表倒数
• ZREVRANGE zsetname start end按照 score 递减排序，列出[start,end]索引区间里的 key，索引是负数代表倒数
• ZCARD zsetname获取 key 的个数，类似于 count()
• ZSCORE zsetname key获取 key 对应的 score
• ZRANK zsetname key获取 key 的排名
• ZRANGEBYSCORE zsetname score1 score2获取[score1,score2]区间里的 key
• ZRANGEBYSCORE zsetname -inf score withscores获取[- ∞ ,score]分值区间里的 key 及其对应的 score 间隔出现，-inf 负无穷

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github