跳跃表

先来回顾常规的跳跃表。
！！！下面的图片和内容都来自于这个链接Redis数据结构——跳跃表 - 随心所于 - 博客园

对于一个有序的链表，我们如何才能快速定位一个元素呢？只能遍历，时间复杂度是O(N)，效率非常低。

既然链表是有序的，我们就可以建立索引，在上一层维护一个索引，也是链表的形式

当我们要查找元素8时，先通过索引定位到8在7和9之间，那么我们直接在7和9之间遍历可以找到。
当元素数量更多时，我们还可以继续向上抽取索引，查询效率明显提升。

这种通过为链表维护多级索引的结构，就是跳跃表
在链表上建立索引，虽然需要占用额外的空间来维护索引，但是对于元素数量非常多时，这些索引占用的空间就不那么重要了，是空间换时间的思想。

Redis中的跳跃表

跳跃表skiplist是一种有序的数据结构，通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
在大部分情况下，跳跃表的效率可以媲美平衡树（AVL树），并且跳跃表的实现比平衡树更简单。
跳跃表是有序集合底层的实现方式之一，如果一个有序集合中包含的元素数量比较多，或者有序集合中的元素是比较长的字符串时，Redis就会使用跳跃表来作为有序集合的实现方式

实现

简单点说，在Redis中，每个节点都包含若干层，每一层就是一级索引。

在Redis中，跳跃表是由zskiplistNode和zskiplist两个结构定义：

• zskiplistNode表示一个节点。
• zskiplist记录整个跳跃表的信息，例如头节点、尾节点、层级
  
  最左侧的蓝色结构就是zskiplist，该结构包含以下属性：
• header:指向跳跃表的头结点
• tail:指向跳跃表的尾节点
• level：记录目前跳跃表内，最大的层数，即顶级索引所在的层数
• length:跳跃表的长度，即跳跃表目前包含节点的数量（表头节点不计入）

zskiplistNode结构，包含以下属性：

• 层level:L1表示第一层，L2表示第二层，以此类推。每一层都有两个属性：前进指针和跨度
  • 前进指针用于访问位于表尾方向的其他节点
  • 跨度记录了前进指针所指向的节点与当前节点的距离。
• 后退指针bw：指向位于当前节点的前一个节点，后退指针在从尾向头遍历时使用
• 分值score:节点的分值，在跳跃表中，节点按各自所保存的分值从小到大排序
• 成员对象obj：各个节点中真实的数据对象

参考文章

• Redis数据结构——跳跃表 - 随心所于 - 博客园