【Redis数据结构·跳跃表】之异火排行榜

在面试中，Redis是面试官最喜欢问的话题，而跳跃表则是Redis中比较复杂的数据结构，读完本文相信掘友定有提升，还望支持一波~

跳跃表是什么

跳跃表(skiplist)一种有序数据结构。它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表与链表不同的地方在于：链表每个节点只有指向头、尾两个指针；而跳跃表每个节点可能有更多的指针，指集合键的节点便于快速的遍历。

从这里我们也可以看出跳跃表是一个空间换时间的一种模型。

它的时间复杂度为O(log N)、最坏O(N)。跳跃表和红黑树的时间复杂度不相上下，并且它的实现更加简单。

跳跃表的使用场景

Redis 只在两个地方用到了跳跃表,一个是实现有序集合健,另一个是在集群节点中用做内部数据结构,除此之外,跳跃表在 Redis 里没有其它用途;

Redis使用跳跃表作为有序集合键(Zset)的底层实现之一,如果一个有序集合包含的元素数量比较多。又或者有序集合中的元素的成员是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。

顺便提一嘴，Zset另外一种底层实现是压缩列表(ZipList)

常见使用于各种排行榜。例如某某游戏战力排行榜，他会统计所有玩家的战力，将Top100展示出来。那么就可以使用Zset完成。

Zset会接收两个参数：

1. score分值，主要用于排序时大小顺序的依据。
2. value值，具体要排序的名称

铛铛铛铛~，萧炎闪亮登场，下面给大家演示一下异火排行榜(部分)。 首先录入异火信息~

// 给Zset添加异火：生灵之焱，战力66666
127.0.0.1:6379> zadd YHRanking 66666 "生灵之焱"  

127.0.0.1:6379> zadd YHRanking 55555 "八荒破灭焱"  

127.0.0.1:6379> zadd YHRanking 88888 "净莲妖火"  

127.0.0.1:6379> zadd YHRanking 77777 "金帝焚天炎"  

127.0.0.1:6379> zadd YHRanking 200000 "帝炎"  

127.0.0.1:6379> zadd YHRanking 99999 "虚无吞炎"  

127.0.0.1:6379> zadd YHRanking 22222 "三千焱炎火" 

127.0.0.1:6379> zadd YHRanking 20000 "九幽风炎"  

127.0.0.1:6379> zadd YHRanking 44444 "九幽金祖火"  

127.0.0.1:6379> zadd YHRanking 33333 "红莲业火"  

127.0.0.1:6379> zadd YHRanking 19999 "骨灵冷火"
127.0.0.1:6379>

下面展示异火威力排名排序

默认情况下按照分值从小到大排序 （从0开始排序，zrank 升序，zrevrank降序）

127.0.0.1:6379> zrevrange YHRanking 0 -1
帝炎
虚无吞炎
净莲妖火
金帝焚天炎
生灵之焱
八荒破灭焱
九幽金祖火
红莲业火
三千焱炎火
九幽风炎
骨灵冷火

可以正着排，也可以反着排

127.0.0.1:6379> zrange YHRanking 0 -1
骨灵冷火
九幽风炎
三千焱炎火
红莲业火
九幽金祖火
八荒破灭焱
生灵之焱
金帝焚天炎
净莲妖火
虚无吞炎
帝炎

TOP5

127.0.0.1:6379> zrevrange YHRanking 0 4
帝炎
虚无吞炎
净莲妖火
金帝焚天炎
生灵之焱

可以查询骨灵冷火排名多少。

127.0.0.1:6379> zrevrank YHRanking 帝炎
0
127.0.0.1:6379> zrevrank YHRanking 九幽风炎
9
127.0.0.1:6379> zrevrank YHRanking 骨灵冷火
10

还有很多功能，就不一一展示啦。

跳跃表的原理

查询策略

由于Zset需要支持随机的删除与插入，所以不适合使用数据结构。下面来看下若是使用有序的链表会怎样实现？ 若是数组的查询可以使用二分查找法加快查找速度，而链表没有索引下标，查找值为9的元素则需要从头开始遍历 1,2,3,4,5,6,7,8,9 。 时间复杂度为O(n).

为了提高效率，可以在某些节点上加上多个指针，多加的指针指向跳过下一个节点之后的节点。

可能有掘友看不懂上图，我来说明一下，其中1,1这两个方块代表着同一个节点的两个指针，可以看到元素1的二层指针指向5的节点，元素1的一层指针指向2的节点。这样在查找9这个元素的时候，会从最高节点开始向后遍历，查到第一个比自己大的元素之前，然后来到下层，前往这层的后一个指针，知道再次查到第一个比自己大的元素之前，依然向下，直到到底最低层的指针，就能够找到查询的值。如图查找路径即为1,5,7,8,9。

定位插入点时，先在顶层进行定位，然后下潜到下一级定位，一直下潜到最底层，找到合适的位置，将新元素插进去。

数据结构

typedef struct zskiplistNode {  
//层  
struct zskiplistLevel {  
//前进指针  
struct zskiplistNode *forward;  
//跨度  
unsigned int span;  
}  
level[];  
//后退指针  
struct zskiplistNode *backward;  
//分值  
double score;  
//成员对象  
robj * obj;  
}  
zskiplistNode;

总结

跳跃表是有序集合的底层实现之一。

❑Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点。

❑每个跳跃表节点的层高都是1至32之间的随机数。

❑在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。

❑跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。

参考文献

1. 《Redis设计与实现》

2. 《Redis深度历练-核心原理与应用实践》