跳跃表

跳跃表(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 节。