Redis 是一个键值对数据库（key-value DB），数据库的值可以是字符串、集合、列表等多种类型的对象，而数据库的键则总是字符串对象。

以下内容摘自（但不仅限于，其他地方引用有相应标注）：
Redis 命令参考
Redis 设计与实现（第一版）
Redis 设计与实现（第二版）
Redis 设计与实现
Redis内部数据结构详解之跳跃表(skiplist)
Redis内部数据结构详解之字典(dict)
Redis中5种数据结构的使用场景介绍

前言

谈文章里的一些叫法？

• 宏观上：我们看到的是一些基本数据类型，如我们常用的哈希，列表，集合等；微观上：这此数据都是由Redis的底层（或称内部）数据结构来支撑的，比如字典，跳跃表；
• 我们管这种宏观的基本数据类型，比如哈希叫哈希（类型）键，我们管有序集合叫有序集合键；
• Redis 的每一种数据类型，比如字符串、列表、有序集，它们都拥有不只一种底层实现（Redis 内部称之为编码，encoding）

关于文章想带来什么？

• 宏观的基本数据类型VS底层数据结构的关系如何；
• 底层数据结构长什么样子（整数集合、压缩列表进一步划分，属于内存映射数据结构，本文不作详细描述，后续可以专门分析下它们是如何相比其他数据结构节约内存的）；
• 更多地，燃起对数据结构的一些兴趣；

Redis六种内部数据结构

• Sds (sds)
• 双端链表（linkedlist）
• 字典(dict)
• 跳跃表(skiplist)
• 整数集合(intset)
• 压缩列表(ziplist)

1. Sds

Sds （Simple Dynamic String，简单动态字符串）是 Redis 底层所使用的字符串表示，几乎所有的 Redis 模块中都用了 sds。Sds 在 Redis 中的主要作用有以下两个：

• 实现字符串对象（StringObject）；http://redisbook.com/preview/sds/content.html
• 在 Redis 程序内部用作 char* 类型的替代品；

主要特点：

Redis的简单动态字符串SDS对比C语言的字符串char*，有以下特性：

• 可以在O(1)的时间复杂度得到字符串的长度
• 可以高效的执行append追加字符串操作
• 二进制安全

应用场景：

• 其他模块（几乎每一个）都用到了 sds 类型值：用来保存数据库中的字符串值
• SDS 还被用作缓冲区（buffer）： 客户端传入服务器的协议内容，AOF 模块中的 AOF 缓冲区， 以及客户端状态中的输入缓冲区， 都是由 SDS 实现的

数据结构：

其中，类型 sds 是 char * 的别名（alias），而结构 sdshdr 则保存了 len 、 free 和 buf 三个属性

typedef char *sds;
struct sdshdr {
    // buf 已占用长度
    int len;

    // buf 剩余可用长度
    int free;

    // 实际保存字符串数据的地方
    char buf[];
};

为了易于理解，我们用一个 Redis 执行实例作为例子，解释一下，当执行以下代码时， Redis 内部发生了什么：

redis> SET msg "hello world"
OK
redis> APPEND msg " again!"
(integer) 18
redis> GET msg
"hello world again!"

1.键值对的键和值都以SDS对象保存：
键值对的键是一个字符串对象， 对象的底层实现是一个保存着字符串 "msg" 的 SDS 。
键值对的值也是一个字符串对象， 对象的底层实现是一个保存着字符串 "hello world" 的 SDS 。

2. SET 命令创建并保存 hello world 到一个 sdshdr 中，这个 sdshdr 的值如下：

struct sdshdr {
    len = 11;
    free = 0;
    buf = "hello world\0";
}

3.当执行 APPEND 命令时，相应的 sdshdr 被更新，字符串 " again!" 会被追加到原来的 "hello world" 之后，同时Redis 为 buf 创建了多于所需空间一倍的大小：

struct sdshdr {
    len = 18;
    free = 18;
    buf = "hello world again!\0                  ";     // 空白的地方为预分配空间，共 18 + 18 + 1 个字节
}

2. 双端链表

链表作为数组之外的一种常用序列抽象，是大多数高级语言的基本数据类型，因为 C 语言本身不支持链表类型，大部分 C 程序都会自己实现一种链表类型，Redis 也不例外 —— 实现了一个双端链表结构。

