为什么需求 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 会调用 zslFirstInRange 或 zslLastInRange 函数获取契合规模条件的开端节点（正序调用**zslFirstInRange** ，逆序调用**zslLastInRange** ）

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

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

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

在 zslFirstInRange （zslLastInRange 相似）中，咱们就能看到跳表依据 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。