Redist有五种基本数据结构：string、hash、set、zset、list。这五种数据结构的底层数据结构有六种：动态字符串SDS、链表、哈希表、跳表、整数集合、压缩链表

底层结构

Redis是用C语言写的，但是Redis并没有使用C的字符串表示（C是字符串是以\0空字符结尾的字符数组），而是自己构建了一种简单动态字符串（simple dynamic string，SDS）的抽象类型，并作为Redis的默认字符串表示

在Redis中，包含字符串值的键值对底层都是用SDS实现的

动态字符串SDS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 3.0
struct sdshdr {
    // 记录buf数组中已使用字节的数量，即SDS所保存字符串的长度
    unsigned int len;
    // 记录buf数据中未使用的字节数量
    unsigned int free;
    // 字节数组，用于保存字符串
    char buf[];
};

// 3.2
/* 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[];
};

3.2版本之后，会根据字符串的长度来选择对应的数据结构

1
2
3
4
5
6
7
8
9
10
11
static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)  // 32
        return SDS_TYPE_5;
    if (string_size < 1<<8)  // 256
        return SDS_TYPE_8;
    if (string_size < 1<<16)   // 65536 64k
        return SDS_TYPE_16;
    if (string_size < 1ll<<32)  // 4294967296 4G
        return SDS_TYPE_32;
    return SDS_TYPE_64;
}

img

len：记录当前已使用的字节数（不包括'\0'），获取SDS长度的复杂度为O(1)

alloc：记录当前字节数组总共分配的字节数量（不包括'\0'）

flags：标记当前字节数组的属性，是sdshdr8还是sdshdr16等，flags值的定义可以看下面代码

buf：字节数组，用于保存字符串，包括结尾空白字符`’\0’

1
2
3
4
5
6
// flags值定义
#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

上面的字节数组的空白处表示未使用空间，是Redis优化的空间策略，给字符串的操作留有余地，保证安全提高效率

双向链表

链表上的节点定义如下，adlist.h/listNode

1
2
3
4
5
6
7
8
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点值
    void *value;
} listNode;

链表的定义如下，adlist.h/list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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：用于对比链表节点所保存的值和另一个输入值是否相等

链表结构图

img

链表特性

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

3.2版本后更改

quicklist：

（1）什么是quicklist：

quicklist是一个双向链表，而且是一个基于ziplist的双向链表，quicklist的每个节点都是一个ziplist，比如，一个包含3个节点的quicklist，如果每个节点的ziplist又包含4个数据项，那么对外表现上，这个list就总共包含12个数据项。

quicklist的结构为什么这样设计呢？总结起来，大概又是一个空间和时间的折中：

双向链表便于在表的两端进行push和pop操作，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。
ziplist由于是一整块连续内存，所以存储效率很高。但是，它不利于修改操作，每次数据变动都会引发一次内存的realloc。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝，进一步降低性能。
于是，结合了双向链表和ziplist的优点，quicklist就应运而生了。

（2）quicklist中每个ziplist长度的配置：

不过，这也带来了一个新问题：到底一个quicklist节点包含多长的ziplist合适呢？比如，同样是存储12个数据项，既可以是一个quicklist包含3个节点，而每个节点的ziplist又包含4个数据项，也可以是一个quicklist包含6个节点，而每个节点的ziplist又包含2个数据项。

这又是一个需要找平衡点的难题。我们只从存储效率上分析一下：

每个quicklist节点上的ziplist越短，则内存碎片越多。内存碎片多了，有可能在内存中产生很多无法被利用的小碎片，从而降低存储效率。这种情况的极端是每个quicklist节点上的ziplist只包含一个数据项，这就蜕化成一个普通的双向链表了。
每个quicklist节点上的ziplist越长，则为ziplist分配大块连续内存空间的难度就越大。有可能出现内存里有很多小块的空闲空间（它们加起来很多），但却找不到一块足够大的空闲空间分配给ziplist的情况。这同样会降低存储效率。这种情况的极端是整个quicklist只有一个节点，所有的数据项都分配在这仅有的一个节点的ziplist里面。这其实蜕化成一个ziplist了
可见，一个quicklist节点上的ziplist要保持一个合理的长度。那到底多长合理呢？这可能取决于具体应用场景。实际上，Redis提供了一个配置参数list-max-ziplist-size，就是为了让使用者可以来根据自己的情况进行调整。

list-max-ziplist-size -2

这个参数可以取正值，也可以取负值。

当取正值的时候，表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如，当这个参数配置成5的时候，表示每个quicklist节点的ziplist最多包含5个数据项。

当取负值的时候，表示按照占用字节数来限定每个quicklist节点上的ziplist长度。这时，它只能取-1到-5这五个值，每个值含义如下：

-5: 每个quicklist节点上的ziplist大小不能超过64 Kb。（注：1kb => 1024 bytes）

-4: 每个quicklist节点上的ziplist大小不能超过32 Kb。

-3: 每个quicklist节点上的ziplist大小不能超过16 Kb。

-2: 每个quicklist节点上的ziplist大小不能超过8 Kb。（-2是Redis给出的默认值）

-1: 每个quicklist节点上的ziplist大小不能超过4 Kb。

哈希表

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

Redis的键值对存储就是用哈希表实现的，散列（Hash）的底层实现之一也是哈希表

哈希表结构定义，dict.h/dictht

1
2
3
4
5
6
7
8
9
10
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值，等于size-1
    unsigned long sizemask;
    // 哈希表已有节点的数量
    unsigned long used;
} dictht;

哈希表是由数组table组成，table中每个元素都是指向dict.h/dictEntry结构的指针，哈希表节点的定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 指向下一个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

其中key是我们的键；v是键值，可以是一个指针，也可以是整数或浮点数；next属性是指向下一个哈希表节点的指针，可以让多个哈希值相同的键值对形成链表，解决键冲突问题

最后就是我们的字典结构，dict.h/dict

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct dict {
    // 和类型相关的处理函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引，当rehash不再进行时，值为-1
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 迭代器数量
    unsigned long iterators; /* number of iterators currently running */
} dict;