主要特点：

• 节点带有前驱和后继指针，访问前驱节点和后继节点的复杂度为 (O(1)) ，并且对链表的迭代可以在从表头到表尾和从表尾到表头两个方向进行；
• 链表带有指向表头和表尾的指针，因此对表头和表尾进行处理的复杂度为 (O(1)) ；
• 链表带有记录节点数量的属性，所以可以在 (O(1)) 复杂度内返回链表的节点数量（长度）；

应用场景：

除了实现列表类型以外，双端链表还被很多 Redis 内部模块所应用

• 事务模块使用双端链表依序保存输入的命令；
• 服务器模块使用双端链表来保存多个客户端；
• 订阅/发送模块使用双端链表来保存订阅模式的多个客户端；
• 事件模块使用双端链表来保存时间事件（time event）；

数据结构：

双端链表的实现由 listNode 和 list 两个数据结构构成：

其中， listNode 是双端链表的节点：

typedef struct listNode {

    // 前驱节点
    struct listNode *prev;

    // 后继节点
    struct listNode *next;

    // 值
    void *value;

} listNode;

而 list 则是双端链表本身：

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;

注意， listNode 的 value 属性的类型是 void * ，说明这个双端链表对节点所保存的值的类型不做限制。

Redis 列表使用两种数据结构作为底层实现：
1.双端链表
2.压缩列表
因为双端链表占用的内存比压缩列表要多，所以当创建新的列表键时，列表会优先考虑使用压缩列表作为底层实现，并且在有需要的时候，才从压缩列表实现转换到双端链表实现。

3. 字典

Redis 的字典使用哈希表作为底层实现（双哈希表）， 一个哈希表里面可以有多个哈希表节点， 而每个哈希表节点就保存了字典中的一个键值对。

主要特点：

Redis的字典是使用一个桶bucket，通过对key进行hash得到的索引值index，然后将key-value的数据存在桶的index位置，Redis处理hash碰撞的方式是链表，两个不同的key hash得到相同的索引值，那么就使用链表解决冲突。使用链表自然当存储的数据巨大的时候，字典不免会退化成多个链表，效率大大降低，Redis采用rehash的方式对桶进行扩容来解决这种退化。

参考：Redis内部数据结构详解之字典(dict)

小结：

• Redis中的字典数据结构使用哈希表来实现，用来存储key-value键值元素；
• 字典使用两个哈希表，一般只使用ht[0]，只有当Rehash时候才使用ht[1]；
• Redis 使用 MurmurHash2 算法来计算键的哈希值；
• 哈希表采用链表的方式解决键碰撞问题；
• 在对哈希表进行扩展或者收缩操作时， 程序需要将现有哈希表包含的所有键值对 rehash 到新哈希表里面， 并且这个 rehash 过程并不是一次性地完成的， 而是渐进式地完成的。

应用场景：

字典在 Redis 中的应用广泛，使用频率可以说和 SDS 以及双端链表不相上下，基本上各个功能模块都有用到字典的地方。
其中，字典的主要用途有以下两个：
1.实现数据库键空间（key space）；
2.用作 Hash 类型键的底层实现之一；

• 实现数据库键空间
  Redis 是一个键值对数据库，数据库中的键值对由字典保存：每个数据库都有一个对应的字典，这个字典被称之为键空间（key space）。

redis> SET msg "hello world"
OK

在数据库中创建一个键为 "msg" ， 值为 "hello world" 的键值对时， 这个键值对就是保存在代表数据库的字典里面的。

• 用作 Hash 类型键的底层实现之一
  Redis 的 Hash 类型键使用以下两种数据结构作为底层实现:

1. 字典；
2. 压缩列表；

当一个哈希键包含的键值对比较多， 又或者键值对中的元素都是比较长的字符串时， Redis 就会使用字典作为哈希键的底层实现。
举个例子， website 是一个包含 10086 个键值对的哈希键， 这个哈希键的键都是一些数据库的名字， 而键的值就是数据库的主页网址：

redis> HSET website Redis "www.g.cn"
(integer) 1
redis> HSET website Redis.io "www.g.cn"
(integer) 1
redis> HSET website MariaDB "www.g.cn"
(integer) 1
...

