redis源码阅读之zskiplist

3400阅读 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;

  10. typedef struct zskiplist {
  11.     struct zskiplistNode *header, *tail;
  12.     unsigned long length;
  13.     int level;
  14. } zskiplist;
  15. #define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
  16. #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;

  5.     zsl = zmalloc(sizeof(*zsl));
  6.     zsl->level = 1;
  7.     zsl->length = 0;
  8.     zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
  9.     for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
  10.         zsl->header->level[j].forward = NULL;
  11.         zsl->header->level[j].span = 0;
  12.     }
  13.     zsl->header->backward = NULL;
  14.     zsl->tail = NULL;
  15.     return zsl;
  16. }
至于对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;

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

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

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

  51.     x->backward = (update[0] == zsl->header) ? NULL : update[0];
  52.     if (x->level[0].forward)
  53.         x->level[0].forward->backward = x;
  54.     else
  55.         zsl->tail = x;
  56.     zsl->length++;
  57.     return x;
  58. }
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