redis数据结构

redis支持五种对象类型，而每一种类型至少都有两种编码，这样的好处在于，一方面接口与实现分离，当需要增加或者改变内部编码的时候，用户使用不会受到影响，另一方面，可以根据不同的场景切换内部的编码，提高效率。
redis各种对象支持的编码如下

image.png

关于rendis的编码都遵循一下定律，编码转换在rendis写入数据时完成，切过程不可逆转，只能小内存编码向大内存编码转换。

1、字符串

（1）概况

字符串是最基础的类型，因为所有的键都是字符串，切字符串之外的其他几种复杂的类型元素也是字符串，字符串的长度不超过512M

（2）内部编码

字符串类型的内部编码有3种，

int：8个字节的长整型，字符串值是整型时，这个值使用long整型表示。
embstr:<=39字节的字符串，embstr与raw都是使用redisObject和sds保存数据，区别在于，embstr的使用只分配一次内存空间（因此redisObject和sds是连续的），而raw需要分配两次内存空间（分别是redisobject和sds分配空间）。因此与raw相比，embstr的好处在于创建时少分配一次空间，少出时少释放一次空间，一级对象和所有数据连在一起，寻找方便。而embstr的坏处也很明显，如果字符串的长度增加需要重新分配内存时，整个redisObject和sds都需要吹牛搞笑分配内存，因此，redis中embstr实现只为可读。
raw:大于39个字节的字符串
示例如下：

image.png

embstr和raw进行区分的长度是39，因为redisObject的长度是16个字节，sds长度是9+字符串长度，16+9+39正好是64，jemalloc正好可以分配64字节的内存单元。

（3）编码转换

当int数据不在是整数，或者大小超过long的范围时，会自动转为raw
而对于embstr，由于其实现是只读，因此在对于embstr对象进行修改时，都会先转化为raw再进行修改，因此，只要是修改embstr对象，修改后的对象一定是raw的，无论是否达到了39个字节。示例图如下：

image.png

（4）bitmap

bitmap并不是redis的一种数据类型，而是定义在String类型上的面向位操作，因为String是二进制安全的并且最大长度是512MB，所以String可以建立2^32个不同的位，位操作被分为两种、

常数时间的单独一个位操作
对一组bit位的操作
Bitmap的最大的一个优点是当存储信息时，可以极大的节省空间，例如一个系统中的用户id由递增，只需要512M就可以记住40亿用户的单比特信息。

Bitmap使用SETBIT和GETBIT命令设置和获取位的值：

setbit key 10 1
getbit key 10

setbit命令的第一个参数表示需要被设置的位，第二个参数表示需要设置的值。需要注意的是，当被设置的位操作字符串当前长度时，setbit命令将会自动增加字符串的长度，getbit返回制定位置上的值，对于超出长度的地方，会视为0。

2、列表

（1）概况

列表用来存储多个有序的字符串，每一个字符串称为元素，一个列表可以存储2^32-1个元素，redis中的列表支持两端插入和弹出，并且可以获得指定位置的元素，可以充当数组、队列、栈等。

（2）内部编码

列表的内部编码可以是压缩列表或者是双端列表
双端列表
由一个list结构和多个listNode结构组成，典型结构如下图所示：

image.png

通过图中可以看出，双端列表同时保存了表头指针和表表尾指针，并且每个节点都指向前和后两个方向的指针；链表中保存了列表的长度；dup、freeh和match为节点值设置类型特点函数，所以链表可以用于保存各种不同类型的值。而链表中每个节点指向的是type为字符串的redisObject。
压缩列表
压缩列表最大的特点，就是它被设计成一种内存紧凑型的数据结构，占用一块连续的内存空间，不仅可以利用cpu缓存，而且会针对不同长度的数据，进行相应的编码，这种方法可以有效的节省内存开销。
但是，压缩列表也不是没有缺点的

不能保存过多的元素，否则查询效率就会降低
新增或者修改某个元素时，压缩列表占用的内存空间需要重新分配，甚至可能引发连锁更新的问题。（连续更新原因是：后一节点会记录前一节点所占内存的字节长度，如果新增字节所占的字节长度大于255，会导致后一节点的prelen属性所占的内存重新分配，进而导致后一节点的整个字节数增大，又会影响到下一个节点，因此产生连锁更新反应）
压缩列表的整体结构图下图：