redis> HLEN website
(integer) 10086

redis> HGETALL website
1) "Redis"
2) "Redis.io"
3) "MariaDB"
4) "MariaDB.org"
5) "MongoDB"
6) "MongoDB.org"
# ...

website 键的底层实现就是一个字典， 字典中包含了 10086 个键值对：
其中一个键值对的键为 "Redis" ， 值为 "Redis.io" 。
另一个键值对的键为 "MariaDB" ， 值为 "MariaDB.org" ；
还有一个键值对的键为 "MongoDB" ， 值为 "MongoDB.org" ；

数据结构：

字典的数据结构和实现比较复杂，这里就针对一些比较有意思的特性直接得出结论：

Rehash的触发机制：dictAdd 在每次向字典添加新键值对之前，都会对工作哈希表ht[0]进行检查，如果used（哈希表中元素的数目）与size（桶的大小）比率ratio满足以下任一条件，将激活字典的Rehash机制：

• 自然 rehash ： ratio >= 1 ，且变量 dict_can_resize 为真。
• 强制 rehash ： ratio 大于变量 dict_force_resize_ratio （目前版本中， dict_force_resize_ratio 的值为 5 ）。

什么时候 dict_can_resize 会为假？

在前面介绍字典的应用时也说到过，数据库就是字典，数据库里的哈希类型键也是字典，当 Redis 使用子进程对数据库执行后台持久化任务时（比如执行 BGSAVE 或 BGREWRITEAOF 时），为了最大化地利用系统的 copy on write 机制，程序会暂时将 dict_can_resize 设为假，避免执行自然 rehash ，从而减少程序对内存的触碰（touch）。
当持久化任务完成之后，dict_can_resize 会重新被设为真。
另一方面，当字典满足了强制 rehash 的条件时，即使 dict_can_resize 不为真（有 BGSAVE 或 BGREWRITEAOF 正在执行），这个字典一样会被 rehash 。

Rehash执行过程：

• 1.创建一个比ht[0].used至少两倍的ht[1].table；2.将原ht[0].table中所有元素迁移到ht[1].table；3.清空原来ht[0]，将ht[1]替换成ht[0]。
• 渐进式Rehash主要由两个函数来进行：
  _dictRehashStep：当对字典进行添加、查找、删除、随机获取元素都会执行一次（被动 rehash），其每次在开始Rehash后，将ht[0].table的第一个不为空的索引上的所有节点全部迁移到ht[1].table;
  dictRehashMilliseconds:由 Redis 服务器常规任务程序（server cron job）执行，用于对数据库字典进行主动 rehash，以毫秒为单位，在一定时间内，以每次执行100步rehash操作。

上面关于 rehash 的章节描述了通过 rehash 对字典进行扩展（expand）的情况，如果哈希表的可用节点数比已用节点数大很多的话，那么也可以通过对哈希表进行 rehash 来收缩（shrink）字典。
收缩 rehash 和上面展示的扩展 rehash 的操作几乎一样，只是它创建了一个比 ht[0]->table 小的 ht[1]->table。

4. 跳跃表

跳跃表（skiplist ）是一种随机化的数据，由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》 中提出。事实上，这是早在1987年就诞生的东西。

主要特点：

• 跳跃表是一种随机化数据结构，查找、添加、删除操作都可以在对数期望时间（O(logn)）下完成，效率可以比拟平衡二叉树。
• 跳跃表目前在 Redis 的唯一作用，就是作为有序集类型的底层数据结构（之一，另一个构成有序集的结构是字典）。
• 它的设计巧妙和随机化的根源来自于：当插入每个节点时需要决定它所要占据的层数，而这个层数正是通过一个算法返回的随机层数值（Redis用ZSKIPLIST_MAXLEVEL来限制最高层数为32）；特别的，当概率因子ZSKIPLIST_P（性能最优的取值是0.5，或0.25）为0.5时，正好形同抛硬币的方式，即是：只要是正面就累加，直到遇见反面才停止，最后记录正面的次数就是这里说的随机层数；
  参考：
  https://blog.csdn.net/men_wen/article/details/70040026
  https://www.cnblogs.com/flyfy1/archive/2011/02/24/1963347.html（有个形象的比喻）
