redis源码阅读之zskiplist

6210阅读　0评论2019-02-19　stolennnxb
分类：NOSQL

作为zset的底层实现之一（另一个是dict），今天来扯扯zskiplist（跳跃表）这个东西，至于zset是怎么利用这两个东西的，咱们之后再表，这次只是说说跳跃表的实现。
跳跃表是一种有序的数据结构，它通过在每个节点中存放多个指向其他节点的指针（正向的指针>=1个，反向的指针就一个）来达到快速访问节点的目的。在redis当中，其代码定义如下：

点击(此处)折叠或打开

  1. typedef struct zskiplistNode {
  2.     sds ele;
  3.     double score;
  4.     struct zskiplistNode *backward;
  5.     struct zskiplistLevel {
  6.         struct zskiplistNode *forward;
  7.         unsigned int span;
  8.     } level[];
  9. } zskiplistNode;

  11. typedef struct zskiplist {
  12.     struct zskiplistNode *header, *tail;
  13.     unsigned long length;
  14.     int level;
  15. } zskiplist;
  16. #define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
  17. #define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
先来说说zskiplistNode结构：
字段名称 含义
ele 当前节点存储的元素
score 当前节点存储的元素的得分
level[] 当前节点向前遍历时的指针数组，数组中的每个元素包含两个属性：1). 可以到达的节点指针forward；2). 该节点与当前节点的距离span，span用于计算forward节点在当前zskiplist当中的排名，而非用于遍历。
backward 当前节点向后遍历时的指针。注意这里不是数组，也就是说反向遍历只能从后往前一个一个来~~~


之后是zskiplist结构
字段名称    含义
header 指向跳跃表的头结点的指针
tail 指向跳跃表的尾节点的指针
length 跳跃表的长度，即当前跳跃表包含的节点数目（头结点不包含在内）
level 跳跃表中，level数组中元素最多的那个节点的level数组的元素个数（头结点不包含在内）

zskiplist结构当中需要多说一下的就是为什么length和level字段没有包括头结点？原因在于当创建一个zskiplist的时候，会直接把头结点设置成最大level，以便后续操作，其创建代码如下所示：

点击(此处)折叠或打开

  1. /* Create a new skiplist. */
  2. zskiplist *zslCreate(void) {
  3.     int j;
  4.     zskiplist *zsl;

  6.     zsl = zmalloc(sizeof(*zsl));
  7.     zsl->level = 1;
  8.     zsl->length = 0;
  9.     zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
  10.     for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
  11.         zsl->header->level[j].forward = NULL;
  12.         zsl->header->level[j].span = 0;
  13.     }
  14.     zsl->header->backward = NULL;
  15.     zsl->tail = NULL;
  16.     return zsl;
  17. }
至于对zskiplist的操作方面，个人觉得还是得推插入和删除了
由于zskiplist当中不允许存在相同的sds，这一保障性工作交由调用插入操作的调用者来保证~
插入的时候需要注意的就是它是以level从大到小的顺序来遍历并更新各个指针的，详情见代码：

点击(此处)折叠或打开

  1. /* Insert a new node in the skiplist. Assumes the element does not already
  2.  * exist (up to the caller to enforce that). The skiplist takes ownership
  3.  * of the passed SDS string 'ele'. */
  4. zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
  5.     zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
  6.     unsigned int rank[ZSKIPLIST_MAXLEVEL];
  7.     int i, level;

  9.     serverAssert(!isnan(score));
  10.     x = zsl->header;
  11.     // 确定每一个level当中由那一个节点来指向新插入的节点，并记录span
  12.     for (i = zsl->level-1; i >= 0; i--) {
  13.         /* store rank that is crossed to reach the insert position */
  14.         rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
  15.         while (x->level[i].forward &&
  16.                 (x->level[i].forward->score < score ||
  17.                     (x->level[i].forward->score == score &&
  18.                     sdscmp(x->level[i].forward->ele,ele) < 0)))
  19.         {
  20.             rank[i] += x->level[i].span;
  21.             x = x->level[i].forward;
  22.         }
  23.         update[i] = x;
  24.     }
  25.     /* we assume the element is not already inside, since we allow duplicated
  26.      * scores, reinserting the same element should never happen since the
  27.      * caller of zslInsert() should test in the hash table if the element is
  28.      * already inside or not. */
  29.     level = zslRandomLevel();
  30.     // 如果超出level，则更新span
  31.     if (level > zsl->level) {
  32.         for (i = zsl->level; i < level; i++) {
  33.             rank[i] = 0;
  34.             update[i] = zsl->header;
  35.             update[i]->level[i].span = zsl->length;
  36.         }
  37.         zsl->level = level;
  38.     }
  39.     // 创建并插入节点
  40.     x = zslCreateNode(level,score,ele);
  41.     for (i = 0; i < level; i++) {
  42.         x->level[i].forward = update[i]->level[i].forward;
  43.         update[i]->level[i].forward = x;

  45.         /* update span covered by update[i] as x is inserted here */
  46.         x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
  47.         update[i]->level[i].span = (rank[0] - rank[i]) + 1;
  48.     }

  50.     /* increment span for untouched levels */
  51.     for (i = level; i < zsl->level; i++) {
  52.         update[i]->level[i].span++;
  53.     }

  55.     x->backward = (update[0] == zsl->header) ? NULL : update[0];
  56.     if (x->level[0].forward)
  57.         x->level[0].forward->backward = x;
  58.     else
  59.         zsl->tail = x;
  60.     zsl->length++;
  61.     return x;
  62. }
zskiplistNode创建的时候会随机生成一个介于1和32之间的数来决定level数组的大小，这个数的生成遵循“越大的数出现的概率越小”这一原则，代码如下：

点击(此处)折叠或打开

  1. int zslRandomLevel(void) {
  2.     int level = 1;
  3.     while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
  4.         level += 1;
  5.     return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
  6. }

节点的删除工作就比较的中规中矩了

点击(此处)折叠或打开

  1. /* Internal function used by zslDelete, zslDeleteByScore and zslDeleteByRank */
  2. void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
  3.     int i;
  4.     for (i = 0; i < zsl->level; i++) {
  5.         if (update[i]->level[i].forward == x) {
  6.             update[i]->level[i].span += x->level[i].span - 1;
  7.             update[i]->level[i].forward = x->level[i].forward;
  8.         } else {
  9.             update[i]->level[i].span -= 1;
  10.         }
  11.     }
  12.     if (x->level[0].forward) {
  13.         x->level[0].forward->backward = x->backward;
  14.     } else {
  15.         zsl->tail = x->backward;
  16.     }
  17.     while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
  18.         zsl->level--;
  19.     zsl->length--;
  20. }
还望大家多提宝贵意见~~~
上一篇：redis源码阅读之intset
下一篇：redis源码阅读之hyperloglog