phpredis跳表技巧_Redis源码剖析之跳表skiplist

打算机领域有很多种数据构造，数据构造的存在要么是为了节省韶光、要么是为了节省空间，或者二者兼具，以是就有部分数据构造有韶光换空间，空间换韶光之说。
实在还有某些以捐躯准确性来达到节省韶光空间的数据构造，像我之间讲过的bloomfilter便是个中的范例。
而本日要讲的skiplist也是一种概任性数据构造，它以一种随机概率降数据组织成多级构造，方便快速查找。

究竟作甚跳表？我们先来考虑下这个场景，假设你有个有序链表，你想看某个特定的值是否涌如今这个链表中，那你是不是只能遍历一次链表才能知道，韶光繁芜度为O(n)。

可能有人会问为什么不直接用连续存储，我们还能用二分查找，用链表是想连续保留它修正韶光繁芜度低的上风。
那我们如何优化单次查找的速率？实在思路很像是二分查找，但单链表无法随机访问的特性限定了我们，但二分逐渐缩小范围的思路启示了我们，能不能想什么办法逐渐缩小范围？

我是不是可以在原链表之上新建一个链表，新链表是原链表每隔一个节点取一个。
假设原链表为L0，新链表为L1，L1中的元素是L0中的第1、3、5、7、9……个节点，然后再建立L1和L0中各个节点的指针。
这样L1就可以将L0中的范围缩小一半，同理对L1再建立新链表L2……，更高level的链表划分更大的区间，确定值域的大区间后，逐级向下缩小范围，如下图。
假设我们想找13，我们可以在L3中确定2-14的范围，在L2中确定8-14的范围，在L1中确定10-14的范围，在L0中找到13，整体探求路径如下图赤色路径，是不是比直接在L0中找13的绿色路径所经由的节点数少一些。

实在这种实现很像二分查找，只不过事先将二分查找的中间点存储下来了，用额外的空间换取了韶光，很随意马虎想到其时间繁芜度和二分查找同等，都是O(logn)。
小伙子很牛X吗，发明了这么牛逼的数据构造，能把有序链表的查找韶光繁芜度从O(n)降落到O(logn)，但是我有个问题，如果链表中插入或者删除了某个节点怎么办？，是不是每次数据变动都要重修全体数据构造？实在不必，我们不须要严格担保两两层级之间的二分之一的关系，只须要概率上为二分之一就行，删除一个节点好说，直接把某个层级中对应的改节点删掉，插入节点时，新节点以指数递减的概率往上层链表插入即可。
比如L0中100%插入，L1中以1/2的概率插入，如果L1中插入了，L2中又以1/2的概率插入…… 把稳，只要高Level中有的节点，低Level中一定有，但高Level链表中涌现的概率会随着level指数递减，终极跳表可能会长这个样子。
我们就这样重新发明了skiplist。

Redis为了供应了有序凑集(sorted set)干系的操作(比如zadd、zrange)，其底层实现便是skiplist。
我们接下来看下redis是如何实现skiplist的。

