Redis的集合底层实现精妙机制运行效率高（redis的集合底层实现）

Redis的集合底层实现：精妙机制运行效率高

Redis是一款高性能的NoSQL数据库，集合是其中重要的数据结构之一。它的底层实现非常精妙，基于跳表和字典实现的结构，让集合操作的运行效率非常高。

集合的底层数据结构

Redis的集合底层数据结构是由两个结构体组成的：

“`c

typedef struct {

//表示集合的字典

dict *dict;

} dictSet;

typedef struct {

//表示集合的跳表

zskiplist *zsl;

} zset;

其中，dictSet结构体利用了字典结构dict，在代码中实现如下：

```c
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    unsigned long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

另外一个zset结构体则利用了跳表结构zskiplist，在代码中实现如下：

“`c

typedef struct zskiplist {

struct zskiplistNode *header, *tl;

unsigned long length;

int level;

} zskiplist;

typedef struct zskiplistNode {

robj *obj;

double score;

struct zskiplistNode *backward;

struct zskiplistLevel {

struct zskiplistNode *forward;

unsigned int span;

} level[];

} zskiplistNode;

从这两个结构体可以看出，在Redis中，集合被实现了两种不同的方式，一种是字典结构，另一种是跳表结构。其中字典结构的实现比较简单，直接利用了dict结构，而跳表结构则比较复杂，利用了zskiplistNode结构以及一些操作跳表的函数。

集合的操作

Redis的集合提供了大量的操作方法，如添加元素、删除元素、判断元素是否存在、求并集、求交集、求差集等。下面以添加元素为例，看看Redis是如何实现集合的操作的。

以添加元素为例，Redis提供了两种不同的方法，一种是使用字典结构实现，一种是使用跳表结构实现。这两种方法的实现代码如下：

使用字典：

```c
int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL);
    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

使用跳表：

“`c

zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {

zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;

unsigned int rank[ZSKIPLIST_MAXLEVEL];

int i, level;

assert(!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

(x->level[i].forward->score == score &&

compareStringObjects(x->level[i].forward->obj,obj)

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, and the re-insertion of score and redisObject is rare enough

* to just handle it with O(N) brute force search. */

level = zslRandomLevel();

if (level > zsl->level) {

for (i = zsl->level; i

rank[i] = 0;

update[i] = zsl->header;

update[i]->level[i].span = zsl->length;

}

zsl->level = level;

}

x = zslCreateNode(level,score,obj);

for (i = 0; i

x->level[i].forward = update[i]->level[i].forward;

update[i]->level[i].forward = x;

x->level[i].span = update[i]->level[i].span – (rank[0] – rank[i]);

update[i]->level[i].span = (rank[0] – rank[i]) + 1;

}

for (i = level; i 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->tl = x;

zsl->length++;

return x;

}

通过分析代码可以发现，虽然Redis使用了两种不同的数据结构来实现集合，但是在具体操作这些数据结构上，两者的代码是非常相似的。

集合的优点

利用跳表和字典结构实现的集合，有以下几个优点：

1.查找速度快：跳表是一种高级数据结构，能够在运行时达到O(log n)的平均速度，因此Redis内部使用跳表的方式能够大大提高集合操作的效率。

2.插入和删除速度快：跳表是链表的变种，因此它具有链表的插入和删除速度快的优点，具有O(1)的插入和删除时间复杂度。

3.支持有序集合：集合的有序集合可以在哪些元素之间引入一个排序关系，从而提供了一些额外的功能，例如范围查找操作。

结语

Redis内部使用跳表和字典结构来实现集合，可以提供非常高效的操作速度，而且也保证了集合的数据完整性和安全性。对于Redis的使用者来说，了解Redis集合的底层实现对于合理利用Redis更加高效，可以让Redis发挥出更大的作用。