数据结构-redis数据结构-跳表skiplist

这篇文章简略共享学习redis(6.0)数据结构-跳表skiplist

redis中的有序数据集合[zset],有两种完成方法：跳表和紧缩列表，咱们今日学习下跳表的完成原理。

学习新的常识，咱们先从已掌握的常识下手，由浅入深，让咱们先从普通链表开端，如果期望一个集合有序，咱们会想到经过有序链表完成：

咱们在该单链表中查询元素[15],经过1,3,5,7,9,11,13,15，需求自始至终遍历8次，效率很低。单链表的查询时刻复杂度为O(N)。

怎么提高查询效率呢？咱们可认为链表树立“索引”：每两个元素提取一层树立索引：

然后咱们在新的两层链表中查询元素[15],经过1,5,9,13,15，需求查询5次。经过树立索引达到了削减查询次数的意图。时刻复杂度为$O(logN)$。

这便是咱们要认识的跳表：跳动表（跳表）是一种有序数据结构，它经过在每个节点中保持多个指向其他节点的指针，然后达到快速拜访节点的意图。

下面咱们剖析下跳表的时刻复杂度怎么核算的：

假设咱们严厉的依照每两个元素提取一层树立索引，如上图的三层索引，N：元素的总规划，h：索引层高

第一层索引元素个数：$N/2$，

第二层索引元素个数$N/2\ast 2$，

第三层索引元素个数$N/2\ast 2\ast 2$

咱们能够得到 数据总规划N与索引层高h的函数联系，最底层的索引元素个数为$2=N/2h$，即可推出$h=log2N-1$，再加上最底层的原始链表 $h=log2N$ (log以2为底N的对数)

跳表的时刻复杂度 = 层高（h） * 每层遍历的个数(m)，当数据规划很大的时分，咱们能够忽略常数项m，所以链表的时刻复杂度$O(logN)$

咱们上面的比方是为了阐明跳表的根本结构，简化的模型，下面再举个更直观的比方，当数据量很大时，能够明显的看到极大的提高查询效率：

比方查找9998，经过树立索引咱们能削减许多的查询进程。

---

---

以上咱们简略认识了跳表，今日的重点是剖析redis中跳表的数据结构。

Redis的跳动表完成和WillianmPugh[WillianmPugh博士在他的论文中提出跳表的数据结构]在“SkipLists:AProbabilisticAlternativetoBalancedTrees”中描述的跳动表算法类似，但又有有些区别：

1、Redis的跳动表答应分值重复；
2、Redis的跳动表排序不止根据分值，在分值相同的时分会对比成员目标；
3、Redis的跳动表有一个撤退指针，形成了一个双向链表，能够从表尾向表头遍历，用于ZREVRANGE命令的完成。

Redis的跳动表由 zskiplistNode 和 skiplist 两个结构定义：

zskiplistNode结构用于表明跳动表节点；
zskiplist结构则用于保存跳动表节点的相关信息,比方节点的数量,以及指向表头节点和表尾节点的指针等

skiplist

header：指向跳动表的表头节点。
tail：指向跳动表的表尾节点。
length：记载跳动表的长度，即除去表头节点之外的节点数量之和。
level：记载跳动表内层数最大的那个节点的层数（表头节点的层数不核算在内）。

zskiplistNode

ele：用于记载跳动表节点的值，类型是 SDS。
score：保存跳动表节点的分值，在跳动表中，节点按各自所保存的分值从小到大排列。
backward：撤退指针，它指向当时节点的前一个节点，在程序从表尾向表头遍历时运用。由于一个跳动表节点只要一个撤退指针，所以每次只能撤退至前一个节点。
level：跳动表节点的层，每个层都带有两个特点：前进指针 forward 和跨度 span。前进指针用于拜访坐落表尾方向的其他节点，而跨度则记载了前进指针所指向节点和当时节点的间隔。每个跳动表节点最多有 32 层。

zskiplistLevel包括以下两个特点：

forward：指向同一层的下一个节点，为节点的forward指向NULL
span：forward指向的节点与本节点之间的节点的个数，span越大阐明越过的节点的个数越多

