Redis的五大基本数据类型

Redis的五大基本类型分别有String,List,Hash,Set,ZSet,它们分别有自己的底层数据结构，如图所示。

Redis数据类型对应的数据结构

不同的数据类型对应着不同的数据结构，这样设计的目的就是性能更好，基于不同的场景就用不同的数据类型，其中常见的数据结构有SDS(简单动态字符串)、双向链表、压缩列表、哈希表、跳表、整数集合、quicklist、listpack,不同的数据结构有不同的优势，总结如图所示：

键值对数据库是怎样实现的？

Redis的键值对种的Key就是字符串对象，而Value既可以是字符串对象，又可以是List对象，Hash对象，Zset对象，Set对象，Redis保存键值对所涉及的数据结构如图所示:

RedisDb结构,表示Redis数据库的结构，结构体存放了指向dict的指针
dict结构，结构体存放了2个哈希表，之所以存放2个哈希表的原因是为了rehash设定的
disctht结构,结构体存放了哈希表数组，数组的每一个元素都指向哈希表节点结构的指针
dictEntry结构，存放了key,value指针，key执行了String对象，而value指针可以指向String对象，还可以指向List、Hash、Zset、Set对象，

*特别注意*
void key 和void value指针指向的是Redis对象，Redis的每一个对象都由redisObject结构表示，如下图所示：

type,表示是什么数据类型，String、List、Hash、Set还是Zset
encoding，标识了底层用了那种数据结构
ptr，指向底层数据结构的指针

Redis键值对的全景图，对应了Redis对象与底层数据结构的关系如图所示：

Redis底层数据结构

SDS(简单动态字符串)

Redis是用C语言实现的，为什么Redis不直接用C语言中的char 字符数组来实现字符串呢，而是自己封装了一个名为简单动态字符串呢？
*C语言字符串的缺陷
比如，下图结束字符串”hello”的字符数组的结构

注：在C语言里字符中的’\0’代表结尾，通过\0的位置来判断字符串的长度。
缺陷1：获取字符串的长度要从头到尾遍历，其时间复杂度为O(N)
缺陷2：由于是规定\0为结束符假如字符串中有个\0字符，那就提前结束了，比如”he\0llo”，
,因此除了字符串的末尾之外，字符串不能含有’\0’,这个限制使得C语言的字符串只能保存字符串这样的文本文件
不能保存图像，视频，图像这样的二进制文件。
缺陷3：容易导致缓存区溢出

//将src字符串拼接到dest字符串的后面
char *strcat(char *dest ,char *src);

C语言中的字符串是不会记录自己的缓冲区大小的，这里的拼接不知道，缓冲区大小是否够用，缓冲区不够的时候将可能导致程序终止运行

总结：1.获取字符串的时间复杂度为O(N)
2.字符串的结尾是以’\0’字符标识，字符串里面不能有’\0’标识，故不能保存二进制文件
3.字符串操作函数不高效且不安全，比如有缓冲区溢出的风险，有可能造成程序终止

基于上述的缺点，Redis的SDS结构设计就把上面的问题解决了：

SDS的结构设计

结构中的成员变量

len，记录了字符串的长度，如果获取字符串的长度，直接调用这个成员变量就可以了时间复杂度为O(1)
alloc,记录了分配字符串的长度
表示sds类型
buf[]，字符数组，用来保存实际数据。不仅可以保存字符串，还可以保存二进制数据

总的来说，Redis的SDS结构在原本字符数组之上，增加了三个元数据:len,alloc,flags,用来解决C语言字符串的缺陷问题。
SDS的优点：
O(1)复杂度获取字符串的长度
因为SDS的成员变量有len这个元数据，记录了字符串的长度，要求得字符串的长度就直接返回这个成员变量的值就可以了。
二进制安全
因为SDS不需要”\0”来标志结束符，所以SDS不光可以存储字符串文件，还可以存储二进制文件。
不会发生缓冲区溢出
因为SDS的成员有len,与alloc，alloc-len=free,可以计算还剩下多少剩余空间，这样字符串在修改的时候就可以判断空间是否够用，而且在判断缓冲区不够用的时候，Redis将自动扩大SDS的空间大小，扩充的规则当缓冲区小于1M时，将扩充至2倍，当大于1M时，按1M扩充
节省内存空间

