Redis第十二讲 Redis之zset底层数据结构实现_zset的底层实现

zset

zset中的每个元素包含数据本身和一个对应的分数(score)。ZSet 为有序的，自动去重的集合数据类型，ZSet 数据结构底层实现为 ziplist+或跳表(skiplist) ，zset的数据本身不允许重复，但是score允许重复。

使用ziplist的条件

• 有序集合保存的元素数量小于128个
• 有序集合保存的所有元素的长度小于64字节

这两个数值是可以通过redis.conf的zset-max-ziplist-entries 和 zset-max-ziplist-value选项 进行修改。

zset-max-ziplist-entries 128 // 元素个数超过128 ，将用skiplist编码

zset-max-ziplist-value 64 // 单个元素大小超过 64 byte, 将用 skiplist编码
1
2
3

数据少时，并且每个元素要么是小整数要么是长度较小的字符串时使用ziplist.

ziplist占用连续内存，每项元素都是（数据+score）的方式连续存储，按照score从小到大排序。ziplist为了节省内存，每个元素占用的空间可以不同，对于大的数据（long long），就多用一些字节来存储，而对于小的数据（short），就少用一些字节来存储。因此查找的时候需要按顺序遍历。ziplist省内存但是查找效率低。

当ziplist作为zset的底层存储结构时候，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，第二个元素保存元素的分值。

关于ziplist数据结构，可以参考我之前在list底层结构实现里的文章：Redis第六讲 Redis之List底层数据结构实现

zset数据结构

数据多时，使用字典+跳表：跳表是基于一条有序单链表构造的，通过构建索引提高查找效率，空间换时间，查找方式是从最上面的链表层层往下查找，最后在最底层的链表找到对应的节点：

typedef struct zset{
   
     zskiplist *zsl;       //跳跃表 按分值排序成员  用于支持平均复杂度为 O(log N) 的按分值定位成员操作以及范围操作
     dict *dice;           //字典  键为成员，值为分值  用于支持 O(1) 复杂度的按成员取分值操作
} zset;

1
2
3
4
5
6

当skiplist作为zset的底层存储结构的时候，使用skiplist按序保存元素及分值，使用dict来保存元素和分值的映射关系。

skiplist作为zset的存储结构，整体存储结构如下图，核心点主要是包括一个dict对象和一个skiplist对象。dict保存key/value，key为元素，value为分值；skiplist保存的有序的元素列表，每个元素包括元素和分值。两种数据结构下的元素指向相同的位置。

skiplist

zset包括dict和zskiplist两个数据结构，其中dict的保存key/value，便于通过key(元素)获取score(分值)。zskiplist保存有序的元素列表，便于执行range之类的命令。

zskiplist作为skiplist的数据结构，包括指向头尾的header和tail指针，其中level保存的是skiplist的最大的层数。

/*
 * 跳跃表
 */
typedef struct zskiplist {
   
    struct zskiplistNode *header, *tail;// 表头节点和表尾节 
    unsigned long length;  				// 表中节点的数量
    int level;    						// 表中层数最大的节点的层数
} zskiplist;
1
2
3
4
5
6
7
8
9

skiplist跳跃列表中每个节点的数据格式，每个节点有保存数据的robj指针，分值score字段，后退指针backward便于回溯，zskiplistLevel的数组保存跳跃列表每层的指针。

/*
 * 跳跃表节点
 */
typedef struct zskiplistNode {
   
    robj *obj;					      		// 成员对象
    double score;      						 // 分值
    struct zskiplistNode *backward;  		 // 后退指针
    struct zskiplistLevel {
              		// 层
        struct zskiplistNode *forward;       // 前进指针   
        unsigned int span;        			// 跨度
    } level[];
} zskiplistNode;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

其实有序集合单独使用字典或跳跃表其中一种数据结构都可以实现，但是这里使用两种数据结构组合起来，原因是假如我们单独使用 字典，虽然能以 O(1) 的时间复杂度查找成员的分值，但是因为字典是以无序的方式来保存集合元素，所以每次进行范围操作的时候都要进行排序；假如我们单独使用跳跃表来实现，虽然能执行范围操作，但是查找操作有 O(1)的复杂度变为了O(logN)。因此Redis使用了两种数据结构来共同实现有序集合。

// 创建zset 数据结构: 字典 + 跳表
robj *createZsetObject(void) {
   
    zset *zs = zmalloc(sizeof(*zs));
    robj *o;
    // dict用来查询数据到分数的对应关系， 如 zscore 就可以直接根据 元素拿到分值 
    zs->dict = dictCreate
1
2
3
4
5
6