zset为有序的，自动去重的集合数据类型，zset数据结构底层实现为字典(dict)+跳表(skiplist)当数据比较少时，用ziplist编码数据结构存储，当满足以下条件之一时，则采用字典+跳表来存储
zset-max-ziplist-entries 128 //元素个数超过128，将用skiplist编码
zset-max-ziplist-value 64 //单个元素大小超过64byte，将用skiplist编码
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
对于字典(dict)的数据结构来说，可以用O(1)的复杂度拿到对应元素
比如zscore命令
zscore key value 就可以拿到以key为键，value的对应的分值，这个就是在字典(dict)的数据结构中取的，字典(dict)数据结构主要用于判断值是否存在以及拿对应的分值，这个不是我们文章阐述的重点，重点看一下跳跃表(skiplist)的数据结构，看看它是如何实现排序的
skiplist的实现
首先我们来看一看链表的数据结构示意图
链表.png
链表的话查找我们所需的元素的时间复杂度为O(n)，显然这是我们不能接受的，所以需要对链表进行一步改造
跳跃表.png
我们每隔两个元素给加一层，然后我们查询从索引层开始查询，遇到了比目标元素大的元素再返回，前往数据层来查询，这样速度会快一些，但是这样速度快的不明显，大概也就快了一半左右，于是我们便想到了加高层数
多层跳跃表.png
其实按照上图我们可以计算一下
元素的总个数为N
那么在上图的所以第一层,元素的个数为n/2
index: 1 n/2
那么在上图的所以第二层,元素的个数为n/2^2
index: 2 n/2^2
那么在上图的所以第三层,元素的个数为n/2^3
index: 3 n/2^3
那么在上图的所以第K层,元素的个数为n/2^k
index: k n/2^k
比如顶层为2个节点
2 = n/2^k
也就是说 2^k = n/2 ----> k=log2(n-1)
加上数据层的话 k = log2 n
所以我们的层高是 log2 n
查找的时候的时间复杂度是log n
我们可以来看一下skiplist的源码
// zskiplistNode包含了数据和索引，也就是跳表中的一列
typedef struct zskiplistNode {
sds ele; //元素
double score; //分数
struct zskiplistNode *backward; //往前指的指针
struct zskiplistLevel {
struct zskiplistNode *forward;//往后指的指针
unsigned long span; // 从当前节点到下一个节点的跨度
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail; //header和tail是方便双向遍历
unsigned long length; //当前数据包含元素个数
int level; // 层高
} zskiplist;
skiplist.png
如何确定索引层的层高
索引层的层高是由一个随机函数，幂次定律实现的
int zslRandomLevel(void) { //幂次定律，随机生成层高，越高的层出现概率越低
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
网友评论