链表

Redis的List对象的底层实现之一就是链表

链表的结构设计

typedef struct listnode{
    //前置节点
    struct listnode *prev;
    //后置节点
    struct listnode *next;
    //节点的值
    void *value
}listnode

有结构体可以看出，有前置节点和后置节点，可以看出是一个双向链表

链表结构设计
Redis在listNode结构体基础上又封装了list这个数据结构，这样操作起来会更方便，链表结构如下：

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;

链表的优势与缺陷：
Redis的链表实现优点如下：

listnode节点有prev,next节点，所以获取节点的上一个和下一个节点的时间复杂度为O(1)
由于list结构提供了表头节点和表尾节点，所以获取链表的头结点和尾节点的时间复杂度为O(1)
由于list结构提供了链表节点的len,所以获取链表的长度的时间复杂度为O(1)

链表的缺陷

链表每个节点的内存都是不连续的，所以无法很好的利用CPU缓存，能很好利用CPU缓存的数据结构就是数组，因为数组的内存是连续的，这样可以充分利用CPU缓存来加速。
内存开销大，每个链表节点都要保存，前一个结点，后一个结点的指针

基于链表的缺陷：Redis3.0在List对象在数据量比较少的情况下会采用【压缩列表】作为List的底层数据结构来实现，它的优势就是节省内存空间，并且是内存紧凑型的数据结构。

压缩列表

压缩列表的最大的特点，就是它被设计成一种内存紧凑型的数据结构，占用一块连续的内存空间，不仅可以利用CPU的缓存，而且会针对不同长度的数据，进行相应的编码，这种方法有效的节省内存空间
但是压缩列表的缺陷是有的：、

不能保存过多的元素，否则查询效率就会降低
新增或者更新某个元素时，压缩列表占用的内存空间需要重新分配甚至可能引起连锁更新的问题

压缩列表的结构设计
压缩列表是Redis为了节约内存而开发的，它是由数据内存块组成的顺序型数据结构，类似于数组

压缩列表在表头有三个字段：Zlbytes.Zltail,Zlen,表尾有一个字段Zlend
Zlbytes:记录了压缩列表一共占用的内存大小
Zltail，记录压缩列表【尾部】节点距离起始地址多少字节，也就是列表尾的偏移量
Zlen,记录压缩列表包含的节点数量
Zlend:压缩列表的结束点，固定值0XFF(十进制255)

在压缩列表中，如果我们想定位第一个和最后一个元素，直接由前三个字段就可以推出来，时间复杂度为O(1),但是访问其他元素就没有这么高效了时间复杂度为O(N)

压缩列表的节点构成如下：

entry节点包含三个字段。分别为prevlen.encoding,data

prevlen:记录的是上一个节点的长度
encoding：记录当前节点的【实际类型】及【长度】
data:记录节点的数据

当我们往压缩列表中插入数据时，压缩列表就会根据数据是字符串还是整数，以及数据的大小，会使用不同空间大小prevlen和encoding这两个元素里保存的信息，这种根据数据大小和类型进行不同的空间大小分配的设计思想，正是Redis为了节省内存而设计的

prevlen大小：

如果上一个节点的值大小小于254字节，那么prevlen属性需要1字节的空间来保存这个值
如果上一个节点的值大小大于等于254字节，那么prevlen属性的需要5字节空间来保存这个值

encoding的属性的空间大小跟数据的是字符串和整数，以及字符串的长度有关

如果当前节点的数据是整数，则encoding会使用1字节的空间进行编码
如果当前节点的数据是字符串，则encoding会很根据字符串的大小不同，encoding会使用1字节、2字节、4字节进行编码。

压缩列表的问题：
连锁更新：假设一个压缩列表中有多个连续的、长度在250~253之间的节点，如下图

当新增一个节点其长度大于等于254字节时，entry1节点的prelen就变为5字节，那么entry1所占用的节点就大于等于254了，entry2节点的prelen的大小就要从1字节变为5字节，故压缩列表的所以节点都需要重新分配空间大小，这种特殊情况下产生的里连续多次空间扩展操作就叫做连锁更新

哈希表