• 空间复杂度为 2n = O(n);跳表的高度期待为 Eh = O(log n)，跳跃表就是一个在空间复杂度为2n的基础上实现了查询等操作在O(logn)的时间复杂度完成的一个性能优秀的数据结构。
  参考：http://blog.sina.com.cn/s/blog_68f6d5370102uykh.html
• 有人将跳跃表分析为链表+二分查找，可以借鉴（因为本身链表是没有二分查找能力的——根本就在于没有索引访问能力，跳跃表利用多层链表的方式实现了类似索引的能力，就是多层，并且它是第三点说的随机的多层；这样很形象地将上层链表可以看成下层链表的索引，这样就可以快速得跳过很多节点进行比较；是一种空间来换取时间的做法）。网上有一个阿里的面试问题是这样问的：如何让链表的元素查询接近线性时间，其实就是指的跳跃表。
• 还有一种说法（未经证明）：如果单纯比较性能，跳跃表和红黑树可以说相差不大，但是加上并发的环境就不一样了，如果要更新数据，跳跃表需要更新的部分就比较少，锁的东西也就比较少，所以不同线程争锁的代价就相对少了，而红黑树有个平衡的过程，牵涉到大量的节点，争锁的代价也就相对较高了。性能也就不如前者了。不过这些对redis这个单进程单线程server来说都是浮云。

看了很多资料之后，突然觉得还是有个疑问，就是，为什么叫跳跃表（我感觉我还是没有懂彻底）？
跳跃表（skiplist）是一种有序数据结构， 它通过在每个节点中维持多个指向其他节点的指针， 从而达到快速访问节点的目的。跳跃表支持平均 O(\log N) 最坏 O(N) 复杂度的节点查找， 还可以通过顺序性操作来批量处理节点。
通过一些话我们来领会下跳跃的含义：

• “就好像火车，有快车有慢车；快车停得站少，慢车停得多。所以，从一个地方到另一个地方，我们需要先乘坐快车，之后换乘慢车。”
• “底层是一个普通的有序链表。每个更高层都充当下面列表的「快速跑道」”；参考：https://blog.csdn.net/daniel_ustc/article/details/20218489
• 让算法的效率“跳起来”！参考：https://www.cnblogs.com/flyfy1/archive/2011/02/24/1963347.html
  （里面贴的几个链接比较值得一看）

关于时间空间度？（目前我查阅了很多资料，始终未能找到有说服性的证明其时间复杂度为O(log n)的有效证明，好多都是生拉硬拽，有兴趣的可以一起讨论）

• （总体分析法）：注意比较次数，在每一条链表上我们可以发现最多比较两次，至少比较一次，所以比较次数不会超过 2LogN。所以比较的时间复杂度是 O(logN)；（https://www.xuebuyuan.com/2115228.html）
• （想象比较法）：可以把它相像成链表的二分查找：总共有n个元素，渐渐跟下去就是n,n/2,n/4,....n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数；最后剩余为1说明找到， 于是n/2^k取整后>=1，得出 k=log2n，需要k次（即log2n），即得复杂度；有人也把跳跃表比作一颗二叉树，可参考：http://courses.csail.mit.edu/6.046/spring04/handouts/skiplists.pdf
• （函数推演法）线段跳表 —— 跳表的一个拓展（https://wenku.baidu.com/view/7285945f804d2b160b4ec0a8.html）
• 原论文：http://www.cl.cam.ac.uk/teaching/0506/Algorithms/skiplists.pdf

查询时间复杂度O(logn)有多快？效率是极其高的

上面说了跳表的高度期待O(log n)，而Redis的跳跃表设定的高度限制是32层，可以反推出最理想最大的节点数量（即zskiplist最大的length）是2³²个。那么查询一个元素所需要花的时间就是log2 2³²，即只需要32次循环，相当惊人（对比O(n)的复杂度体会一下）。因为2³²是一个相当大的数字，即为4 294 967 296，如，2的32次方ms是多少天：49.41天。

应用场景：

