redis zset底层实现

1.Redis zset底层实现

转载自：https://marticles.github.io/2019/03/19/%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3Redis-Zset%E5%8E%9F%E7%90%86/

zset底层是压缩列表 + 跳表实现的。

跳表里面又由字典hash表 + 跳表实现。

什么时候用压缩列表？什么时候用跳表？

有两个参数控制：

当ziplist保存的元素的个数超过某个阈值或者元素的member的长度大于某个阈值的时候。就会用跳表

元素在压缩列表中存储的时候，是连续的，先存放member，再存放分数；而且是按分数从小到大进行排序。

/* zset结构体 */
typedef struct zset {// 字典，维护元素值和分值的映射关系dict *dict;// 按分值对元素值排序序，支持O(logN)数量级的查找操作zskiplist *zsl;
} zset;

跳表结构：字典hash表 + 跳表

1.字典hash表存储的是member到score的映射，可以做到O(1)时间复杂度来查找member对应的score值

2.跳表按score从小到大保存所有的元素。查找元素的时间复杂度可以达到O(logN)

虽然有两种结构，但是它们会通过指针来共享相同元素的member和score，因此并不会浪费内存。