跳跃表

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

跳跃表支持平均 O(\log N) 最坏 O(N) 复杂度的节点查找， 还可以通过顺序性操作来批量处理节点。

在大部分情况下， 跳跃表的效率可以和平衡树相媲美， 并且因为跳跃表的实现比平衡树要来得更为简单， 所以有不少程序都使用跳跃表来代替平衡树。

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

举个例子， fruit-price 是一个有序集合键， 这个有序集合以水果名为成员， 水果价钱为分值， 保存了 130 款水果的价钱：

redis> ZRANGE fruit-price 0 2 WITHSCORES
1) "banana"
2) "5"
3) "cherry"
4) "6.5"
5) "apple"
6) "8"

redis> ZCARD fruit-price
(integer) 130

fruit-price 有序集合的所有数据都保存在一个跳跃表里面， 其中每个跳跃表节点（node）都保存了一款水果的价钱信息， 所有水果按价钱的高低从低到高在跳跃表里面排序：

• 跳跃表的第一个元素的成员为 "banana" ， 它的分值为 5 ；

• 跳跃表的第二个元素的成员为 "cherry" ， 它的分值为 6.5 ；

• 跳跃表的第三个元素的成员为 "apple" ， 它的分值为 8 ；

诸如此类。

和链表、字典等数据结构被广泛地应用在 Redis 内部不同， Redis 只在两个地方用到了跳跃表， 一个是实现有序集合键， 另一个是在集群节点中用作内部数据结构， 除此之外， 跳跃表在 Redis 里面没有其他用途。

本章将对 Redis 中的跳跃表实现进行介绍， 并列出跳跃表的操作 API 。

本章不会对跳跃表的基本定义和基础算法进行介绍， 如果有需要的话， 可以参考 William Pugh 关于跳跃表的论文 《Skip Lists: A Probabilistic Alternative to Balanced Trees》 ， 或者 《算法：C 语言实现（第 1 ～ 4 部分）》 一书的 13.5 节。