Redis5种常见数据结构：字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted Set)，不同结构有不同的底层实现、特点和运用场景。

SDS(simple dynamic string)

定义

Redis是用C语言写的，但是Redis并没有使用C的字符串表示（C是字符串是以空字符结尾的字符数组），而是自己构建了一种简单动态字符串（simple dynamic string，SDS）的抽象类型，并作为Redis的默认字符串表示。在Redis中，包含字符串值的键值对底层都是用SDS实现的。👉sds.h

len：记录当前已使用的字节数（不包括’’），获取SDS长度的复杂度为O(1)alloc：记录当前字节数组总共分配的字节数量（不包括’’）flags：标记当前字节数组的属性，是sdshdr8还是sdshdr16等，flags值的定义可以看下面代码buf：字节数组，用于保存字符串，包括结尾空白字符’’

SDS与C字符串的区别

C语言使用长度为N+1的字符数组来表示长度为N的字符串，字符数组的最后一个元素为空字符’’，但是这种简单的字符串表示方法并不能满足Redis对于字符串在安全性、效率以及功能方面的要求，那么使用SDS，会有哪些好处呢

常数复杂度获取字符串长度

C字符串不记录字符串长度，获取长度必须遍历整个字符串，复杂度为O(N)；而SDS结构中本身就有记录字符串长度的len属性，所有复杂度为O(1)。Redis将获取字符串长度所需的复杂度从O(N)降到了O(1)，确保获取字符串长度的工作不会成为Redis的性能瓶颈

杜绝缓冲区溢出，减少修改字符串时带来的内存重分配次数

C字符串不记录自身的长度，每次增长或缩短一个字符串，都要对底层的字符数组进行一次内存重分配操作。如果是拼接append操作之前没有通过内存重分配来扩展底层数据的空间大小，就会产生缓存区溢出；如果是截断trim操作之后没有通过内存重分配来释放不再使用的空间，就会产生内存泄漏而SDS通过未使用空间解除了字符串长度和底层数据长度的关联，3.0版本是用free属性记录未使用空间，3.2版本则是alloc属性记录总的分配字节数量。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化的空间分配策略，解决了字符串拼接和截取的空间问题

二进制安全

C字符串中的字符必须符合某种编码，除了字符串的末尾，字符串里面是不能包含空字符的，否则会被认为是字符串结尾，这些限制了C字符串只能保存文本数据，而不能保存像图片这样的二进制数据而SDS的API都会以处理二进制的方式来处理存放在buf数组里的数据，不会对里面的数据做任何的限制。SDS使用len属性的值来判断字符串是否结束，而不是空字符

兼容部分C字符串函数

虽然SDS的API是二进制安全的，但还是像C字符串一样以空字符结尾，目的是为了让保存文本数据的SDS可以重用一部分C字符串的函数

字典dict

定义

字典，又称为符号表（symbol table）、关联数组（aSSOciative array）或映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构。字典中的每一个键都是唯一的，可以通过键查找与之关联的值，并对其修改或删除 Redis的键值对存储就是用字典实现的，散列（Hash）的底层实现之一也是字典

👉dict.h

通过拉链解决hash冲突

/*Hash表一个节点包含Key,Value数据对 */
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; /* 指向下一个节点, 链接表的方式解决Hash冲突 */
} dictEntry;
 
/* 存储不同数据类型对应不同操作的回调函数 */
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;
 
typedef struct dictht {
    dictEntry **table; /* dictEntry*数组,Hash表 */
    unsigned long size; /* Hash表总大小 */
    unsigned long sizemask; /* 计算在table中索引的掩码, 值是size-1 */
    unsigned long used; /* Hash表已使用的大小 */
} dictht;
 
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2]; /* 两个hash表,rehash时使用*/
    long rehashidx; /* rehash的索引, -1表示没有进行rehash */
    int iterators; /*  */
} dict;

链表(ListNode)

定义

链表是一种比较常见的数据结构了，特点是易于插入和删除、内存利用率高、且可以灵活调整链表长度，但随机访问困难。许多高级编程语言都内置了链表的实现，但是C语言并没有实现链表，所以Redis实现了自己的链表数据结构链表在Redis中应用的非常广，列表（List）的底层实现就是链表。此外，Redis的发布与订阅、慢查询、监视器等功能也用到了链表👉adlist.h