image.png

压缩列表在表头有三个字段：
zlbytes 记录整个压缩列表占用的内存字节数
zltail 记录压缩列表尾部节点距离起始地址有多少字节，也就是列表尾的偏移量。
zllen 记录压缩列表包含多少节点数
zlend 标记压缩列表的结束点，固定值0XFF 十进制就是255
在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位到，复杂度是O（1），而其他元素就没有这么高效了，只能阻逐个的查，复杂度是O(n)，因此压缩列表不适合保存过多的元素。
压缩列表的节点结构如下如图

image.png

压缩列表节点包含三部分内容：
prevlen 记录了前一个节点的长度
encoding 记录当前节点实际数据的类型以及长度
data 记录当前节点的实际数据

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

那么prevlen和encoding是怎么根据数据的大小和类型来进行不同空间大小分配的呢？
压缩列表里每一个节点中的prevlen字段都记录着前一个节点的长度，而且prevlen属性的空间大小跟前一个节点的长度有关，比如：

如果前一个节点的长度大小小于254，那么prevlen属性就需要用1个字节的空间来保存这个长度，
如果前一个字节的长度大于254，那么prevlen就需要5个字节的空间来保存长度。

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

如果当前节点的数据时整数，则encoding会使用1字节的空间进行编码，
如果当前节点的数据时字符串，根据字符串的长度大小，encoding会使用1字节，2字节，5字节等来进行编码。

（3）编码转换

只有同时满足下面两个条件时，才会使用压缩列表：

列表中元素数量小于512个
列表中所有字符串对象都小于64字节

下图展示了列表编码的转换：

image.png

其中，单个字符串不能超过64字节，是为了便于统一分配每个节点的长度，这里的64字节是指字符串的长度，不包含SDS的结构。因为压缩列表使用的是连续的内存块，不需要sds结构指明长度。

3、哈希

（1）概况

哈希，不仅是redis对外提供的5种对象类型的一种，也是redis作为Key-value数据库所使用的数据结构，

（2）内部编码

内层哈希使用的内部编码可以是压缩列表和哈希表两种，redis的外层的哈希则使用的是hashtable。
压缩列表列表前面已经介绍了，和哈希表相比，压缩列表用于元素个数少，元素长度小的场景，优势在于集中存储，节省空间，同事，虽然对于元素的操作复杂度由O(1)变为了o(n)，但是由于哈希中元素数量较少，因此，操作的时间并没有明显的优势。

hashtable: 一个hashtable由1个dict结构，2个dictht结构，1个dictEntry指针数组（称为bucket）和多个dictentry结构组成，正常情况下（hashtable没有进行rehash）各个部分关系如图：

image.png

dictEntry
dictentry结构用于保存键值对，结构定义如下：

typedef struct  dictEntry{
        void *key;
        union{
                void *val;
                uint64_tu64;
                int64_ts64;
       }val;
        struct dictEntry *next;
}dictEntry;

其中，各个属性的功能如下：

key 键值对中的键
val 键值对中的值，使用的union实现，存储内容既可以是一个指向值得指针，也可以是64位整型或者无符号64位整型。
next 指向下一个dictEntry对象

bucket
bucket是一个数组，数组的每一个元素都指向一个dicEntry结构的指针。redis中bucket数组的大小计算规则如下：大于dictEntryd的最小的2^n,例如，如果有1000个dictentry，那么bucket的大小为1024.如果是1500个那么大小就是2048.

dictht
dictht结构如下：

typedef struct dictht{
        dictEntry **table;
        unsigned long size;
        unsigned long sizemask;
        unsigned long used;
}dictht;

其中各个属性功能说明如下：

table属性是一个指针，指向bucket
size属性记录了哈希表的大小，即bucket的大小
used记录了已经使用的dictEntry的数量
sizemask属性的值总数为size-1，这个属性和哈希值一起去决定一个键在table中存储的位置。

dict
一般来说，通过使用dictht和dictEntry结构，便可以实现普通哈希表的功能，但是redis还是在dictht结构上，还有一个dict结构。
dict结构如下

