跳跃表通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的.
跳跃表支持平均O(logN),最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点
在大部分情况下,跳跃表的效率可以和平衡树相媲美,并且因为跳跃表的实现比平衡术要来的更为简单,所以有不少程序都使用跳跃表来代替平衡树
Redis使用跳跃表作为有序集合键的底层实现之一,吐过一个有序集合包含的元素数量比较多,又或者有序集合中元素成员是比较长的字符串时,Redis就会使用跳跃表来作为有序集合键的底层实现
1 | redis> ZRANGE fruit-price 0 2 WITHSCORES |
fruit-price有序集合的所有数据都保存在一个跳跃表里面,其中每个跳跃表节点都保存了一款水果的价钱信息,所有水果按价钱的高低从低到高在跳跃表里面排序
和链表,字典等数据结构被广泛地应用在Redis内部不同,Redis只在两个地方用到了跳跃表,一个是实现有序集合键,另一个是在集群节点中用作内部数据结构,除此之外,跳跃表在Redis里面没有其他用途
重点回顾
- 跳跃表是有序集合的底层实现稚艺
- Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成,其中zskiplist用于保存跳跃表信息,而zskiplistNode则用于表示跳跃表节点
- 每个跳跃表节点的层高都是1至32之间的随机数
- 在同一个跳跃表中,多个节点可以包含相同的分支,但每个节点的对象必须是唯一的
- 跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象的大小进行排序