# 节点
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点值
    void *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;

每个节点listNode可以通过prev和next指针分布指向前一个节点和后一个节点组成双端链表，同时每个链表还会有一个list结构为链表提供表头指针head、表尾指针tail、以及链表长度计数器len，还有三个用于实现多态链表的类型特定函数

dup：用于复制链表节点所保存的值

free：用于释放链表节点所保存的值

match：用于对比链表节点所保存的值和另一个输入值是否相等

结构图

特点

双端链表：带有指向前置节点和后置节点的指针，获取这两个节点的复杂度为O(1)
无环：表头节点的prev和表尾节点的next都指向NULL，对链表的访问以NULL结束
链表长度计数器：带有len属性，获取链表长度的复杂度为O(1)
多态：链表节点使用 void*指针保存节点值，可以保存不同类型的值

跳跃表

定义

跳跃表其实可以把它理解为多层的链表，它有如下的性质

多层的结构组成，每层是一个有序的链表
最底层（level 1）的链表包含所有的元素
跳跃表的查找次数近似于层数，时间复杂度为O(logn)，插入、删除也为 O(logn)
跳跃表是一种随机化的数据结构(通过抛硬币来决定层数)

那么如何来理解跳跃表呢，我们从最底层的包含所有元素的链表开始，给定如下的链表

然后我们每隔一个元素，把它放到上一层的链表当中，这里我把它叫做上浮（注意，科学的办法是抛硬币的方式，来决定元素是否上浮到上一层链表，我这里先简单每隔一个元素上浮到上一层链表，便于理解），操作完成之后的结构如下

查找元素的方法是这样，从上层开始查找，大数向右找到头，小数向左找到头，例如我要查找17，查询的顺序是：13 -> 46 -> 22 -> 17；如果是查找35，则是 13 -> 46 -> 22 -> 46 -> 35；如果是54，则是 13 -> 46 -> 54

上面是查找元素，如果是添加元素，是通过抛硬币的方式来决定该元素会出现到多少层，也就是说它会有 1/2的概率出现第二层、1/4 的概率出现在第三层……

跳跃表节点的删除和添加都是不可预测的，很难保证跳表的索引是始终均匀的，抛硬币的方式可以让大体上是趋于均匀的

假设我们已经有了上述例子的一个跳跃表了，现在往里面添加一个元素18，通过抛硬币的方式来决定它会出现的层数，是正面就继续，反面就停止，假如我抛了2次硬币，第一次为正面，第二次为反面

跳跃表的删除很简单，只要先找到要删除的节点，然后顺藤摸瓜删除每一层相同的节点就好了

跳跃表维持结构平衡的成本是比较低的，完全是依靠随机，相比二叉查找树，在多次插入删除后，需要Rebalance来重新调整结构平衡

实现

Redis的跳跃表实现是由redis.h/zskiplistNode和redis.h/zskiplist（3.2版本之后redis.h改为了server.h）两个结构定义，zskiplistNode定义跳跃表的节点，zskiplist保存跳跃表节点的相关信息

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    // 成员对象 （robj *obj;）
    sds ele;
    // 分值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        // 跨度实际上是用来计算元素排名(rank)的，在查找某个节点的过程中，将沿途访过的所有层的跨度累积起来，得到的结果就是目标节点在跳跃表中的排位
        unsigned long span;
    } level[];
} zskiplistNode;

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

假设我们现在展示一个跳跃表，有四个节点，节点的高度分别是2、1、4、3

zskiplist的头结点不是一个有效的节点，它有ZSKIPLIST_MAXLEVEL层(32层)，每层的forward指向该层跳跃表的第一个节点，若没有则为NULL，在Redis中，上面的跳跃表结构如下

每个跳跃表节点的层数在1-32之间
一个跳跃表中，节点按照分值大小排序，多个节点的分值是可以相同的，相同时，节点按成员对象大小排序
每个节点的成员变量必须是唯一的

