Redis 内部数据结构详解

redis zskiplist

2019-08-15  本文已影响0人  多多的大白

skiplist 是一种有序数据结构。它通过在每个节点中维持多个指向其他节点的指针， 从而达到快速访问节点的目的。 跳跃表支持平均O(log N) 最坏 O(N)
复杂度的节点查找。

1、跳表介绍

为了使得链表支持类似二分查找的算法，对原始的链表进行修改，修改后的链表就是跳跃表，简称跳表。跳表支持快速的插入、删除、查找操作，是一种动态的数据结构。

1-1

如果我们想查找图1-1 的链表里面的某个元素，那必须从头遍历到尾才能找到，时间复杂度为O(n)

1-2

我们可以给原始链表加一级索引，如上图1-2，从图中可以看出如果我们此时查找是6这个元素的，从红线表示看我们只需要查找5次，原始链表查询需要6次

1-3

我们可以给原始链表再增加一级索引，来减少我们的查找时间复杂度。

由于这个数据量不大，查找效率提升的不明显，对于数据量较大的时候，查找效率提高很快，拿空间换时间。
JAVA中也有跳表的实现-ConcurrentSkipListMap。

2、redis skiplist 结构

在redis中 对外暴露的数据结构：sorted set，然后sorted set 底端不仅仅使用skiplist，还是使用ziplist和dict （关于ziplist 后面章节会介绍），那么具体什么情况下面才会使用skiplist

# Similarly to hashes and lists, sorted sets are also specially encoded in
# order to save a lot of space. This encoding is only used when the length and
# elements of a sorted set are below the following limits:
  zset-max-ziplist-entries 128
  zset-max-ziplist-value 64

通过redis.conf 上面这俩个配置来具体确定 ziplist 到skiplist的转换

1-1 
#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;
typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

上面代码出自redis-4.0 的 server.h ，对上面结构做些简单分析

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

3、redis skiplist 创建过程以及skiplist的转换

创建过程

为什么把创建过程单独拿出来作为一项，因为笔者在刚刚开始的时候对跳表完全不了解，看了很多资料也还是一知半解。特别当笔者第一次看到图1-1（别人画的借用下）完全不理解header指向为什么是一个null的node 而且还是长度为32的level[]，所以这里面做下特殊的源码讲解。

/* Create a skiplist node with the specified number of levels.
 * The SDS string 'ele' is referenced by the node after the call. */
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
    zskiplistNode *zn =
        zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    zn->score = score;
    zn->ele = ele;
    return zn;
}
/* Create a new skiplist. */
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;
    zsl = zmalloc(sizeof(*zsl));
    zsl->level = 1;
    zsl->length = 0;
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    zsl->header->backward = NULL;
    zsl->tail = NULL;
    return zsl;
}

上述代码出自redis-4.0 的 t_zset.c ，简单做下分析

下面分析插入节点操作：

/* Insert a new node in the skiplist. Assumes the element does not already
 * exist (up to the caller to enforce that). The skiplist takes ownership
 * of the passed SDS string 'ele'. */
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;
    serverAssert(!isnan(score));
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        /* store rank that is crossed to reach the insert position */
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        while (x->level[i].forward &&
                (x->level[i].forward->score < score ||
                    (x->level[i].forward->score == score &&
                    sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    /* we assume the element is not already inside, since we allow duplicated
     * scores, reinserting the same element should never happen since the
     * caller of zslInsert() should test in the hash table if the element is
     * already inside or not. */
    level = zslRandomLevel();
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }
    x = zslCreateNode(level,score,ele);
    for (i = 0; i < level; 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 - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }
    /* increment span for untouched levels */
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;
    zsl->length++;
    return x;
}

代码很长，总体思路大概分为3步：

skiplist的转换

前面介绍sorted set并不是一开始就用skiplist 而是后面才开始转换成的。通过上面介绍的zset-max-ziplist-entries 和zset-max-ziplist-value来控制的。

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

4、为什么redis用skiplist而不用平衡树

关于这个话我们可以从查找、新增删除的角度考虑

平衡树:采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度。

从上面三点其实已经说明很多选择skiplist的优势，还有一点skiplist 实现起来比平衡树简单很多。

Redis作者：(原话地址）

There are a few reasons:

  1. They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
  2. A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
  3. They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

5、总结

上一篇下一篇

猜你喜欢

热点阅读