SKIPLIST

skipList是一种有序的数据结构

• 平均复杂度logN，最坏复杂度N
• 大部分情况下跳跃表的性能可以和平衡树媲美，并且因为实现简单，所以大部分会选择Skip

适用场景：有序集合中包含的数据量比较多，或者元素的乘以是比较长的字符串时。比如ZSET

redis的实现skiplist需要的2种结构 redis.h文件中哄的zskiplistNode和zskiplist

• zskiplist包含：header（指向跳跃表的表头节点），tail （指向跳跃表的表尾节点），level（记录目前跳跃表内层数最大的那个节点的层数，表头的节点不包含在内），length（记录跳跃表的长度，也就是目前包含节点的数量，表头节点不计算在内）

• 我们可以看到 我红色标记的就是一个具体的节点，节点里面就是一个节点包含的属性

  
  image.png

• zskiplistNode包含下列元素

• level：节点用L1之内的字样标记节点的各个层，L1代表第一层，每一层有2个属性，前进指针和跨度。

• 前进 指针用于访问表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离

• 后退指针（BW）：节点中用BW字样标记的后退指针，它指向当前节点的前一个节点，后退指针用来当程序从尾向头遍历时使用。

• 分值（SCROE）：在跳跃表中，节点按照各自所保存的分值从小到大排列

• 成员对象 obj，各个节点中的 o1之类保存的成员对象

• 表头节点也有上述属性

• obj 是一个指针，它指向一个字符串对象，而字符串对象则保存一个SDS值。

  
  image.png

• 整个跳跃表的过程如下：

  
  image.png

• 跨度指向Null 则其跨度为0