哈希表是用来保存键值对（key_value）的数据结构
哈希表的优点：他能以O(1)的复杂度快速查询数据，执行流程是：将key通过hash函数的计算，他就能定位到表中的位置，因为哈希表实际上是数组，所以可以通过索引值快速查询到数据。
但是存在的风险也是有，在哈希表大小固定的情况下，随着数据不断增多，那么哈希冲突的可能性也比较高。
解决哈希冲突：Redis采用了【链式哈希】

哈希表结构设计

Redis的哈希表结构如下：

typedef struct dictht{
    //哈希表数组
    dictEntry **table
    //哈希表大小
    unsigned long size
     //哈希表大小掩码，用于计算索引值
     unsigned long sizemask;
    //哈希表已有的节点数量
    unsigned long used;
}dictht;

哈希表的节点的结构如下：

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

dictEntry结构不仅包含指向键和值的指针，还包含了指向下一个哈希表节点的指针，这个指针可以将多个哈希值相同的哈希节点串起来，已解决哈希冲突问题，这就是链式哈希。

哈希冲突

什么是哈希冲突呢？
举个例子，有一个可以存放8个哈希桶的哈希表，key1经过哈希计算，再将哈希值%8得到的结果为1，那么对应的哈希桶就为1.类似的key9和key10对应的哈希桶就相同了。

此时，key1和key9对应到了相同的哈希桶中，这就发生了哈希冲突。

解决方法：Redis采用【链式哈希】来解决哈希冲突

实现方法：就是每个哈希节点都有一个next指针，用于指向下一个哈希表节点，因此多个哈希表节点可以用next指针构成单链表，被分配到同一个哈希桶上的多个节点就可以用这个单链表连接起来，这就解决了哈希冲突

局限性：随着元素越来越多，链表越来越长，在查询这一位置的时间复杂度为O(N)

解决办法：rehash,也就是对哈希表的大小进行拓展。

rehash