typedef struct zskiplist { struct zskiplistNode header, tail; // 头尾指针 unsigned long length; // skiplist的长度 int level; // 最高多少级链表 } zskiplist;

我们先来看下redis中zskiplist的定义，没啥内容，就头尾指针、长度和级数，重点还是在zskiplistNode中。
zskiplistNode中是有前向指针的，以是Level[0]实在是个双向链表。

typedef struct zskiplistNode { sds ele; // 节点存储的详细值 double score; // 节点对应的分值 struct zskiplistNode backward; // 前向指针 struct zskiplistLevel { struct zskiplistNode forward; // 每一层的后向指针 unsigned long span; // 到下一个节点的跨度 } level[];} zskiplistNode;

redis中的skiplist实现轻微和我们上文中讲的不大一样，它并不是大略的多级链表的形式，而是直接在zskiplistNode中的level[]将不同level的节点的关联关系组织起来，zskiplist的构造可视化如下。

知道了zskiplist的布局，我们来看下其几个紧张操作。

/ 创建跳表 /zskiplist zslCreate(void) { int j; zskiplist zsl; zsl = zmalloc(sizeof(zsl)); zsl->level = 1; zsl->length = 0; zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL); // 创建头节点 for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) { zsl->header->level[j].forward = NULL; zsl->header->level[j].span = 0; } zsl->header->backward = NULL; zsl->tail = NULL; return zsl;}

创建跳表就比较大略了，直接创建一个空的节点做为头节点。

/ 在跳表中插入一个新的节点, /zskiplistNode zslInsert(zskiplist zsl, double score, sds ele) { zskiplistNode update[ZSKIPLIST_MAXLEVEL], x; unsigned int rank[ZSKIPLIST_MAXLEVEL]; int i, level; serverAssert(!isnan(score)); x = zsl->header; for (i = zsl->level-1; i >= 0; i--) { / store rank that is crossed to reach the insert position / 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; } / skiplist中不会涌现重复的元素，但我们许可重复的分值，由于如果是调用zslInsert()的话，不会涌现重复插入两 个相同的元素，由于在zslInsert()中已经判断了hash表中是否存在/ level = zslRandomLevel(); // 天生一个随机值，确定最高须要插入到第几级链表里 if (level > zsl->level) { for (i = zsl->level; i < level; i++) { rank[i] = 0; update[i] = zsl->header; update[i]->level[i].span = zsl->length; } zsl->level = level; } 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; /插入新节点后须要更新前后节点对应的span值 / x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]); update[i]->level[i].span = (rank[0] - rank[i]) + 1; } / 为其他level增加span值，由于在原有俩节点之间插入了一个新节点 / for (i = level; i < zsl->level; i++) { update[i]->level[i].span++; } 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;}int zslRandomLevel(void) { int level = 1; while ((random()&0xFFFF) < (ZSKIPLIST_P 0xFFFF)) // ZSKIPLIST_P == 0.25 level += 1; return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;}

数据插入就轻微繁芜些，须要新建节点，然后确定须要在哪些level中插入新节点，还要更新前节点中各个level的span值。
这里额外把稳下zslRandomLevel，zslRandomLevel因此25%的概率决定是否将单个节点放置到下一层，而不是50%。

void zslDeleteNode(zskiplist zsl, zskiplistNode x, zskiplistNode update) { int i; for (i = 0; i < zsl->level; i++) { if (update[i]->level[i].forward == x) { update[i]->level[i].span += x->level[i].span - 1; //删除节点须要修正span的值 update[i]->level[i].forward = x->level[i].forward; } else { update[i]->level[i].span -= 1; } } if (x->level[0].forward) { x->level[0].forward->backward = x->backward; } else { zsl->tail = x->backward; } while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL) zsl->level--; zsl->length--;}/从skiplist中删除ele，如果删除成功返回1，否则返回0. 如果节点是null，须要调用zslFreeNode()开释掉该节点，否则只是把指向sds的指针置空，这样 后续其他的节点还可以连续利用这个sds/int zslDelete(zskiplist zsl, double score, sds ele, zskiplistNode node) { zskiplistNode update[ZSKIPLIST_MAXLEVEL], x; int i; x = zsl->header; for (i = zsl->level-1; i >= 0; i--) { 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))) { x = x->level[i].forward; } update[i] = x; } / 可能有多个节点有相同的socre，都必须找出来并删除 / x = x->level[0].forward; if (x && score == x->score && sdscmp(x->ele,ele) == 0) { zslDeleteNode(zsl, x, update); if (!node) zslFreeNode(x); else node = x; return 1; } return 0; / not found /}

数据的删除也很大略，很类似于单链表的删除，但同时须要更新各个level上的数据。

别的代码就比较多，知道了skiplist的详细实现，其他干系操作的代码也就比较随意马虎想到了，我这里就不在罗列了，有兴趣可以查阅下t_zset.c

Redis中的skiplist紧张是为了实现sorted set干系的功能，红黑树当然也能实现其功能，为什么redis作者当初在实现的时候用了skiplist而不是红黑树、b树之类的平衡树？ 而且显然红黑树比skiplist更节省内存啊！
Redis的作者antirez也曾经亲自回应过这个问题，原文见https://news.ycombinator.com/item?id=1171423

我大致翻译下：

本文是Redis源码阐发系列博文，同时也有与之对应的Redis中文注释版，有想深入学习Redis的同学，欢迎star和关注。
Redis中文表明版仓库：https://github.com/xindoo/RedisRedis源码阐发专栏：https://zxs.io/s/1h如果以为本文对你有用，欢迎一键三连。
本文来自https://blog.csdn.net/xindoo