typedef struct dict{
        dictType * type;
        void *privdata;
        dictht ht[2];
        int trehashidx;
}dict;

其中，type属性和privdata属性是为了适应不同类型的键值对，用于创建多态字典。
ht属性和trehashidx属性则用于rehash,即当哈希表需要扩展或者收缩时使用，ht包含两项的数组，每一项都指向一个dictht结构，这也是redis的哈希会有一个dict和两个dictht的原因，通常情况下，所有的数据都放在dict的ht[0]中，ht[1]只有在rehash的时候使用，dict进行rehash操作的时候，将ht[0]中的数据rehash到ht[1]中，然后将ht[1]的值复制给ht[0]，并清空ht[1].
因此，redis在hash中使用了dict和dictht是为了适应不同类型的键值对，另一方面是为了rehash

（3）编码

如前所诉，redis的内层hash既可以使用哈希表，也可以使用压缩列表，转换规则和list的规则一样。

4、集合

（1）概述

集合（set）与列表类型，都是用来保存多个字符串，但是和集合不同的是

集合的元素时无序的，因此不能通过索引来操作
集合中的元素不能有重

一个集合中最多可以存储2^32-1个元素，除了支持常规的增删改查，redis还支持多个集合去交集，并集，差集。

（2）内部编码

集合的内部编码可以是整数集合或哈希表
哈希表和哈希一直，不过集合在使用哈希表的时候，值都是null

整数集合结构定义如下：

typedef struct intset{
      uint32_t encoding;
      uint32_t length;
      int8_t contents[];
} intset;

其中，encoding代表contents中存储内容的类型，虽然contents是int8_t类型，但是实际上存储的值是int16_t int32_t和int64_t 具体的类型由encoding决定，length表示元素个数。

整数集合适用于所有元素都是整数，并且集合元素数量较小，和哈希表相比，整数集合的优势在于集中存储，节省空间。同时虽然对于操作的复杂度变化了，但是集合的数量比较小，所以劣势不明显

（3）编码转换

转换条件有两个

集合元素小于512个
集合中所有元素都是整数值
下图展示了集合编码转换的特点：

image.png

5、有序集合

（1）概况

有序集合和集合一样，元素都不能重复，但是和集合不同的是，有序集合的元素是有顺序的，于列表使用索引下标作为排序依据不同，有序集合为每一个元素设置了一个分数作为排序依据。

（2）内部编码

有序集合内部编码可以是压缩列表和跳表。压缩列表前面依据讲过了，主要将一下跳表

如何理解跳表，在了解跳表之前，我们先讲一下普通的链表
首先不同的单链表，即使链表是有序的，我们要查找某个元素的时候，也需要从头遍历到尾，时间复杂度为O(n)。

image.png

那么有没有可以提高查询效率的方法呢，我们可以尝试为链表建立索引来提升查询效率，如图，我们在原始链表的基础上，没两个元素提取一个索引，down指向原始链表节点，如图：

image.png

此时，加入我们要查询19的节点，我们从索引层开始遍历，当遍历到16时，下一个节点是23，所以19一定在两个节点之间，我们通过16节点的down指针来到原始链表，将继续遍历，知道找到19，在没有所以之前，我们需要8次，有了之后只需要6次。
如果我们再建立一层索引，如图：

image.png

找到19虽然还是6次，但是如果数据量大的时候，会有比较明显的效果。
跳表的时间复杂度
假设链表有N个节点，每两个节点生产一个索引，则有第一层索引的节点个数为N/2，第二层为N/4，第N层节点的个数就是N/(2^h) 那么h=log2n-1，再加上原始链表，那么整个跳表的高度就是log2n.
我们在查询某个数据的时候，每一层需要遍历M个节点，那么在跳表中查询某个数的时间复杂度就是O(m*log2n)。那么M是多少呢，按照每两个节点上升一个索引，那么m=3，如图解释：

image.png

因此，跳表的时间复杂度就是O(3log2n).

（3）编码转换

只有满足两个条件才会转换：

有序集合的元素小于128个
集合中所有成员长度都不足24
转换如下图：

image.png