Redis中利用跳跃列表实现超高效率排序（redis 跳跃列表）

Redis是一款流行的开源key-value存储数据库。与其他关系型数据库不同，Redis支持很多特殊的数据类型，比如：字符串(String)、哈希(Hash)、列表(List)、集合(Set)、有序集合(Sorted Set)等等。

在数据结构中，跳跃列表(Skip List）是一棵多叉树结构，每一个节点定义了一个跳跃目标，比较特殊的是跳跃列表没有左右孩子的概念，它的实现的依据是节点中每一层的伪随机有序，且和任何一层都相互独立。由于此种特殊的结构，查询通常情况下可以比较快的完成，特别是在数据量特别大的时候表现的更好。

Redis利用跳跃列表实现超高效率排序，这种方式可以很好的解决在面对有序性查询时面临的各种挑战，如存储量大、排序时间短暂等，同时也很好的避免了之前采用的排序算法，算法消耗大量时间及内存资源。

Redis中 使用 跳跃列表 实现 超高效率 排序，这就是 Redis ZINCRBY 函数和 ZRANGEBYSCORE 函数的实现原理，它们可以在很短的时间内获取有序集合中结果，在一些重要的场景中尤为有效，比如排行榜的查询，往往是按照分数从小到大来查出前几位的结果，使用 Redis 跳跃列表可以实现更高的查询性能。

实现跳跃列表，Redis 所使用的算法为 red-black tree，具体实现如下：

（1）建立 skip list 结构；
// 创建 skip list 
struct sl{
 slnode *head;
 slnode *tl;
 // …… 
};
（2）将要插入的结点作为一个新的结点，插入到 skip list 的 最后；
// 尾插入
slnode *sl_add(struct sl *self, int data){
 slnode *node = (slnode*)malloc (sizeof(slnode)); 
 node->data = data;
 node->next = self->head;
 self->head->pre->next = node;
 node->pre = self->head->pre;  
 self->head-> pre = node;

 return node;
}
（3）大循环，查询在某一层中，插入位置的前驱结点，如果不存在前驱结点，则继续往更低一层查找；
（4）反复循环，直到查询不到前驱结点，将插入结点直接插入跳跃列表中；
（5）在插入操作后，可以按照空间/时间权衡，准确的估算出把新结点放入多少个伪随机有序的层，以减少查找时间；
>>>>
struct slnode *sl_insert(struct sl* self, int data){ 
 struct slnode *ins_node; 
 int level = 0;
 // 插入结点 
 ins_node = sl_add(self, data);
 // 估算插入健的随机级 
 while(rand() > 0.25 && level 
  level++;
 }
 // 级联 
 sl_cascading(self, ins_node, level);
    return ins_node; 

以上是 Redis 利用跳跃列表实现超高效率排序的原理介绍，从性能上来看，它的优势非常明显，在大数据量的场景下，按需查询的性能和稳定性能都有一个很大的提升。