跳跃表

# 跳跃表 跳跃表（skiplist）是一种有序数据结构， 它通过在每个节点中维持多个指向其他节点的指针， 从而达到快速访问节点的目的。 跳跃表支持平均  最坏  复杂度的节点查找， 还可以通过顺序性操作来批量处理节点。 在大部分情况下， 跳跃表的效率可以和平衡树相媲美， 并且因为跳跃表的实现比平衡树要来得更为简单， 所以有不少程序都使用跳跃表来代替平衡树。 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](ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf)》 ， 或者 《[算法：C 语言实现（第 1 ～ 4 部分）](http://book.douban.com/subject/4065258/)》 一书的 13.5 节。