和字典、链表或者字符串这几种在 Redis 中大量使用的数据结构不同，跳跃表在 Redis 的唯一作用，就是实现有序集数据类型。跳跃表将指向有序集的 score 值和 member 域的指针作为元素，并以 score 值为索引，对有序集元素进行排序。
参考：
https://www.kancloud.cn/kancloud/redisbook-first/63781
Lucene的跳跃表应用

数据结构：

https://blog.csdn.net/u014427196/article/details/52454462/ （可以通过图直观感受它的实现思路）

跳跃表是一种随机化数据结构，基于并联的链表（简单的说，就是一个多层链表，你可以把每层看成一个链表），其效率可以比拟平衡二叉树，查找、删除、插入等操作都可以在对数期望时间内完成，对比平衡树，跳跃表的实现要简单直观很多。

以下是个典型的跳跃表例子（图片来自维基百科）：

从图中可以看出跳跃表主要有以下几个部分构成：
1、 表头head：负责维护跳跃表的节点指针
2、 节点node：实际保存元素值，每个节点有一层或多层
3、 层level：保存着指向该层下一个节点的指针
4、 表尾tail：全部由null组成
跳跃表的遍历总是从高层开始，然后随着元素值范围的缩小，慢慢降低到低层。

Redis作者为了适合自己功能的需要，对原来的跳跃表进行了一下修改：

1、 允许重复的score值：多个不同的元素(member)的score值可以相同，若score值相同时，需要对比member，按字典排序存储在跳表结构中。
2、 span存在于forward中，这个跨度字段的出现有助于快速计算元素在整个集合中的排名
3、 每个节点都有一个高度为1层的前驱指针forward，用于从底层表尾向表头方向遍历：当执行 ZREVRANGE 或 ZREVRANGEBYSCORE这类以逆序处理有序集的命令时，就会用到这个属性。
4、 dict维护了skiplist的元素值（key）和分数（value）用于快读的查找元素对应的分值以及判断元素是否存在。

跳跃表数据结构如下:

//跳跃表节点
typedef struct zskiplistNode {
    // member 对象
    robj *obj;
    // 分值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 这个层跨越的节点数量
        unsigned int span;
    } level[];
} zskiplistNode;
 
//跳跃表
typedef struct zskiplist {
    // 头节点，尾节点
    struct zskiplistNode *header, *tail;
    // 节点数量
    unsigned long length;
    // 目前表内节点的最大层数
    int level;
} zskiplist;

//有序集合
typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

Redis 使用跳跃表作为有序集合键的底层实现之一： 如果一个有序集合包含的元素数量比较多， 又或者有序集合中元素的成员（member）是比较长的字符串时， Redis 就会使用跳跃表来作为有序集合键的底层实现。

举个例子， fruit-price 是一个有序集合键， 这个有序集合以水果名为成员， 水果价钱为分值， 保存了 130 款水果的价钱：

redis> ZRANGE fruit-price 0 2 WITHSCORES
1) "banana"
2) "5"
3) "cherry"
4) "6.5"
5) "apple"
6) "8"

redis> ZCARD fruit-price
(integer) 130

fruit-price 有序集合的所有数据都保存在一个跳跃表里面， 其中每个跳跃表节点（node）都保存了一款水果的价钱信息， 所有水果按价钱的高低从低到高在跳跃表里面排序：
跳跃表的第一个元素的成员为 "banana" ， 它的分值为 5 ；
跳跃表的第二个元素的成员为 "cherry" ， 它的分值为 6.5 ；
跳跃表的第三个元素的成员为 "apple" ， 它的分值为 8 ；

内存映射数据结构

虽然内部数据结构非常强大，但是创建一系列完整的数据结构本身也是一件相当耗费内存的工作，当一个对象包含的元素数量并不多，或者元素本身的体积并不大时，使用代价高昂的内部数据结构并不是最好的办法。为了解决这一问题，Redis在条件允许的情况下，会使用内存映射数据结构来代替内部数据结构。

内存映射数据结构可以为用户节省大量的内存。不过，因为内存映射数据结构的编码和操作方式要比内部数据结构要复杂得多，所以内存映射数据结构所占用的CPU 时间会比作用类似的内部数据结构要多。
这一部分将对Redis目前正在使用的两种内存映射数据结构进行介绍。
参考： redis内存映射数据结构