下面咱们剖析下跳表刺进节点的进程，有助于进一步了解跳表的数据结构及完成原理：

**1、查找要刺进的方位**
update[]：用来保存刺进节点每一层的前一个节点。update[i]表明Node M刺进后的第i层的前一个节点
rank[]：用来保存头节点到update[i]节点的间隔。rank[i]表明header节点到update[i]节点的间隔
咱们经过下面这段代码，详细剖析怎么更新update和rank这两个数组的值。在一个for循环中，从数组下标为level-1开端一向更新到下标为0，在这个比方中，level=3，因而从数组下标2开端更新，先核算update[2]和rank[2]，一向到update[0]和rank[0]。
第一次进入循环，rank[2]的初始值为0，然后经过一个while循环，从头节点的第2层开端一向往后查找，找到终究一个小于Node M的节点，这个节点便是Node M刺进后的第2层的前一个节点，显然这个节点是Node 3，在查找的进程中，会将经过的节点的第2层的span值累加到rank[2]上，因而rank[2]=0(初始值)+1+2=3，（查找途径为从header -> Node 1 -> Node 3）。终究得到update[2]=Node 3，即Node M第2层的前一个节点为Node 3，rank[2]=3，即从header节点到Node 3的间隔为3
第二次进入循环，rank[1]的初始值为rank[2]=3，从Node 3的第1层开端往后查找终究一个小于Node M的节点，这个节点仍然是Node 3，因而update[1]=Node 3，即Node M第1层的前一个节点也是Node 3，rank[1]=3（查找途径停留在Node 3，因而rank[1]终究仍是为初始值）。
第三次进入循环，rank[0]的初始值为rank[1]=3，从Node 3的第0层开端往后查找终究一个小于Node M的节点，这个节点是Node 4，因而update[0]=Node 4，即Node M第0层的前一个节点是Node 4，rank[0]=3+1=4，（查找途径为Node 3 -> Node 4），即header节点到Node 4的间隔为4
2、调整跳表高度
在 Redis 的跳动表中，如果新增一个节点，节点的层数是经过函数 zslRandomLevel 随机出来的，节点层数的范围为 1 到 32，0xFFFF 为 65535，即每次随机都是生成一个 0 到 65535之间的数，总结下来有以下规律：
由于 level 初始化为 1，所以终究层数为 1 的概率为 1-ZSKIPLIST_P，即 0.75。
当终究层数大于 1 时，每次层数添加的概率都是 ZSKIPLIST_P，那么 n 层的概率是 (1-ZSKIPLIST_P ) * ZSKIPLIST_P ^ (n - 1)，即  。
由于层数添加的概率是 ZSKIPLIST_P，能够看成是第 k 层的节点数是第 k+1 层节点数的 1/ZSKIPLIST_P 倍，所以 Redis 的跳动表相当所以一颗四叉树。
节点层高为1的概率为 (1-p)
节点层高为2的概率为 (1-p)*p
节点层高为3的概率为 (1-p)*p^2
...
节点层高为n的概率为 (1-p)*p^2
当节点层高大于32时，终究也会取32，所以实践上节点层高为32的概率为：1 - (节点层高小于32的概率值和)
3、刺进节点
设置Node M的forward特点
将update[i]的forward修正为Node M
设置Node M每一层的span值
修正update[i]的span值
4、调整backward
由于新刺进节点Node M的前一个节点一定是update[0]，因而将Node M的backward设置为update[0]，
Node M的下一节点的backward设置为Node M，然后跳表的长度+1。至此，整个节点的刺进操作就完成了。

这是第一步查询的要刺进的方位的描述：

此处详细剖析了查找刺进节点的进程剖析，由于新增、修正、删去节点都涉及查询

总结下redis的跳表结构：

1、跳动表根据单链表加索引的方法完成
2、跳动表以空间换时刻的方法提高了查找速度
3、Redis有序集合在节点元素较大或者元素数量较多时运用跳动表完成
4、Redis的跳动表完成由 zskiplist和 zskiplistnode两个结构组成,其间 zskiplist用于保存跳动表信息(比方表头         节点、表尾节点、长度),而zskiplistnode则用于表明跳动表节点
5、Redis每个跳动表节点的层高都是1至32之间的随机数
6、在同一个跳动表中,多个节点能够包括相同的分值,但每个节点的成员目标必须是仅有的跳动表中的节点依照分值大小进行排序,当分值相同时,节点依照成员目标的大小进行排序

