《Redis设计与实现》读书笔记（四） ——Redis中的跳跃表

《Redis设计与实现》读书笔记（四） ——Redis中的跳跃表

（原创内容，转载请注明来源，谢谢）

一、概述

跳跃表（skiplist）是一种有序的数据结构，它通过每个节点中维持多个指向其他节点的指针，从而实现快速访问。跳跃表平均O(logN)，最坏O(N)，支持顺序遍历查找。

在redis中，有序集合（sortedset）的其中一种实现方式就是跳跃表。当有序集合的元素较多，或者集合中的元素是比较常的字符串，则会使用跳跃表来实现。另外，在redis集群节点中的内部数据结构，也是用跳跃表实现。

二、跳跃表实现

跳跃表是由各个跳跃表节点组成。

1、跳跃表数据结构

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

上图最左边就是跳跃表的结构。

其中，header和tail是跳跃表节点的头结点和尾节点，length是跳跃表的长度（即跳跃表节点的数量，不含头结点），level表示层数中最大节点的层数（不计算表头结点）。

因此，获取跳跃表的表头、表尾、最大层数、长度的时间复杂度都是O(1)。

2、跳跃表节点数据结构

typedef structzskiplistNode{
struct zskiplistLevel{
struct zskiplistNode *forward;
unsigned int span;
}level[];
struct zskiplistNode *backward;
double score;
robj *obj;
}zskiplistNode;

上图右边四列就是跳跃表节点的结构。

跳跃表节点包含下列四个概念：

1）层（level）。

zskiplistNode中的zskiplistLevel就表示层。上图L1、L2等，也就是层。L1是第一层，L2是第二层，以此类推。

每个层都有两个属性，前进指针（forward）和跨度（span）。前进指针用于访问表尾方向的节点，便于跳跃表正向遍历节点的时候，查找下一个节点位置；跨度记录前进指针所指的节点和当前节点的距离，用于计算排位，访问过程中，将沿途访问的所有层的跨度累计起来，得到的结果就是跳跃表的排位。上图中带数字的箭头就表示前进指针，箭头上面的数字就是跨度。当程序从表头向表尾遍历，会沿着前进指针进行。

层的意义：

层的作用是加快访问速度，这也是跳跃表的核心思想。每次创建跳跃表后，根据幂次定律，越大的数字出现的概率越小，随机生成一个1~32之间的值作为level数组的大小，这个就是层的高度。

越高层出现的概率越低，这也是实现跳跃表的中心思想。类似的概念如图所示：

每个节点的层都是随机的，但是每个节点高层的概率都是，越高层概率越低。通过这个高层，可以快速查找到score是某个值（或某个范围的值）的跳跃表节点。

查找方式是，先从最高层进行查找，由于其从小到大排序，因此只要在最高层中确定其在哪两个节点对应的范围之间。其次，再从次高层查找。以此类推，直到在第一层的从小到大遍历，可以确定节点在或不在此跳跃表中。

下图分别是带有1、3、5个层的跳跃表节点：

程序遍历节点的时候，会从头结点开始，沿着zskiplistLevel[i].span=1，从高层开始，逐个遍历下一个节点。直到发现zskiplistLevel[i].forward=null，表示已经完成全部的遍历。

2）后退指针（backward）。

zskiplistNode中的backward就表示后退指针。在上图的节点中用BW来表示，其指向当前节点的前一个节点，用于反向遍历时候使用。

不过后退指针每次只能往回退一个节点，不像前进指针可以一次跳过很多个节点。并且，后退指针不会指向头节点。

3）分值（score）。

zskiplistNode中的score就表示分值。各节点中的数字就是分值，跳跃表中，节点按照分值从小到大排列。

这个分值，即存储有序集合中的score。

4）成员对象（obj）。

zskiplistNode中的obj就表示成员对象的指针，其指向存储着节点的具体内容的redis的sds类型的字符串。

这个obj，即指向有序集合对应的具体值。因此，每个节点的成员对象唯一。

但是，每个节点的分值可以一样。分值一样时，会按照成员变量在字典中的大小顺序，小的靠近表头。

——written by linhxx 2017.08.30