为什么需求 SkipList(跳表)

在普通链表中查找元素的时分,由于需求遍历查找,所以查询效率非常低,时刻复杂度是O(N)。

因而咱们需求跳表。跳表是在链表基础上改进过来的,完成了一种 “多层”有序 链表,这样的优点是能快速定位数据。

跳表的结构设计

如下图所示,这是一个层级为3的跳表

浅析 Redis 底层数据结构 SkipList

  • 和普通的双向链表相同,SkipList 都有一个指向上一个节点的指针,也有一个指向下一个节点的指针。

  • 可是你会发现,在层次为 3 的跳表中,会有三级指针的存在,而且 SkipList 中元素会依照 score 值升序排序(score 值相同则依照 ele 排序)

    • 一级指针普通链表相同,指向下一个节点(图中的 L0)
    • 二级指针跨度为2,指向的节点与自己间隔了一个节点
    • 三级指针跨度为3,指向的节点与自己间隔了两个节点

这样的设计会带来什么优点呢?

  • 假定咱们要在普通链表中查询值为 3 的节点,咱们需求从头结点开端,向后遍历1 → 2 → 3 ,三个节点才能找到。时刻复杂度为 O(n)O(n)
  • 当使用了 SkipList 这个数据结构之后,咱们可以直接经过三级指针(L2),直接找到这个节点(建立在元素有序的情况下,相似于二分查找一步一步缩小规模)。时刻复杂度为 O(logN)O(log N)

跳表的节点(zskiplistNode )

咱们来看看跳表的结构体源码

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

其中,

  • ele,用于存储该节点的元素
  • score,用于存储节点的分数(节点依照 score 值排序,score 值相同则依照 ele 排序)
  • *backward,指向上一个节点

level[] 便是完成跳表多层次指针的关键所在,level 数组中的每一个元素代表跳表的一层,比如 leve[0] 就表明第一层,leve[1] 就表明第二层。zskiplistLevel 结构体里定义了指向下一个跳表节点的指针** *forward 和用来记载两个节点之间的间隔 span,如图所示,

浅析 Redis 底层数据结构 SkipList

span 跨度有什么用?


  • 第一眼看到跨度的时分,你或许以为是遍历操作有关,实际上并没有任何关系,遍历操作只需求用前向指针(struct zskiplistNode *forward)就可以完成了。
  • 跨度实际上是为了核算这个节点在跳表中的方位。具体怎样做的呢?
  • 由于跳表中的节点都是按序摆放的,那么核算某个节点方位的时分,从头节点点到该结点的查询途径上,将沿途访问过的一切层的跨度累加起来,得到的结果便是方针节点在跳表中的排位。
  • 举个比如,查找图中节点 3 在跳表中的排位,从头节点开端查找节点 3,查找的进程只经过了一个层(L2),而且层的跨度是 3,一切节点 3 在跳表中的排位是 3。

跳表(zskiplist )

跳表的结构如下

    typedef struct zskiplist {
        struct zskiplistNode *header, *tail;
        unsigned long length;
        int level;
    } zskiplist;
  • zskiplistNode *header, *tail ,跳表的头尾节点
  • length,跳表的长度
  • level,跳表的最大层数

跳表的查询进程

  • 在使用 ZRANGEBYSCORE key min max进行规模查询的时分

    • redis 会调用 zslFirstInRangezslLastInRange 函数获取契合规模条件的开端节点(正序调用**zslFirstInRange** ,逆序调用**zslLastInRange** )

    • 获取开端节点之后,进入一个循环,每次迭代时都会查看节点的分数是否仍在规模内(假如存在偏移量,越过指定数量的元素,而不进行分数的查看),假如不在规模内,则中止循环。

    • 这样就能获取指定分数内的一切元素。

    可在 t_zset.c#genericZrangebyscoreCommand(zrange_result_handler *handler, zrangespec *range, robj *zobj, long offset, long limit, int reverse) 查看源码

zslFirstInRangezslLastInRange 相似)中,咱们就能看到跳表依据 scroe 值的查询进程,源码如下:

    /* Find the first node that is contained in the specified range.
     * Returns NULL when no element is contained in the range. */
    zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range) {
        zskiplistNode *x;
        int i;
        /* If everything is out of range, return early. */
        if (!zslIsInRange(zsl,range)) return NULL;
        x = zsl->header;
        for (i = zsl->level-1; i >= 0; i--) {
            /* Go forward while *OUT* of range. */
            while (x->level[i].forward &&
                !zslValueGteMin(x->level[i].forward->score,range))
                    x = x->level[i].forward;
        }
        /* This is an inner range, so the next node cannot be NULL. */
        x = x->level[0].forward;
        serverAssert(x != NULL);
        /* Check if score <= max. */
        if (!zslValueLteMax(x->score,range)) return NULL;
        return x;
    }

该函数执行逻辑如下:

  1. 首先,经过调用 zslIsInRange 函数查看整个有序集合是否都在规模之外,假如是,则直接回来空,表明规模内不存在满意条件的节点。
  2. 初始化变量 x 为跳表的头节点。
  3. 从跳表的最高层级开端逆序遍历每个层级,直到到达最底层级
  4. 在每个层级中,经过比较节点的分数(score)和规模的最小值,向前遍历跳表,直到找到第一个在规模内的节点
  5. 终究,变量 x 存储的是规模内第一个节点的前一个节点。
  6. 使用 serverAssert 函数进行断语,确保变量 x 的下一个节点不为空(假如跳表中存在节点,则下一个节点不应为空)。
  7. 更新变量 x 为下一个节点,即规模内的第一个满意条件的节点。
  8. 查看变量 x 的score 是否小于等于规模的最大值,假如大于最大值,则回来空,表明规模内不存在满意条件的节点。
  9. 回来变量 x,即规模内的第一个满意条件的节点。

简单来说在 SkipList 中找到一个元素的过程如下:


  1. 从跳表的顶层开端,从左到右遍历指针,直到找到一个指针指向的值大于或等于方针元素。记载下该方位作为当时方位。
  2. 假如当时方位指向的值等于方针元素,则找到了方针元素,查找结束
  3. 假如当时方位的下一个指针存在且指向的值小于方针元素,将当时方位向右移动到下一个指针所指向的方位。重复过程1。
  4. 假如当时方位的下一个指针不存在或指向的值大于方针元素,将当时方位向下移动一层。重复过程1。