Redis中跳表实现了性能优化（redis跳表优化）

Redis中的跳表是一种存储结构，它可以优化 Redis 的特定操作的性能，可用于存储有序的元素集合。事实上，Redis 中的跳表就是一个实现了元素排序的数据结构，它的实现基于一种叫做“跳表”的数据结构，该数据结构比标准的链表和数组数据结构更加灵活且快速，它能够根据关键字快速定位到元素，也能够快速获取有序列表中元素的范围，从而提高 Redis 的查找性能。

Redis 中的跳表是一个二叉树，包含一系列索引和“真实值”（元素值）的节点，每一个节点都有一个整数类型的索引和着一个指向“真实值”的指针。而“真实值”则是一个可以被外部存储的键值对，其中的 key 可以使用 O(1) 时间内获取到，value 则需要在 redis 中进行查找比较。

Redis 将每个跳表节点和“真实值”之间的关系建模为一种双向链表：每一个节点都指向一个“真实值”，而“真实值”又包含一个指向下一个节点的指针。这种链表构成了一种按顺序排列的数据结构，能够满足查找，范围查找，添加，删除等操作的需求。

下面是 Redis 跳表的部分源码，其中实现了 Redis 跳表的核心函数：

// 初始化跳表skiplist *skiplistCreate(void) {    struct skiplist *sl;    int j;    if ((sl = zmalloc(sizeof(*sl))) == NULL)        return NULL;    sl->level = 1;    sl->length = 0;    sl->header = skiplistNodeCreate(SKIPLIST_MAXLEVEL,0,NULL);    for (j = 0; j         sl->header->level[j].forward = NULL;        sl->header->level[j].span = 0;    }    sl->header->backward = NULL;    sl->tl = NULL;    return sl;}// 给定一个特定值，插入新节点int skiplistInsert(skiplist *sl, double score, sds ele) {    struct skiplistNode *update[SKIPLIST_MAXLEVEL], *x;    unsigned int level;    int i;    x = sl->header;    for (i = sl->level - 1; i >= 0; i--) {        while (x->level[i].forward &&             (x->level[i].forward->score             x = x->level[i].forward;        update[i] = x;    }    /* we assume the key is not already inside, since we allow duplicated     * scores, and the re-insertion of score and redis object should never     * happen since the caller of skiplistInsert() should test in the     * hash table first. */    level = skiplistRandomLevel();    if (level > sl->level) {        for (i = sl->level; i             update[i] = sl->header;            update[i]->level[i].span = sl->length;        }        sl->level = level;    }    x = skiplistNodeCreate(level,score,ele);    for (i = 0; i         x->level[i].forward = update[i]->level[i].forward;        update[i]->level[i].forward = x;        /* update span covered by update[i] as x is inserted here */        x->level[i].span = update[i]->level[i].span - (sl->length - update[i]->level[i].span);        update[i]->level[i].span = (sl->length - update[i]->level[i].span) + 1;    }    x->backward = (update[0] == sl->header) ? NULL : update[0];    if (x->level[0].forward)        x->level[0].forward->backward = x;    else        sl->tl = x;    sl->length++;    return 1;}

Redis 中的跳表支持 O(logn) 复杂度的查找，普通插入操作的复杂度也只需要 O(logn) ，在一定程度上可以帮助 Redis 提升性能。

香港服务器首选，2H2G首月10元开通。（）提供简单好用，价格厚道的香港/美国云服务器和独立服务器。IDC+ISP+ICP资质。ARIN和APNIC会员。成熟技术团队15年行业经验。