redis的几个数据结构 —— zset

zset实现和解析

zset是redis中比较经典的数据结构了,有序集合,带分值可排序,有序集合的硬性需求有这两条:

  • 分值区间获取key
  • 通过key直接获取分值

而redis中zset其各个操作的时间复杂度如下:

  • 获取分值:O(1)
  • 添加元素:O(M*log(N)), N 是有序集的基数, M 为成功添加的新成员的数量
  • 返回指定区间内的元素:O(log(N)+M)

层高

redis中zset是通过哈希表和跳表来实现的:
---1

插入跳表的时候是从上往下,从前往后找到插入点后插入。插入之后需要计算其层高,如果高于现有的层,则需要为这个新节点新建一层。

层太高不是好事,太高的层数往往并不会提供额外的性能。

实际使用时,如果高度太高,会造成空间浪费,我们要做一个空间和时间的平衡。那么跳跃表的高度多少最合适?

假设跳跃表中的元素个数为N,当跳跃表的高度为log(N)时,跳跃表进化为一个二叉树结构,其查询次数与二分查找法一致。这无疑是最理想的结果。

如果有一亿条记录,高度log(N)约等于30。redis中,最大高度也就是32,最多可以存几亿条记录。通常,我们用不了这么多记录。所以高度可以降低一点。

具体到redis中,其新插入节点的层高,则是通过下面的代码算出来的:

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

其中ZSKIPLIST_MAXLEVEL为64,ZSKIPLIST_P为0.25。

我们来算一下层高的期望:

  • 节点层高为1的概率为(1-𝑝)
  • 节点层高为2的概率为𝑝(1-𝑝)
  • 节点层高n的概率𝑝^(n−1) (1−𝑝)

所以层高的期望为 1/(1-0.25) ≈ 1.33
zset-levelE

comments powered by Disqus