redis(4)跳跃表

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

2、跳跃表支持平均O(logN) 最坏o(N)复杂度的节点查找，还可以通过顺序操作来批量处理节点，大部分情况下效率媲美平衡树，实现比平衡树简单，所以不少程序员用跳跃表来代替平衡树

3、使用场景，有序集合包含元素数量比较多，或者成员member是比较长的字符串时。

4、跳跃表实现，包含zskiplistnode zskiplist

4.1、zskiplist

header:指向跳跃表的表头节点 tail:指向跳跃表的表尾节点，level:跳跃表内，层数最大的那个节点的层数（表头节点层数不计算在内） length:跳跃表长度，，，㔓包含的节点数量，表头不计在内

4.2、zskiplistnode

level：层 每个跳跃表节点层高都是1到32之间的随机数

每个层有两个属性，前进指针和跨度，前进指针用户访问位于表尾方向的其他节点，跨度则记录前进指针所指向节点和当前节点的距离 后退（backward）指针：bw字样标记节点后退指针，后退指针从表尾向头遍历时使用

分值，各个节点按照各自保存的分值从小到大排列

成员对象obj

得分相同，则按照字典顺序排序

5、仅通过多个跳跃表节点就能组成一个跳跃表，但是通过zskiplist结构来持有这些节点，程序可以更方便的对整个跳跃表进行处理

5.1、查找表头表尾复杂度为o(1) 计算长度length复杂度为o(1)

漫画跳跃表https://www.jianshu.com/p/ac351674d8eb?utm_campaign=maleskine&utm_content=note&utm_medium=seo_notes&utm_source=recommendation