跳跃表

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

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

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

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

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

  1. redis> ZRANGE fruit-price 0 2 WITHSCORES
  2. 1) "banana"
  3. 2) "5"
  4. 3) "cherry"
  5. 4) "6.5"
  6. 5) "apple"
  7. 6) "8"
  8.  
  9. redis> ZCARD fruit-price
  10. (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 节。