redis数据结构-跳跃表

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

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

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

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

面试常问：

1、redis 排序集合使用什么实现？

跳跃表

2、跳跃表的时间复杂度？

o(lgn),最差o（n）

3、跳跃表的插入、删除、查找的过程？

参考：https://www.jianshu.com/p/61f8cad04177

redis数据结构-跳跃表

原文：https://www.cnblogs.com/albert32/p/13384948.html