整数集合

整数集合（intset）是Redis用于保存整数值的集合抽象数据结构，可以保存类型为int16_t、int32_t、int64_t的整数值，并且保证集合中不会出现重复元素整数集合是集合（Set）的底层实现之一，如果一个集合只包含整数值元素，且元素数量不多时，会使用整数集合作为底层实现

定义

整数集合的定义为inset.h/inset

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

contents数组：整数集合的每个元素在数组中按值的大小从小到大排序，且不包含重复项
length记录整数集合的元素数量，即contents数组长度
encoding决定contents数组的真正类型，如INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64

整数集合的升级

当想要添加一个新元素到整数集合中时，并且新元素的类型比整数集合现有的所有元素的类型都要长，整数集合需要先进行升级（upgrade），才能将新元素添加到整数集合里面。每次想整数集合中添加新元素都有可能会引起升级，每次升级都需要对底层数组已有的所有元素进行类型转换升级添加新元素：

根据新元素类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
把数组现有的元素都转换成新元素的类型，并将转换后的元素放到正确的位置，且要保持数组的有序性
添加新元素到底层数组

整数集合的升级策略可以提升整数集合的灵活性，并尽可能的节约内存另外，整数集合不支持降级，一旦升级，编码就会一直保持升级后的状态

压缩列表

压缩列表（ziplist）是为了节约内存而设计的，是由一系列特殊编码的连续内存块组成的顺序性（sequential）数据结构，一个压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者一个整数值压缩列表是列表（List）和散列（Hash）的底层实现之一，一个列表只包含少量列表项，并且每个列表项是小整数值或比较短的字符串，会使用压缩列表作为底层实现（在3.2版本之后是使用quicklist实现）

压缩列表的构成

一个压缩列表可以包含多个节点（entry），每个节点可以保存一个字节数组或者一个整数值

各部分组成说明如下

zlbytes：记录整个压缩列表占用的内存字节数，在压缩列表内存重分配，或者计算zlend的位置时使用
zltail：记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过该偏移量，可以不用遍历整个压缩列表就可以确定表尾节点的地址
zllen：记录压缩列表包含的节点数量，但该属性值小于UINT16_MAX（65535）时，该值就是压缩列表的节点数量，否则需要遍历整个压缩列表才能计算出真实的节点数量
entryX：压缩列表的节点
zlend：特殊值0xFF（十进制255），用于标记压缩列表的末端

压缩列表节点的构成

每个压缩列表节点可以保存一个字节数字或者一个整数值，结构如下

previous_entry_ength：记录压缩列表前一个字节的长度
encoding：节点的encoding保存的是节点的content的内容类型
content：content区域用于保存节点的内容，节点内容类型和长度由encoding决定

redis五种数据结构的实现

redis对象

redis中并没有直接使用以上所说的各种数据结构来实现键值数据库，而是基于一种对象，对象底层再间接的引用上文所说的具体的数据结构。

字符串

hash

list

set

zset

使用场景

字符串

常见key val 存储

hash

存储map结构 Hash 存储一个学生信息对象数据，字段包括：id、姓名、班级、年龄等，通过id可以获取/修改任意的字段。

链表

关注列表、粉丝列表、消息队列

集合

使用Set存储一些集合性的数据，比如在微博应用中，可以将一个用户所有的关注人存在一个集合中，将其所有粉丝存在一个集合；
可以对集合取交集、并集、差集，应用到好友推荐、共同关注等。
还可以利用唯一性，统计访问网站的所有独立IP。

SortedSetSortedSet与Set的使用场景类似，是不允许重复项的String集合

有序集合

SortedSet可以通过提供一个优先级(score)的参数为成员排序，并且是插入有序的，即自动排序，可以应用于积分排行榜等。
如果需要一个有序且不重复的集合列表，可以选择sorted set数据结构，比如twitter 的public timeline可以以发表时间作为score来存储，这样获取时就是自动按时间排好序的。
用SortedSet做带权重的队列，比如普通消息的score为1，重要消息的score为2，然后工作线程可以选择按score的倒序来获取工作任务，让重要的任务优先执行。