wenfengsun

Redis的sorted set用于高频率的变换排序十分方便，例如论坛，贴吧，微博等。

Redis是用C语言实现的，sorted set的实现方式是通过ZSET。

ZSET的实现用到了两个数据结构：hash table 和 skip list(跳跃表)，其中hash table是具体使用redis中的dict来实现的，主要是为了保证查询效率为O(1) ，而skip list(跳跃表)主要是保证元素有序并能够保证INSERT和REMOVE操作是O(logn)的复杂度。

关于skip list这里简单介绍下：skip list是链表的一种特殊形式，对链表的一种优化；保证INSERT和REMOVE操作是O(logn)的负载读，而通用链表的复杂度为O(n);

下面是关于skip list的介绍：

这是一个链表。上面链表是有序排列的，那么如果想查找某一个元素x，则可以如下操作

1. node *p = head;
2. while(p->next <x) p=p->next;
3. return p->next;

如此以来，得到了p之前的元素均小于x，而p之后的元素均不小于x，p是不小于x的第一个元素节点指针.
如果要按照顺序插入一个元素x，则可以如下操作。

1. node *p = find(x);
2. p1->next=p->next;
3. p->next = p1;

删除操作，删除不小于x的第一个元素

1. node *p = find(x);
2. node *p1 = new node;
3. p1 = p;
4. p = p->next;
5. delete p1;
6. p1 = NULL;

以上是顺序链表，而skip list能够在这三个操作上节省时间。将时间由原来的O(n)节省到O(log(n))。

1. node *p = top;
2. while(1)
3. {
4. while(p->next->key<x) p = p->next;
5. if(p->down == NULL) return p;
6. p=p->down;
7. }

1.如何构建一个skip list?

按照顺序排列的链表作为底层；

将链表中随机抽取一些元素，作为第二层，而第二层的每一个元素均有向下的一个指针，指向第一层中与其相同的元素；

而后再在第二层元素中，随机选取一部分元素，作为第三层，而第三层中的元素也均有向下的指针指向第二层与其相同的元素；以此类推，

直到构建了一层只有最大值最小值(-1,1)指针的元素。如此构建一个skip list。

skip list有以下特征：

最下面得一层具有所有元素；

上面每一层的元素均是来自其下面一层的元素；

每层元素均有向下的指针与其下一层相同的元素相关联；

有一个top指针指向最高一层的第一个元素。

在skip list中，要实现查找、插入、删除等操作时，只需要操作O(log(n))次。

插入元素，假设要在第k层插入元素x，k的值不同也会有不同：