Redis中之跳跃表插入实现算法（redis 跳跃表插入）

Redis是一款性能非常优秀的开源键值数据库，它支持丰富的特性，其中的跳跃表是比较重要的一种数据结构，用于支持范围查询，它能更高效的处理查询操作。那么Redis中跳跃表插入实现算法是怎样的呢？

Redis中跳跃表插入实现算法如下：申请一个新的节点，并且设置其对应的键和值；根据新节点的键和已有节点的键，从后向前找直到某个节点的键下界大于新节点，记住此节点；再次，新节点的前驱后驱成为该节点；从新节点到其前驱，更新链表中节点级数和每层节点的后驱指针；跳跃表插入成功。

Redis中跳跃表插入实现算法的C语言实现如下：

/* step1: Create the new node. */
zskiplistNode* zslCreateNode(int level, double score, robj* obj) {
  zskiplistNode *zn = zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
  zn->score = score;
  zn->obj = obj;
  return zn;
}
/* step2: Find a position to locate the new node. */
zskiplistNode* zslFindBestNode(zskiplist *zsl, double score, zskiplistNode **update) {
/* Invariant: update[i]->level[i].forward is the pointer min score is larger than score, */
/* and update[i]->level[i].span is the span of score. */
  zskiplistNode *t = zsl->header;
  int i;
  for(i = zsl->level - 1; i >= 0; i--) {
    while (t->level[i].forward 
      && (t->level[i].forward->score 
      t = t->level[i].forward;
    }
    update[i] = t;
  }
  return t;
}

/* step3: Insert the new node to the list. */
zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {
  zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
  int i;
  x = zslFindBestNode(zsl, score, update);
  /* Update all the spans of nodes, which are under the new one. */
  if(x->score == score) {
    x->obj  = obj;
    return x;
  } 
  x = zslCreateNode(rb_randomlevel(zsl), score, obj);
  for(i = 0; i level; i++) {
    x->level[i].forward = update[i]->level[i].forward;
    update[i]->level[i].forward = x;
    
    /* Update span of the following nodes when needed. */
    if(node_level_span) 
      x->level[i].span = update[i]->level[i].span -
                       (update[i]->level[i].span - 
                        update[i]->level[i].span + 1);
  }
  /* Level is invalid because it depends on span */
  /* update[i]->level = x->level; */
  return x;
}

跳跃表在Redis中尤为重要，为范围查询提供了更高效的支持，其中插入操作的实现算法步骤分为：申请新节点，找出新节点位置，更新链表，更新链表中节点级数与每层节点的指针；跳跃表插入成功。使用Redis中跳跃表插入实现算法的C语言实现，其步骤基本一致。Redis中的跳跃表插入实现算法，是由三个步骤组成的，从申请新节点，找出新节点位置，到更新链表，最终算法实现完毕。