redis数据结构--跳表

跳表实质是链表，通过维护多个指向其他节点的指针，达到快速访问节点的目的。
跳表查找的时间复杂度平均情况下是O(logN)，最坏情况是O(N)。跳表作用类似于平衡树，实现上却比平衡树简单不少。
Redis中使用跳表作为有序集合键的底层实现之一。当有序集合元素较多时，或有序集合中元素为较长字符串时，都会使用跳表作为底层结构。
Redis在两个地方用到了跳表，一种是有序集合键中，另一种是集群节点中做内部数据结构。

跳表节点

typedef struct  zskiplistNode {
  struct zskiplistLevel {
    struct zskiplistNode *forward; // 前进指针
    unsigned int span; // 跨度 
  } level[]; // 层
  struct zskiplistNode *backward; // 后退指针
  double score; //分数
  robj *obj; // 成员对象
} zskiplistNode;

• 层 跳表节点的level数组包含指向其他节点的指针，一般来说，层数越多，跨度就越小，节点查找速度就越快。
• 前进节点 每层都有指向表尾方向的前进指针，用于按score升序访问节点。
• 跨度 层的跨度记录两个节点之间的距离，跨度可以用来找到节点并快速计算节点的rank。
• 后退指针 与前进指针不同，后退指针在节点维度是每个节点只有一个，所以后退操作每次只能进行一步。
• 分值和成员 分值用来将节点排序，节点成员底层实际上是一个SDS对象。

跳表

跳表数据结构定义如下:

typedef struct zskiplist {
  struct zskiplistNode *header, *tail; // 跳表头结点，尾结点
  unsigned long length; // 表中节点个数
  int level; // 表中最大层级数
} zskiplist;

可以看出跳表数据结构存放了跳表的元数据，用来快速访问头尾节点，计算元素总数，最大层高。