redis数据结构(六) 有序集合对象

有序集合的底层实现可以是压缩列表或者跳跃表+字典。压缩列表就不再重复了。

跳跃表

跳跃表原理

什么是跳表?对于一个普通的单链表而言,无论是否有序,其查询的时间复杂度都是O(n)

那我们如何更高效的查找呢?跳跃表提供了一种思想,如下图所示,我们建立多级“索引”,每一级可以叫做每一层,每一个level。

其思想和二分查找(Binary Search)也挺相似的,从一个粗略的范围逐步缩小。在上图中,我们从二级索引开始查询,然后进入到一级索引,在一级索引时整个数组已经被分成一半了,从而提高了效率。

而跳表的时间复杂度与我们每隔几个结点就建立一个索引点有关,如果我们每隔两个点就建立一级索引点,那么其实就是二分查找了。时间复杂度为O(logn)。

源码分析

跳表

跳表的原理大致如上图,那么深入到源码这边,我们看下跳表的定义:

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;
  • header:指向跳跃表的表头结点
  • tail:指向跳跃表的表尾结点
  • level:记录跳跃表内,层数最大的那个结点的层数
  • length:记录跳跃表的长度,即结点数量(表头结点不计算在内)

例如前面讲原理举的例子,放在这个结构中就是上图所示。length为5,level为3,header是1,tail是9。

跳表结点

结点的定义如下:

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;
  • ele:sds类型,简单动态字符串,表示这个结点存的值
  • score:分值,跳跃表中的所有结点都按照分值从小到大排列
  • backward:指向后退的结点,用于从表尾往表头遍历
  • forward:前进的结点
  • span:指从当前结点前进到下一个结点的跨度。用来计算排位。

有序集合对象

当编码是skiplist的时候,zset的底层实现是采用字典+跳跃表的:

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

通过跳跃表,按分值从小到大排序,可以对有序集合进行范围型操作,如ZRANK、ZRANGE。

通过字典,将键作为元素,值作为分值,可以进行O(1)复杂度的查询。

并且上述两个结构都是通过指针指向同一块内存,因此不会浪费。

编码转换

当有序集合对象可以同时满足以下两个条件时,对象使用ziplist编码:

  • 有序集合保存的元素数量小于zset-max-ziplist-entries个(默认128)
  • 有序集合保存的所有元素成员的长度都小于zset-max-ziplist-value字节(默认64)

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

浙ICP备19002997号