附带刺进节点的部分代码

1、查找要刺进的方位

/* Insert a new node in the skiplist. Assumes the element does not already
 * exist (up to the caller to enforce that). The skiplist takes ownership
 * of the passed SDS string 'ele'. */
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    //update数组记载新增节点在每一层的前驱节点
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    //rank数组用于记载新增节点在跳动表中的排名
    //表头节点排名为0，所以查找到刺进节点方位时，经过的节点数量之和便是其排名
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;
    serverAssert(!isnan(score));
    //x指向跳动表的头节点
    x = zsl->header;
    //从最高层依次向下遍历
    for (i = zsl->level-1; i >= 0; i--) {
        /* store rank that is crossed to reach the insert position */
        //最高层对应的rank数组的元素初始化为0，其他层初始化为上一层对应的数组元素的值
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        //当时层下一个节点存在
        //当时层下一个节点的分值小于刺进节点的分值
        //当分值相等时，刺进节点的元素大于下一节点元素
        while (x->level[i].forward &&
                (x->level[i].forward->score < score ||
                    (x->level[i].forward->score == score &&
                    sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            //计算当时层查找过的节点跨度之和
            rank[i] += x->level[i].span;
            //节点指针游标后移,持续往后查找刺进方位
            x = x->level[i].forward;
        }
        //记载新增节点在当时层的前驱节点
        update[i] = x;
    }

2、调整跳表高度

/* we assume the element is not already inside, since we allow duplicated
     * scores, reinserting the same element should never happen since the
     * caller of zslInsert() should test in the hash table if the element is
     * already inside or not. */
    //咱们假定元素还没有刺进到跳动表，虽然咱们答应跳动表存在重复的节点分值，重复刺进相同的元素是不答应
    //的，所以在调用 zslInsert 函数之前咱们需求测验一下在哈希表中是否已经存在相同的元素。
    //随机出新节点的层数
    level = zslRandomLevel();
    //新节点的层高大于当时跳动表节点的最大层高
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            //高出的层数只要当时一个节点，所以该层节点跨度之和为0
            rank[i] = 0;
            //高出的层刺进节点的前驱节点是头节点
            update[i] = zsl->header;
            //初始化该层头节点的跨度，实践是头节点到尾节点的间隔
            update[i]->level[i].span = zsl->length;
        }
        //更新跳动表的最高层数
        zsl->level = level;
    }

3、刺进节点

//创立跳动表节点
    x = zslCreateNode(level,score,ele);
    for (i = 0; i < level; i++) {
        //在当时层刺进新节点(这里和链表刺进节点的做法类似)
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;
        /* update span covered by update[i] as x is inserted here */
        //需求核算新增节点的每一层跨度
        //每层的跨度为其后继节点的排名减去新增节点的排名
        //后继节点的排名为：update[i]->level[i].span + rank[i] + 1
        //新增节点的排名为：rank[0] + 1
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        //需求核算新增节点每一层的前驱节点的跨度
        //前驱节点的跨度为：新增节点的排名减去前驱节点的排名
        //新增节点的排名：rank[0] + 1
        //前驱节点的排名为：rank[i]
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }
    /* increment span for untouched levels */
    for (i = level; i < zsl->level; i++) {
        //高出的层，新增节点的前驱是头节点，头节点的跨度是间隔尾部的长度，由于新增节点，所以跨度加1
        update[i]->level[i].span++;
    }

4、调整backward

//设置撤退节点
    //如果新增节点的前驱为头节点，则撤退节点为空
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    //怎么新增节点不是尾节点，则设置其下一个节点的撤退指针指向新增节点
    //撤退节点只能使得逆序遍历时撤退一位，所以只判别第一层
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;
    //跳动表节点数量添加
    zsl->length++;
    return x;