1、ziplist 压缩列表

1.1 概述

压缩列表是Redis为了节约内存而开发，是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空间。

Redis 为了节约内存空间使用，zset 和 hash 容器对象在元素个数较少的时候，采用压缩列表 (ziplist) 进行存储。3.2.0版本之前, 当 List 容器对象在元素个数较少的时候，也采用压缩列表 (ziplist) 进行存储, 3.2.0之后 List 全部使用 quickList(快速列表)

1.2 数据结构

image.png

struct ziplist<T> {
    int32 zlbytes; // 4 byte, 记录整个压缩列表占用内存字节数,在内存分配或者计算 zlend 的位置时使用
    int32 zltail_offset; // 4 byte, 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
    int16 zllength; // 2 byte, 元素个数当属性值 < 65535 时, 属性值表示节点个数, 当属性值 = 65535 时, 真实节点个数需要遍历压缩列表才能计算得出
    T[] entries; // 元素节点列表，节点之间挨个紧凑存储,无冗余空间
    int8 zlend; // 1 byte,标志压缩列表的结束，值恒为 0xFF
}

真正保存的数据是在元素节点entries中的content，每个压缩列表的节点可以保存一个字节数组或者一个整数值

struct entry {
 // 前一个 entry 的字节长度,
 // 前一个节点长度小于254字节,则该属性用一个字节表示, 否则(大于等于254字节)用五个字节表示,第一个字节被设置为0xFE(254), 后四个字节表示前一个节点长度
    int<var> prevlen;

// 记录了节点的 content 属性所保存的数据的类型及长度
//当属性长度为 1 2 5 字节,值最高位为 00 01 10 时表示为字节数组, 数组长度有编码去除最高2位之后的其他位记录, 当属性长度为 1 字节长, 最高位以 11 开头表示是整数编码,整数的类型和长度有编码去除最高2位的其他位表示
    int<var> encoding; 

// 保存节点的值, 可以是一个字节数组或者整数
    optional byte[] content; 
}

2、quicklist 快速列表

2.1 概述

我们知道，链表中每个节点都会有prev 和 next 指针，每个指针占用8个字节，同时，其每个节点的内存都是单独分配的，这会加剧内存的碎片化，影响内存管理效率。对于redis来说，内存是相当宝贵的。所以有了quicklist。

2.2 数据结构

image.png

从上面可以看出，quicklist其实就是ziplist作为节点元素组成的链表。

// 快速列表
struct quicklist {
    quicklistNode* head;
    quicklistNode* tail;
    long count; // 元素总数
    int nodes; // ziplist 节点的个数
    int compressDepth; // LZF 算法压缩深度
    ...
}
// 快速列表节点
struct quicklistNode {
    quicklistNode* prev;
    quicklistNode* next;
    ziplist* zl; // 指向压缩列表
    int32 size; // ziplist 的字节总数
    int16 count; // ziplist 中的元素数量
    int2 encoding; // 存储形式 2bit，原生字节数组还是 LZF 压缩存储
    ...
}

2.3 zipList 长度

quicklist 内部默认单个 ziplist 长度为 8k 字节，超出了这个字节数，就会新起一个 ziplist。

ziplist 的长度由配置参数 list-max-ziplist-size 决定。

3、zskiplist

3.1 概述

跳跃表是一种有序的数据结构，通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的
大部分情况下, 跳跃表的效率可以和平衡树相媲美
Redis中只在两处用到了跳跃表，一个是实现有序集合，另一个是 集群节点中用作内部数据结构

3.2 数据结构

image.png

typedef struct zset {
    dict *dict; // 字典
    zskiplist *zsl; // 跳跃表
} zset;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头节点 尾节点
    unsigned long length; // 节点个数
    int level; // 最高层数
} zskiplist;


typedef struct zskiplistNode {
    sds ele; //成员
    double score; // 分值
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned long span; // 跨度
    } level[]; // 多层连接指针
} zskiplistNode;

每个跳跃表节点都保存一个元素，并按分值从小到大排列；节点的object属性保存了元素的成员，score属性保存分值；

字典的每个键值对保存一个元素，字典的键保存元素的成员，字典的值保存分值

4、总结

在Redis的五大数据对象中，string对象是唯一个可以被其他四种数据对象作为内嵌对象的；

列表（list）、哈希（hash）、集合（set）、有序集合（zset）底层实现都用到了压缩列表结构，并且使用压缩列表结构的条件都是在元素个数比较少、字节长度较短的情况下；

四种数据对象使用压缩列表的优点：

• 节约内存，减少内存开销，Redis是内存型数据库，所以一定情况下减少内存开销是非常有必要的。

• 减少内存碎片，压缩列表的内存块是连续的，并分配内存的次数一次即可。

• 压缩列表的新增、删除、查找操作的平均时间复杂度是O(N)，在N再一定的范围内，这个时间几乎是可以忽略的，并且N的上限值是可以配置的。

• 四种数据对象都有两种编码结构，灵活性增加。