Redis使用dictht结构体表示哈希表。不过，在实际使用哈希表是，Redis定义一个dict结构体，这个结构体里定义了两个哈希表（ht([2]）
之所以定义两个哈希表，是因为进行rehash的时候，需要用2个哈希表了。

在正常的插入数据都会写在哈希表1，在进行rehash的时候哈希表2才有作用，此时的哈希表2并没有分配空间。
rehashf分为3步

给哈希表2分配空间，一般大小为哈希表的2倍
将哈希表1的元素，移到哈希表2中
迁徙完毕后，释放哈希表1的空间，此时哈希表2变为之前的哈希表1，进行插入操作，哈希表1变成哈希表1为之后的rehash做准备

缺点：如果哈希表的数据比较大，迁徙到哈希表的速度会慢，造成Redis阻塞，无法服务其他请求
解决办法：渐进式hash

渐进式rehash

为了避免rehash在数据迁徙过程中，因拷贝数据的耗时，影响Redis性能的情况，所以Redis采用了渐进式hash,也就是将数据的迁徙的工作不再是一次性迁徙完成的，而是分次迁徙。

渐进式rehash的步骤

给哈希表2分配空间
在rehash期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis除了会执行对应的操作之外，还会顺序将【哈希表1】中索引位置上的所有key-value迁徙到哈希表2中。
随着处理客户端发起的哈希表的操作数量越多，最终在某个时间段，会把哈希表1的所有key-value
迁移到哈希表2，从而完成rehash操作

注：在渐进式rehash过程中，会变成两个哈希表，所以在渐进式rehash进行期间，哈希表的删除、和查找、新增会在两个哈希表中进行
如果hash表1查找不到元素，就在hash表2中查找，如果hash表1删除失败，就在hash表2中删除，新增元素直接在哈希表2中进行。

rehash触发条件：

rehash的触发条件和负载因子有关
负载因子=哈希表已保存节点数量/哈希表大小
触发条件：
1.当负载因子大于等于1，并且Redis没有执行bgsave命令或者bgrewriteof命令。也就是没有执行RDB快照或者没有进行AOF重写的时候就会rehash
2.当负载因子大于等于5时，不管有没有进行ROB快照还是AOF重写，都要进行rehash.

整数集合

整数集合时Set对象的底层之一。当一个Set对象只包含整数数值元素，并且元素数量不大时，就会用这个数据结构作为底层实现。

整数集合结构设计

整数集合本质是一块连续的内存空间，它的结构定义如下：

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

可以看到，保存元素的容器是一个 contents 数组，虽然 contents 被声明为 int8_t 类型的数组，但是实际上 contents 数组并不保存任何 int8_t 类型的元素，contents 数组的真正类型取决于 intset 结构体里的 encoding 属性的值。比如：

如果 encoding 属性值为 INTSET_ENC_INT16，那么 contents 就是一个 int16_t 类型的数组，数组中每一个元素的类型都是 int16_t；
如果 encoding 属性值为 INTSET_ENC_INT32，那么 contents 就是一个 int32_t 类型的数组，数组中每一个元素的类型都是 int32_t；
如果 encoding 属性值为 INTSET_ENC_INT64，那么 contents 就是一个 int64_t 类型的数组，数组中每一个元素的类型都是 int64_t；
不同类型的 contents 数组，意味着数组的大小也会不同。

整数数组的升级操作
如果原有的元素都是int16_t的类型，此时加入了一个元素，它的大小大于int16_t，故要进行整数数组升级，把所i有的int16_t的类型变为int32_t，升级的过程也要保证元素有序性。
整数集合升级的过程不会重新分配一个新类型的数组，而是在原本的数组上扩展空间，然后在将每个元素按间隔类型大小分割，如果 encoding 属性值为 INTSET_ENC_INT16，则每个元素的间隔就是 16 位。
举个例子，假设有一个整数集合里有 3 个类型为 int16_t 的元素。

现在，往这个整数集合中加入一个新元素 65535，这个新元素需要用 int32_t 类型来保存，所以整数集合要进行升级操作，首先需要为 contents 数组扩容，在原本空间的大小之上再扩容多 80 位（4x32-3x16=80），这样就能保存下 4 个类型为 int32_t 的元素。

扩容完 contents 数组空间大小后，需要将之前的三个元素转换为 int32_t 类型，并将转换后的元素放置到正确的位上面，并且需要维持底层数组的有序性不变，整个转换过程如下：

整数集合升级的好处？
如果要让一个数组同时保存 int16_t、int32_t、int64_t 类型的元素，最简单做法就是直接使用 int64_t 类型的数组。不过这样的话，当如果元素都是 int16_t 类型的，就会造成内存浪费的情况。

整数集合升级就能避免这种情况，如果一直向整数集合添加 int16_t 类型的元素，那么整数集合的底层实现就一直是用 int16_t 类型的数组，只有在我们要将 int32_t 类型或 int64_t 类型的元素添加到集合时，才会对数组进行升级操作。

总结：整数升级的好处就是为了节省内存空间。

注：整数集合不支持降级操作：

跳表

Redis只有在Zset对象的底层实现用到了跳表，跳表的优势是能支持平均O(logN)复杂度的节点查找。
Zset对象是唯一一个同时使用了两个数据结构来实现Redis对象，这两个数据结构是跳表、哈希表。这样的好处是既能进行高效的范围查找，也就进行高效单点查询。

typedef struct zset{
    dict *dict;
    zskiplist *zsl;
}

Zset对象能支持范围查询（如 ZRANGEBYSCORE操作），这是因为它的数据结构设计采用了跳表，而又能以常数复杂度获取元素权重（如ZSCORE操作），这是因为它同时采用了哈希表进行索引。

跳表结构设计

链表在查询的时候，因为需要逐一查找，所以查询复杂度为O(N)，于是出现了跳表。跳表是在链表基础改进过来的，实现了一种【多层】的有序链表，这样的好处是能快速定位数据。

图中头结点有L0-L2三个头指针，分别指向了不同层级的节点，然后每个层级的节点都通过指针连接起来、

L0层级共有5个节点，分别是1、2、3、4、5
L1层级共有3个节点，分别是2，3，5

L2层级只有1个节点，也就是节点3

跳表的结构体

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

跳表的结构包括

跳表的头尾节点，便于在O(1)时间复杂度内访问跳表的头结点和尾节点
跳表的长度，便于在O(1)时间复杂度获取跳表的节点的数量
跳表的最大层数，便于在O(1)时间复杂度获取跳表中层高最大的那个节点的层数量

跳表节点查询过程

查找一个跳表节点的过程时，跳表会从头结点的最高层开始，逐一遍历每一层。在遍历某一层的跳表节点时，会用跳表节点中的SDS类型的元素和元素的权重来进行判断，一共有两个判断条件：

如果当前节点的权重小于要查询的权重时，跳表会访问该层上的下一个节点。
如果当前节点的权重【等于】要查找的权重时，并且当前节点SDS类型【小于】要查找的数据时，跳表就会访问该层节点的下一个节点

如果上面两个条件都不满足，或者下一个节点为空时，跳表就会使用目前遍历的节点的level数组的下一层指针，然后沿着下一层指针继续查找，这就相当于跳到下一层接着查找。
举个例子，下图有个3层级的跳表
如果要查找元素【ab，权重为2】的节点，查找过程为

遍历L2节点的第一个指针，权重为3大于要查询的权重，遍历节点的下一层节点的指针
节点指针指向权重为2，匹配，然后比较SDS类型数据，相同，查询成功，查询结束。
跳表节点层数设置
跳表的相邻两层的节点数量的比例会影响跳表的查询性能。
举个例子，下面的跳表，第二层的节点数量只有一个，而第一层节点数量有6个。

这样如果要查询节点6，那基本就跟链表的查询复杂度一样，就需要在第一层节点顺序查找，时间复杂度就是O（N）了，所以为了降低查询复杂度，我们就需要维持相邻层节点间的关系。

跳表的相邻两层节点数量最理想的比例是2:1,查询的复杂度可以降低到O(logN).
下图的跳表就是，相邻两层的节点数量的比例是2：1

那怎样才能维持相邻两层节点数量比例为2:1呢?

如果采用新增接待你或者删除节点时，来调整跳表节点以维持比例的方法的话，会带来额外开销。

Redis则采用一种巧妙地方法是,跳表在创建节点的时候，随机生成每个节点的层数，并没有严格维持相邻两层节点为2;1的情况

具体的做法是，跳表在创建节点的时候，回生成范围为【0-1】的一个随机数，如果这个随机数小于0.25，（相当于概率25%），那么层数就增加1层，然后继续用生成下一个随机数，直到随机数的结果大于0.25结束，最终确定该节点的层数。

这样的做法是，相当于每增加一层的概率不超过25%,层数也高，概率越低，层高最大限制为64.

quicklist

在Redis3.0之前，List对象的底层数据结构是双向链表或者压缩列表。然后在Redis3.2的时候,List对象的底层改为由quicklist数据结构实现。

quicklist就是双向链表+压缩列表的组合,压缩列表虽然通过紧凑的内存布局节省了内存开销，但是因为它的结构设计，如果元素数量增加了，或者元素变大了，压缩列表有连锁更新的风险，一旦发生，会造成性能下降。

quicklist的解决办法，通过控制每个链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题。因为压缩列表元素越少越好，连锁更新到来的影响就越小，从而提供了更好的访问性能，

在向quicklist添加一个元素的时候，不会像普通的链表那样，直接新建一个链表节点。而是会检查插入位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到quicklistNode结构的压缩列表，如果不能容纳，就会建立新的quickNode结构。

quicklist会控制quicklistNode结构里的压缩列表的大小或者元素的个数,来规避潜在的连锁更新的风险，但是这并没有完全避免连锁更新的问题

listpack

quicklist虽然通过控制quicklistnode结构里的压缩列表的大小或者元素个数，来减少连锁更新带来的性能影响，但并没有完全解决这个问题。
于是Redis5.0新设计一个数据结构是listpack，目的是替代压缩列表，它最大的特点就是listpack中每一个节点不再包含前一个节点的长度了，压缩列表每个节点正因为需要保存前一个节点的长度，就会有连锁更新的隐患。

listpack结构设计

listpack 头包含两个属性，分别记录了 listpack 总字节数和元素数量，然后 listpack 末尾也有个结尾标识。图中的 listpack entry 就是 listpack 的节点了。

每个 listpack 节点结构如下：

主要包含三个方面内容：

encoding，定义该元素的编码类型，会对不同长度的整数和字符串进行编码；
data，实际存放的数据；
len，encoding+data的总长度；
可以看到，listpack 没有压缩列表中记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当我们向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。

Java 学习笔记

Redis数据结构总结