整数集合（intset）：用于有序、无重复地保存多个整数值，它会根据元素的值，自动选择该用什么长度的整数类型来保存元素。
压缩列表（Ziplist）：是由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构，它可以保存字符数组或整数值，它还是哈希键、列表键和有序集合键的底层实现之一。

5. 整数集合

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

举个例子， 如果我们创建一个只包含五个元素的集合键， 并且集合中的所有元素都是整数值， 那么这个集合键的底层实现就会是整数集合：

redis> SADD numbers 1 3 5 7 9
(integer) 5

redis> OBJECT ENCODING numbers
"intset"

6. 压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一。

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

比如说， 执行以下命令将创建一个压缩列表实现的列表键：

redis> RPUSH lst 1 3 5 10086 "hello" "world"
(integer) 6
redis> OBJECT ENCODING lst
"ziplist"

因为列表键里面包含的都是 1 、 3 、 5 、 10086 这样的小整数值， 以及 "hello" 、 "world" 这样的短字符串。

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

Redis五种基本数据类型

• String——字符串
• Hash——字典
• List——列表
• Set——集合
• Sorted Set——有序集合

基本数据类型与底层数据结构的关系

1. String——字符串

String 数据结构是简单的 key-value 类型，value 不仅可以是 String，也可以是数字（当数字类型用 Long 可以表示的时候encoding 就是整型，其他都存储在 sdshdr 当做字符串）。

字符串编码

字符串类型分别使用 REDIS_ENCODING_INT 和 REDIS_ENCODING_RAW 两种编码：

• REDIS_ENCODING_INT 使用 long 类型来保存 long 类型值。
• REDIS_ENCODING_RAW 则使用 sdshdr 结构来保存 sds （也即是 char* )、 long long 、 double 和 long double类型值。
  换句话来说，在 Redis 中，只有能表示为 long 类型的值，才会以整数的形式保存，其他类型的整数、小数和字符串，都是用 sdshdr 结构来保存。
  

（字符串）是 Redis 使用得最为广泛的数据类型，它除了是 SET 、 GET等命令的操作对象之外，数据库中的所有键，以及执行命令时提供给 Redis 的参数，都是用这种类型保存的。

2. Hash——字典

在 Memcached 中，我们经常将一些结构化的信息打包成 hashmap，在客户端序列化后存储为一个字符串的值（一般是 JSON 格式），比如用户的昵称、年龄、性别、积分等。这时候在需要修改其中某一项时，通常需要将字符串（JSON）取出来，然后进行反序列化，修改某一项的值，再序列化成字符串（JSON）存储回去。简单修改一个属性就干这么多事情，消耗必定是很大的，也不适用于一些可能并发操作的场合（比如两个并发的操作都需要修改积分）。而 Redis 的 Hash 结构可以使你像在数据库中 Update 一个属性一样只修改某一项属性值。

（哈希表）是 HSET 、 HLEN等命令的操作对象，它使用 REDIS_ENCODING_ZIPLIST 和 REDIS_ENCODING_HT 两种编码方式

https://www.kancloud.cn/kancloud/redisbook-first/63788

字典编码的哈希表

当哈希表使用字典编码时，程序将哈希表的键（key）保存为字典的键，将哈希表的值（value）保存为字典的值。哈希表所使用的字典的键和值都是字符串对象。

压缩列表编码的哈希表

当使用 REDIS_ENCODING_ZIPLIST 编码哈希表时，程序通过将键和值一同推入压缩列表，从而形成保存哈希表所需的键-值对结构。

image.png

当创建新的哈希表时，默认是使用压缩列表作为底层数据结构的，因为省内存呀。只有当触发了阈值才会转为字典

哈希表中某个键或者值的长度大于server.hash_max_ziplist_value（默认为64）
压缩列表中的节点数量大于server.hash_max_ziplist_entries(默认为512)

3. List——列表

List 说白了就是链表（redis 使用双端链表实现的 List），相信学过数据结构知识的人都应该能理解其结构。使用 List 结构，我们可以轻松地实现最新消息排行等功能（比如新浪微博的 TimeLine ）。List 的另一个应用就是消息队列，可以利用 List 的 *PUSH 操作，将任务存在 List 中，然后工作线程再用 POP 操作将任务取出进行执行。Redis 还提供了操作 List 中某一段元素的 API，你可以直接查询，删除 List 中某一段的元素

