Redis 跳表的源码剖析与实现（redis 跳表 源码）

Redis是一个开源的、基于内存的ykey-value存储系统，由于它快速、高效、可扩展性高，所以被众多开发人员普遍使用，尤其是移动和互联网应用。本文主要围绕Redis跳表这一基础数据结构展开，深入探讨Redis跳表的源码剖析与实现，帮助读者更好的了解Redis。

Redis跳表（Skip List）是一种空间时间权衡的有序数据结构，是以数据关键字的升序进行排序的，他拥有比red-black树更好的查询效率、拥有比hash更高的空间效率。算法插入、删除和搜索复杂度都是O(log n)，此外，Redis跳表实现起来也非常简单灵活。

Redis跳表的实现原理是，他建立了一个N个层级的有序链表，每一层的表项之间的关联性取决于上一层的表项，同时每一层的表项也可以存储任意的值，当插入表项的时候，会首先在第一层生成一个新的表项，然后逐级往上提升，每一级的提升概率都是50％，当超过指定的层级时停止提升，这样就保证了随机性。

此外，还有不少Redis跳表源码是值得一提的，比如在插入（insert）操作中，可以使用随机值来实现一致性，不使用分布式锁，从而提高效率。同时，还可以使用指针压缩法来存储每级链表的地址，以达到更节省内存的效果。

// Redis跳表插入示例
int skiplistInsert(skiplist *sl, int key)
{
    skiplistNode *update[maxlevel];
    skiplistNode *x;
    x = sl->head;
    int i;
    for(i = sl->level - 1; i >= 0; i--) { 
        while(x->forward[i] != NULL && (x->forward[i]->key 
            x = x->forward[i];
        }
        update[i] = x; //记录搜索路径
    }
    x = x->forward[0];

    // 插入新节点
    int level = randomLevel();
    if (level > sl->level) {
        for (int i = sl->level; i 
            update[i] = sl->head;
        }
        sl->level = level;
    }
    x = new skiplistNode(level);
    x->key = key;
    for (i= 0; i
        x->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = x;
    }
    return 1;
}

从上面的源码可以看出，插入节点时，会从头指针（head）开始在每一级搜索出插入位置的前驱结点，再随机生成一个插入节点的层数，最后将其插入每一级链表。

Redis跳表源码剖析与实现就是这样，通过不断搜索，每一层的表项之间也可以互联紧密关联，同时由于随机性原因，维护这些关系也是非常有效的。