type属性和privdata属性是针对不同类型的键值对，用于创建多类型的字典，type是指向dictType结构的指针，privdata则保存需要传给类型特定函数的可选参数，关于dictType结构和类型特定函数可以看下面代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct dictType {
    // 计算哈希值的行数
    uint64_t (*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;

dict的ht属性是两个元素的数组，包含两个dictht哈希表，一般字典只使用ht[0]哈希表，ht[1]哈希表会在对ht[0]哈希表进行rehash（重哈希）的时候使用，即当哈希表的键值对数量超过负载数量过多的时候，会将键值对迁移到ht[1]上

rehashidx也是跟rehash相关的，rehash的操作不是瞬间完成的，rehashidx记录着rehash的进度，如果目前没有在进行rehash，它的值为-1

结合上面的几个结构，我们来看一下字典的结构图（没有在进行rehash）

img

跳表

一个普通的单链表查询一个元素的时间复杂度为O(N)，即便该单链表是有序的。使用跳跃表（SkipList）是来解决查找问题的，它是一种有序的数据结构，不属于平衡树结构，也不属于Hash结构，它通过在每个节点维持多个指向其他节点的指针，而达到快速访问节点的目的

跳跃表是有序集合（Sorted Set）的底层实现之一，如果有序集合包含的元素比较多，或者元素的成员是比较长的字符串时，Redis会使用跳跃表做有序集合的底层实现

跳跃表的定义

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

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

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

img

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

img

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

img

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

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

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

img

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

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

跳跃表的实现

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 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;

zskiplistNode结构

  • level数组（层）：每次创建一个新的跳表节点都会根据幂次定律计算出level数组的大小，也就是次层的高度，每一层带有两个属性-前进指针和跨度，前进指针用于访问表尾方向的其他指针；跨度用于记录当前节点与前进指针所指节点的距离（指向的为NULL，阔度为0）
  • backward（后退指针）：指向当前节点的前一个节点
  • score（分值）：用来排序，如果分值相同看成员变量在字典序大小排序
  • obj或ele：成员对象是一个指针，指向一个字符串对象，里面保存着一个sds；在跳表中各个节点的成员对象必须唯一，分值可以相同

zskiplist结构

  • header、tail表头节点和表尾节点
  • length表中节点的数量
  • level表中层数最大的节点的层数

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

img

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

img

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

整数集合

整数集合（intset）是Redis用于保存整数值的集合抽象数据结构，可以保存类型为int16_t、int32_t、int64_t的整数值，并且保证集合中不会出现重复元素

整数集合是集合（Set）的底层实现之一，如果一个集合只包含整数值元素，且元素数量不多时，会使用整数集合作为底层实现

整数集合的定义实现

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

1
2
3
4
5
6
7
8
9
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

img

整数集合的升级

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

升级添加新元素：

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

整数集合的升级策略可以提升整数集合的灵活性，并尽可能的节约内存

另外，整数集合不支持降级，一旦升级，编码就会一直保持升级后的状态

压缩链表

压缩列表（ziplist）是为了节约内存而设计的，是由一系列特殊编码的连续内存块组成的顺序性（sequential）数据结构，一个压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者一个整数值

压缩列表是列表（List）和散列（Hash）的底层实现之一，一个列表只包含少量列表项，并且每个列表项是小整数值或比较短的字符串，会使用压缩列表作为底层实现（在3.2版本之后是使用quicklist实现）

压缩列表的构成

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

img

各部分组成说明如下

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

压缩列表节点的构成

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

img

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

对象

上面介绍了Redis的主要底层数据结构，包括简单动态字符串（SDS）、链表、字典、跳跃表、整数集合、压缩列表。但是Redis并没有直接使用这些数据结构来构建键值对数据库，而是基于这些数据结构创建了一个对象系统，也就是我们所熟知的可API操作的Redis那些数据类型，如字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted Set)

根据对象的类型可以判断一个对象是否可以执行给定的命令，也可针对不同的使用场景，对象设置有多种不同的数据结构实现，从而优化对象在不同场景下的使用效率

类型 编码 BOJECT ENCODING 命令输出 对象
REDIS_STRING REDIS_ENCODING_INT “int” 使用整数值实现的字符串对象
REDIS_STRING REDIS_ENCODING_EMBSTR “embstr” 使用embstr编码的简单动态字符串实现的字符串对象
REDIS_STRING REDIS_ENCODING_RAW “raw” 使用简单动态字符串实现的字符串对象
REDIS_LIST REDIS_ENCODING_ZIPLIST “ziplist” 使用压缩列表实现的列表对象
REDIS_LIST REDIS_ENCODING_LINKEDLIST ‘“linkedlist’ 使用双端链表实现的列表对象
REDIS_HASH REDIS_ENCODING_ZIPLIST “ziplist” 使用压缩列表实现的哈希对象
REDIS_HASH REDIS_ENCODING_HT “hashtable” 使用字典实现的哈希对象
REDIS_SET REDIS_ENCODING_INTSET “intset” 使用整数集合实现的集合对象
REDIS_SET REDIS_ENCODING_HT “hashtable” 使用字典实现的集合对象
REDIS_ZSET REDIS_ENCODING_ZIPLIST “ziplist” 使用压缩列表实现的有序集合对象
REDIS_ZSET REDIS_ENCODING_SKIPLIST “skiplist” 使用跳跃表表实现的有序集合对象

数据结构

String

String数据结构是最简单的数据类型。一般用于复杂的计数功能的缓存：微博数，粉丝数等。

底层实现方式：动态字符串sds 或者 long

String的内部存储结构一般是sds（Simple Dynamic String，可以动态扩展内存），但是如果一个String类型的value的值是数字，那么Redis内部会把它转成long类型来存储，从而减少内存的使用。

  • 确切地说，String在Redis中是用一个robj来表示的。
  • 用来表示String的robj可能编码成3种内部表示：OBJ_ENCODING_RAW，OBJ_ENCODING_EMBSTR，OBJ_ENCODING_INT。其中前两种编码使用的是sds来存储，最后一种OBJ_ENCODING_INT编码直接把string存成了long型。
  • 在对string进行incr, decr等操作的时候，如果它内部是OBJ_ENCODING_INT编码，那么可以直接进行加减操作；如果它内部是OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR编码，那么Redis会先试图把sds存储的字符串转成long型，如果能转成功，再进行加减操作。
  • 对一个内部表示成long型的string执行append, setbit, getrange这些命令，针对的仍然是string的值（即十进制表示的字符串），而不是针对内部表示的long型进行操作。比如字符串”32”，如果按照字符数组来解释，它包含两个字符，它们的ASCII码分别是0x33和0x32。当我们执行命令setbit key 7 0的时候，相当于把字符0x33变成了0x32，这样字符串的值就变成了”22”。而如果将字符串”32”按照内部的64位long型来解释，那么它是0x0000000000000020，在这个基础上执行setbit位操作，结果就完全不对了。因此，在这些命令的实现中，会把long型先转成字符串再进行相应的操作。

Hash

Hash特别适合用于存储对象，因为一个对象的各个属性，正好对应一个hash结构的各个field，可以方便地操作对象中的某个字段。

底层实现方式：压缩列表ziplist 或者 字典dict

当Hash中数据项比较少的情况下，Hash底层才用压缩列表ziplist进行存储数据，随着数据的增加，底层的ziplist就可能会转成dict，具体配置如下：

1
2
hash-max-ziplist-entries 512
hash-max-ziplist-value 64

当hash中的数据项（即filed-value对）的数目超过512时，也就是ziplist数据项超过1024的时候
当hash中插入的任意一个value的长度超过了64字节的时候

当满足上面两个条件其中之一的时候，Redis就使用dict字典来实现hash。

Redis的hash之所以这样设计，是因为当ziplist变得很大的时候，它有如下几个缺点：

  • 每次插入或修改引发的realloc操作会有更大的概率造成内存拷贝，从而降低性能。

  • 一旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更大的一块数据。

  • 当ziplist数据项过多的时候，在它上面查找指定的数据项就会性能变得很低，因为ziplist上的查找需要进行遍历。

总之，ziplist本来就设计为各个数据项挨在一起组成连续的内存空间，这种结构并不擅长做修改操作。一旦数据发生改动，就会引发内存realloc，可能导致内存拷贝。

List

list 的实现为一个双向链表，经常被用作队列使用，支持在链表两端进行push和pop操作，时间复杂度为O(1)；同时也支持在链表中的任意位置的存取操作，但是都需要对list进行遍历，支持反向查找和遍历，时间复杂度为O(n)。

list是一个能维持数据项先后顺序的列表（各个数据项的先后顺序由插入位置决定），便于在表的两端追加和删除数据，而对于中间位置的存取具有O(N)的时间复杂度。

list 的应用场景非常多，比如微博的关注列表，粉丝列表，消息列表等功能都可以用Redis的 list 结构来实现。可以利用lrange命令，做基于redis的分页功能。

  • Redis3.2之前的底层实现方式：压缩列表ziplist 或者 双向循环链表linkedlist

当list存储的数据量比较少且同时满足下面两个条件时，list就使用ziplist存储数据：

list中保存的每个元素的长度小于 64 字节；

列表中数据个数少于512个。

当不能同时满足上面两个条件的时候，list就通过双向循环链表linkedlist来实现了

  • Redis3.2及之后的底层实现方式：quicklist

quicklist是一个双向链表，而且是一个基于ziplist的双向链表，quicklist的每个节点都是一个ziplist，结合了双向链表和ziplist的优点

Set

set是一个存放不重复值的无序集合，可以做全局去重的功能，提供了判断某个元素是否在set集合内的功能，这个也是list所不能提供的。基于set可以实现交集、并集、差集的操作，计算共同喜好，全部的喜好，自己独有的喜好等功能。

底层实现方式：有序整数集合intset 或者 字典dict

当存储的数据同时满足下面这样两个条件的时候，Redis 就采用整数集合intset来实现set这种数据类型：

  • 存储的数据都是整数
  • 存储的数据元素个数小于512个

当不能同时满足这两个条件的时候，Redis 就使用dict来存储集合中的数据

Sorted Set

Sorted set多了一个权重参数score，集合中的元素能够按score进行排列。可以做排行榜应用，取TOP N操作。另外，sorted set可以用来做延时任务。最后一个应用就是可以做范围查找。

底层实现方式：压缩列表ziplist 或者 zskiplistNode

当存储的数据同时满足下面这两个条件的时候，Redis就使用压缩列表ziplist实现sorted set

  • 集合中每个数据的大小都要小于 64 字节
  • 元素个数要小于 128 个，也就是ziplist数据项小于256个

当不能同时满足这两个条件的时候，Redis 就使用zskiplistNode来实现sorted set。