前言，上一篇文章了解了SDS、linkedlist和dict。接下来了解redis中剩余的底层数据结构intset、ziplist和skiplist。

intset(整数集合)

当一个set只包含整数值元素，并且数量不多时，set底层会采用intset实现。

虽然intset结构将contents属性声明为int8_t类型的数组，但实际上contents数组并不保存任何 int8_t类型的值。 contents 数组的真正类型取决于 encoding 属性的值：

如果 encoding 属性的值为INTSET_ENC_INT16，那么 contents 就是一个int16_t类型的数组。
如果 encoding 属性的值为INTSET_ENC_INT32，那么 contents 就是一个int32_t类型的数组。
如果 encoding 属性的值为INTSET_ENC_INT64，那么 contents 就是一个int64_t类型的数组。

升级

一个新元素添加到集合时，如果长度超过了现有的类型，那么要先进行升级。

扩展数组空间大小，为新元素分配空间
升级元素类型，比如原来的类型是INTSET_ENC_INT16，但是新加入的元素超过了INTSET_ENC_INT16能存储的长度，那么就升级成INTSET_ENC_INT32类型。
存入新元素

intset不支持降级操作

图解升级过程

第一步：分配空间，新加入的元素需要用INTSET_ENC_INT32存储，所以需要32 * 4 = 128的空间

第二步：旧的元素升级成INTSET_ENC_INT32，移动到新的位置上。从后往前以此类推，不是从前往后，因为这样不会覆盖掉后面的数据。

第三步：存入新元素

ziplist(压缩列表)

一个普通的链表，每一个节点是一个单独的内存，通过指针链接，会产生内存碎片。为了提高存储效率，ziplist是一整块内存。

上图是ziplist的内存结构，也就是它用一块内存存储的实现原理。

zlbytes：记录整个ziplist的字节数（包括zlbytes自身）
zltail：最后一项（entry）在ziplist中的偏移字节数，比如zltail是60，通过指向压缩列表初始地址的指针p加上zltail偏移量60，就能计算出最后一个entry的地址。
zllen：表示压缩列表包含的节点数，自身只有2个字节大小，所以自身只能表示1111111111111111（65535），所以zllen规定，自身最大只能表示65534，超过这个值就需要遍历整个数据项，才能计算出节点数。
entry：存储数据的节点，有自己的数据结构
zlend：表示压缩列表结尾，是固定的值255

entry

entry如上图，分成3个部分组成。

previous_entry_length

previous_entry_length表示前一个数据项占用的总字节数。previous_entry_length属性的长度可能是1字节，也可能是5字节长。

如果前一个数据项占用字节数小于254，那么previous_entry_length就只用一个字节来表示，这个字节的值就是前一个数据项的占用字节数。
如果前一个数据项占用字节数大于等于254，那么previous_entry_length就用5个字节来表示，其中第1个字节的值是254（作为这种情况的一个标记），而后面4个字节组成一个整型值，来真正存储前一个数据项的占用字节数。

通过previous_entry_length就可以根据当前节点的地址计算出前一个节点的地址，那么就可以一直往前回溯，实现表尾往前的遍历。

encoding

每个entry既可以保存一个字节数组也可以保存一个整数值，通过encoding来记录content中所保存的类型和长度。

如上图，一共有9种情况。
最高位是00,01,10开头的编码，表示content存储着字节数组。
1字节，最高位是11开头的编码，表示content存储着整数值，长度由去除最高位2位的其他位记录。

值得注意的是：1111xxxx 表示极小整数，xxxx 的范围只能是 (0001~1101), 也就是1~13，因为0000、1110、1111都被占用了。读取到的 value 需要将 xxxx 减 1，也就是整数0~12就是最终的value。content的字段不是必须的，在1111xxxx情况下，值就表示在encoding中

连锁更新

前面说过previous_entry_length的长度可能在1字节和5字节之间变化，现在有一种情况，有多个连续的e1-eN节点长度刚好处在临界点上250-253之间。

突然将一个长度大于254字节的节点插入到e1，由于e1的previous_entry_length的长度是1字节无法存储新节点的字节长度需要扩展成5字节，那么e2也无法存储保存了，e2也要扩展，以此类推需要进行一系列的连续扩展，也被称为连锁更新。

skiplist(跳跃列表)

讲redis中的跳表之前，我们先了解一下跳表的概念。

跳表的概念

我们都学过链表的结构，如上图如果需要找到元素值为4的数据，需要从1一直遍历到4。为了查询效率我们可以跳过一些节点比如，直接从1跳到3，从3跳到6这样查询。同理，不止可以只用2层而是多层，越往上层，节点越少，跨越的节点数也越多。

比如下个找17，最高层9开始找，下一个是21，21比17大，肯定9和21之间，9下移一层，找到17。
实际上就是多层的有序链表。

redis中skiplist的实现

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

zskiplist持有zskiplistNode，在zskiplistNode具体存储元素值和元素分数。zskiplist还有一些其他的字段可以更方便的对跳跃列表进行处理。

header：指向跳跃列表头节点
tail：指向跳跃列表尾节点
length：表中节点的数量
level：表示skiplist的总层数，即所有节点层数的最大值。

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;
复制代码