REDIS_LIST （列表）是 LPUSH 、 LRANGE 等命令的操作对象，它使用 REDIS_ENCODING_ZIPLIST 和 REDIS_ENCODING_LINKEDLIST 这两种方式编码：

创建新列表时 Redis 默认使用 REDIS_ENCODING_ZIPLIST 编码，当以下任意一个条件被满足时，列表会被转换成 REDIS_ENCODING_LINKEDLIST 编码：

试图往列表新添加一个字符串值，且这个字符串的长度超过 server.list_max_ziplist_value （默认值为 64 ）。
ziplist 包含的节点超过 server.list_max_ziplist_entries （默认值为 512 ）。

因为列表本身的操作和底层实现基本一致，讲讲阻塞（列表，其实就是队列）：

BLPOP 、 BRPOP 和 BRPOPLPUSH lpush] 三个命令都可能造成客户端被阻塞，将这些命令统称为列表的阻塞原语。
比如，POP命令是删除一个节点，那么当没有节点的时候，客户端会阻塞直到一个元素添加进来，然后再执行POP命令。

参考：https://www.kancloud.cn/kancloud/redisbook-first/63789

4. Set——集合

Set 就是一个集合，集合的概念就是一堆不重复值的组合。利用 Redis 提供的 Set 数据结构，可以存储一些集合性的数据。比如在微博应用中，可以将一个用户所有的关注人存在一个集合中，将其所有粉丝存在一个集合。因为 Redis 非常人性化的为集合提供了求交集、并集、差集等操作，那么就可以非常方便的实现如共同关注、共同喜好、二度好友等功能，对上面的所有集合操作，你还可以使用不同的命令选择将结果返回给客户端还是存集到一个新的集合中。

REDIS_SET （集合）是 SADD 、 SRANDMEMBER 等命令的操作对象，它使用 REDIS_ENCODING_INTSET 和 REDIS_ENCODING_HT 两种方式编码：

编码的选择
第一个添加到集合的元素，决定了创建集合时所使用的编码：

如果第一个元素可以表示为 long long 类型值（也即是，它是一个整数）， 那么集合的初始编码为 REDIS_ENCODING_INTSET 。
否则，集合的初始编码为 REDIS_ENCODING_HT 。

编码的切换
如果一个集合使用 REDIS_ENCODING_INTSET 编码，那么当以下任何一个条件被满足时，这个集合会被转换成 REDIS_ENCODING_HT 编码：

intset 保存的整数值个数超过 server.set_max_intset_entries （默认值为 512 ）。
试图往集合里添加一个新元素，并且这个元素不能被表示为 long long 类型（也即是，它不是一个整数）。

Redis 集合类型命令的实现，主要是对 intset 和 dict 两个数据结构的操作函数的包装，以及一些在两种编码之间进行转换的函数

5. Sorted Set——有序集合

和Sets相比，Sorted Sets是将 Set 中的元素增加了一个权重参数 score，使得集合中的元素能够按 score 进行有序排列，比如一个存储全班同学成绩的 Sorted Sets，其集合 value 可以是同学的学号，而 score 就可以是其考试得分，这样在数据插入集合的时候，就已经进行了天然的排序。另外还可以用 Sorted Sets 来做带权重的队列，比如普通消息的 score 为1，重要消息的 score 为2，然后工作线程可以选择按 score 的倒序来获取工作任务。让重要的任务优先执行。
应用场景：
1.带有权重的元素，比如一个游戏的用户得分排行榜
2.比较复杂的数据结构，一般用到的场景不算太多

（有序集）是 ZADD 、 ZCOUNT 等命令的操作对象，它使用 REDIS_ENCODING_ZIPLIST 和 REDIS_ENCODING_SKIPLIST 两种方式编码：

编码的转换
对于一个 REDIS_ENCODING_ZIPLIST 编码的有序集，只要满足以下任一条件，就将它转换为 REDIS_ENCODING_SKIPLIST 编码：

ziplist 所保存的元素数量超过服务器属性 server.zset_max_ziplist_entries 的值（默认值为 128 ）
新添加元素的 member 的长度大于服务器属性 server.zset_max_ziplist_value 的值（默认值为 64 ）

