redis之跳跃表的实现

跳跃表 跳跃表（skiplist） 是一种有序数据结构， 它通过在每个节点中维持多个指向其他节点的指针， 从而达到快速访问节点的目的。 跳跃表支持平均O（logN） 、 最坏O（N） 复杂度的节点查找， 还可以通过顺序性操作来批量处理节点。 在大部分情况下， 跳跃表的效率可以和平衡树相媲美， 并且因为跳跃表的实现比平衡树要来得更为简单， 所以有不少程序都使用跳跃表来代替平衡树。 Redis使用跳跃表作为有序集合键的底层实现之一， 如果一个有序集合包含的元素数量比较多(默认情况是大于128个使用跳表)， 又或者有序集合中元素的成员（member） 是比较长的字符串时， Redis就会使用跳跃表来作为有序集合键的底层实现。 在redis的实现中,在有序集合键和集群节点中使用跳表 跳表结构 zskiplist结构用来保存跳跃表节点的相关信息。 typedef struct zskiplist { struct zskiplistNode *header, *tail; // 头尾节点指针 unsigned long length; // 跳跃表的长度 int level; // 目前跳跃表内,层数最大的节点的层数(不包括头结点) } zskiplist; 跳跃表 跳跃表（skiplist） 是一种有序数据结构， 它通过在每个节点中维持多个指向其他节点的