zskiplistNode跳跃表节点的实现。
obj：存储着元素值，指向一个字符串对象，字符串对象保存着一个sds值
score：一个double类型的浮点数。
backward：指向前一个节点的指针（不能跨越多个节点）
level[]：存放指向各层链表后一个节点的指针，也就是这个字段实现了跳跃表的多层有序列表。
forward： 指向后一个节点。
span： 表示2个节点的跨度。span跟遍历无关，而是用来计算排位的。将沿途所有访问过的跨度加起来，就是目标节点在跳跃列表中的排位。

比如上图分值2.0，虚线就是访问的路径，一共经过了2个跨度为1的节点，那么它的排位就是2。

每个跳跃表节点的层高都是 1 至 32 之间的随机数。
在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。
跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。

redisobject(对象)

使用redis时，不管怎么样都是一个key映射着一个value的，key很简单是一个sds的字符串，而value可能是多种类型，string，hash,list等等。而string,hash结构底层又对应着不同的实现sds,ziplist,skiplist等等。

redis一种数据结构，不止只有一种底层实现，而是有着多种实现，比如list可以是ziplist或者linkedlist实现。
redisobject的encoding字段记录着数据结构的底层实现方式。

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;
复制代码

redisObject中的type和encoding就对应着暴露外部的结构，和底层实现。

type：对应着暴露给外部的结构，如string,hash，list,set,zset。
encoding：内部的底层实现，一共有10种编码。
ptr: 数据指针。指向真正的数据。比如，一个代表string的robj，它的ptr可能指向一个sds结构；

type命令

可以使用type命令获取对应的数据类型。

OBJECT ENCODING命令

可以使用OBJECT ENCODING命令获取对应的底层实现。

编码与底层实现

字符串对象（String）

字符串的编码有三种：int、raw、embstr。

int：如果保存的是一个整数值，并且可以用long类型表示
raw：如果保存的是一个字符串值并且长度大于32，那么使用sds保存，并将编码设置成raw。
embstr：如果保存的是一个字符串值并且长度小于等于32，那么使用embstr的编码保存。

embstr

embstr是一种专门用来保存短字符串的编码方式。embstr和raw都是使用redisobject和sds保存字符串。但是raw会调用两次分配内存分别创建redisobject和sds，而embstr只会调用一次分配内存，用一个连续的空间存redisobject和sds。

列表对象（list）

列表对象的编码有2种：ziplist、 linkedlist。

列表保存的所有字符串长度都小于64字节。
列表保存的元素数量小于512个。

当以上2个条件都满足时，使用ziplist，否则使用linkedlist。

哈希对象（hash）

hash对象的编码有2种：ziplist、 dict。

ziplist

当ziplist作为hash的底层实现时，程序现将保存了键的节点推入压缩列表，然后将保存了值的节点推入压缩列表。因为压缩列表中键值对总是紧挨在一起，键在前，值在后。

hash对象保存的所有键值对的键和值的字符串长度都小于64字节。
hash对象保存的键值对数量小于512个。

当以上2个条件都满足时，使用ziplist，否则使用dict。

集合对象（set）

set的编码有2种：intset、 dict。使用dict时，使用键保存，值都是null。

set对象保存的所有元素都是整数值。
set对象保存的元素数量不超过512个。

当以上2个条件都满足时，使用intset，否则使用dict。

有序集合对象（zset）

set的编码有2种：ziplist、 skiplist。

ziplist： 和hash很像，不过是前面保存元素成员，后面保存元素分值。成员和分值的位置也是一前一后紧挨着的，集合元素按照分值大小，从前往后排序，分值小在前，分值大在后。

skiplist： skiplist编码的zset，底层是通过dict加skiplist一起实现的。

typedef struct zset{
	zskiplist *zsl;
	dict *dict;
} zset;
复制代码

dict：键保存着元素成员，而值保存着元素分数。通过这个字典可以用O(1)的复杂度找到成员的分值，这也是ZSCORE的原理。
zsl：跳跃表从小到大按序保存了集合元素，通过这个跳跃表可以进行有序操作，如ZRANK,ZRANGE命令。

事实上dict和zskiplist都使用指针来共享元素和分数，不会产生冗余数据。

zset对象保存的所有元素成员长度都小于64字节。
zset对象保存的元素数量小于128个。

当以上2个条件都满足时，使用ziplist，否则使用skiplist。

内存回收

因为c语言不具备自动回收内存的功能，所以redis使用引用记数的方式自己实现了一套内存回收机制。

在创建一个新对象时，引用计数的值会被初始化为1。
当对象被一个新程序使用时，它的引用计数值会被增一。
当对象不再被一个程序使用时，它的引用计数值会被减一。
当对象的引用计数值变为0时，对象所占用的内存会被释放。

对象的空闲时长

redisobject中除了之前讲的几个属性，还要一个lru的属性。该属性记录了对象被最后一次访问的时间。

OBJECT IDLETIME命令可以获取指定键的空闲时长，就是用当前时间减去值对象的lru的值算出来的。（这个命令本身是特殊的，不算访问的，不会去修改lru的值）

当淘汰策略是volatile-lru或allkeys-lru时，服务器会优先释放空闲时长较高的键，从而回收内存。

后记

以上就已经介绍完了redis里所有的底层数据结构。

感觉跳跃链表没解释清楚可以看这篇文章：zhangtielei.com/posts/blog-…

redis：底层数据结构与对象（二）intset(整数集合