了解两种编码实现的方式和效率（还是比较有意思），请参考：https://www.kancloud.cn/kancloud/redisbook-first/63791

6. 对象处理机制（RedisObject）

分析：

在 Redis 的命令中，用于对键（key）进行处理的命令占了很大一部分，而对于键所保存的值的类型（后简称“键的类型”），键能执行的命令又各不相同。

比如说，LPUSH 和 LLEN 只能用于列表键，而 SADD 和 SRANDMEMBER 只能用于集合键，等等。

另外一些命令，比如 DEL 、 TTL 和 TYPE ，可以用于任何类型的键，但是，要正确实现这些命令，必须为不同类型的键设置不同的处理方式：比如说，删除一个列表键和删除一个字符串键的操作过程就不太一样。

以上的描述说明，Redis 必须让每个键都带有类型信息，使得程序可以检查键的类型，并为它选择合适的处理方式。

另外，在前面介绍各个底层数据结构时有提到，Redis 的每一种数据类型，比如字符串、列表、有序集，它们都拥有不只一种底层实现（Redis 内部称之为编码，encoding），这说明，每当对某种数据类型的键进行操作时，程序都必须根据键所采取的编码，进行不同的操作。

比如说，集合类型就可以由字典和整数集合两种不同的数据结构实现，但是，当用户执行 SADD命令时，他/她应该不必关心集合使用的是什么编码，只要 Redis 能按照 SADD 命令的指示，将新元素添加到集合就可以了。
这说明，操作数据类型的命令除了要对键的类型进行检查之外，还需要根据数据类型的不同编码进行多态处理。

结论：

为了解决以上问题，Redis 构建了自己的类型系统，这个系统的主要功能包括：

• redisObject 对象。
• 基于 redisObject 对象的类型检查。
• 基于 redisObject 对象的显式多态函数。
• 对 redisObject 进行分配、共享和销毁的机制。

数据结构：

redisObject 是 Redis 类型系统的核心，数据库中的每个键、值，以及 Redis 本身处理的参数，都表示为这种数据类型。

redisObject 的定义位于 redis.h ：

/*
 * Redis 对象
 */
typedef struct redisObject {

    // 类型
    unsigned type:4;

    // 对齐位
    unsigned notused:2;

    // 编码方式
    unsigned encoding:4;

    // LRU 时间（相对于 server.lruclock）
    unsigned lru:22;

    // 引用计数
    int refcount;

    // 指向对象的值
    void *ptr;

} robj;

type 、 encoding 和 ptr 是最重要的三个属性。

type 记录了对象所保存的值的类型，它的值可能是以下常量的其中一个（定义位于 redis.h）：

/*
对象类型
*/
#define REDIS_STRING 0 // 字符串
#define REDIS_LIST 1 // 列表
#define REDIS_SET 2 // 集合
#define REDIS_ZSET 3 // 有序集
#define REDIS_HASH 4 // 哈希表

encoding 记录了对象所保存的值的编码，它的值可能是以下常量的其中一个（定义位于 redis.h）：

/*
对象编码
*/
#define REDIS_ENCODING_RAW 0 // 编码为字符串
#define REDIS_ENCODING_INT 1 // 编码为整数
#define REDIS_ENCODING_HT 2 // 编码为哈希表
#define REDIS_ENCODING_ZIPMAP 3 // 编码为 zipmap
#define REDIS_ENCODING_LINKEDLIST 4 // 编码为双端链表
#define REDIS_ENCODING_ZIPLIST 5 // 编码为压缩列表
#define REDIS_ENCODING_INTSET 6 // 编码为整数集合
#define REDIS_ENCODING_SKIPLIST 7 // 编码为跳跃表

ptr 是一个指针，指向实际保存值的数据结构，这个数据结构由 type 属性和 encoding 属性决定。

小结

• Redis 使用自己实现的对象机制来实现类型判断、命令多态和基于引用计数的垃圾回收。
• 一种 Redis 类型的键可以有多种底层实现。
• Redis 会预分配一些常用的数据对象，并通过共享这些对象来减少内存占用，和避免频繁地为小对象分配内存