简述

上一期我们讲了RedisObject类，其中type代表数据类型，encoding代表ptr所指向底层实现的数据结构。今天我看来学习encoding之一，Redis数据结构-跳表。
跳表是一种有序的数据结构，它通过每个节点中维持多个指向其他节点的指针，达到快速访问节点的目的。

跳表

首先，我们先看看跳表是怎样设计的。

链表

如图所示，这是个排序的链表，其实ptr指的是指向下一个节点的指针。这时候我们想查询节点9，则需要从节点1开始遍历，查询效率会很低，时间复杂度为O（n）。

优化

如果我们想提高查询效率，有什么办法呢？比方说我们要获得节点9的地址，如果不遍历就好了，这么一想，我们其实可以在链表上建立一个索引，索引从节点1的指针直接指向节点9，这样查询效率大大提高。所以我们可以获得如图所示的数据结构：

图中可以看出，如果我们这时候查询节点9，我们直接通过创建的索引，1->3->5->7->9，只需要遍历5个节点就能获取到节点9，原先则需要遍历9个节点。从此图我们可得出，如果我们每添加一层索引，则查询效率就会提升，当然，占用空间也就更多，典型的空间换时间，对于Redis这种高性能NoSQL数据库来说，也是值得的。

我们再加多一层，则这次查节点9只要1->5->9，遍历3个节点即可获得节点9。

我们再加多一层，这次差节点9只要1->9，遍历两个节点即可获得节点9，查询效率提升巨大。刚刚忘记说了，第一层索引是L0，第二层索引是L1，第三层索引是L3，以此类推。链表上添加多级索引的数据结构物，我们称之为跳表。

Redis跳表

Redis跳表是由zskiplistNode和skiplist两个类定义的，其中zskiplistNode是用于表示跳表的节点，而zskiplist则用在保存跳跃表节点的信息。

zskiplist

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

• header
  指向跳表的头结点。通过此指针可以获得表的头结点。
• tail
  指向跳表的尾节点。通过此指针可以获得表的尾节点。
• length
  记录跳表的长度。
• level
  记录目前跳表层数最大的那个节点的层数。通过此变量可以获得跳表的最高层索引的层数。

zskiplistNode

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

• ele
  成员对象。具体对象信息保存在此成员变量中。在同一个跳表中，每个节点保存的成员对象是唯一的，多个节点保存的分值可以是相同的。如果分值相同，则会按照成员对象在字典序中的大小进行排序，成员对象较小的节点会排在前面，成员对象较大的节点会排在后面。
• score
  分值。redis的skiplist通过分值从小到大排序来排序节点。
• backward
  后退指针。它指向的是当前节点的前一个节点地址。后退指针在从表尾到表头遍历使用，每个节点只有一个后退指针，每次只能后退一个节点。
• zskiplistLevel
  代表每层索引的信息。由代码可以看出，它的结构是个数组，保存的是每层节点索引的信息。节点每层索引信息都带有两个成员变量，一个是forward指针，代表的是前进指针，指向下一个节点位置。另外一个是span，代表前进指针所指向的节点和当前节点的距离。
  这里我再解释清楚下，nodeXX->level[0]代表的是节点XX原链表的信息，nodeXX->level[1]代表的是节点XX一级索引信息。所以一个zskiplistNode代表一个节点，zskiplistLevel是节点共有的层数（包括原链表）。如下图所示：

总结

今天我介绍了跳表，也介绍了Redis中跳表数据结构。Redis跳表中最重要两个对象，一个zskiplist，另外一个是zskiplistNode，我也做了详细介绍。总的来说，跳表是一个空间换时间的数据结构，可以使得查询效率大大提升。