Redis的数据结构分析

一、ZSkipList（跳表）

1. 概念

跳跃表结构在Redis中的运用场景只有一个，那就是作为有序列表 (Zset) 的使用。跳跃表的性能可以保证在查找，删除，添加等操作的时候在对数期望时间内完成，这个性能是可以和平衡树来相比较的，而且在实现方面比平衡树要优雅，这就是跳跃表的长处。跳跃表的缺点就是需要的存储空间比较大，属于利用空间来换取时间的数据结构。

2. 解释

对于于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)。比如查找12，需要7次查找，但是，如果我们增加如下两级索引，那么它搜索次数就变成了3次（注意，上图和实际上源码实现的跳表结构有点差异，只是方便理解而已）。

3. 实现

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Redis的跳跃表由zskiplistNode和skiplist两个结构定义，其中zskiplistNode结构用于表示跳跃表节点，而zskiplist结构则用于保存跳跃表节点的相关信息比如节点的数量，以及指向表头节点和表尾节点的指针等等。

3.1 skiplist

1. header：指向跳跃表的表头节点，通过这个指针程序定位表头节点的时间复杂度就为O(1)。
2. tail：指向跳跃表的表尾节点，通过这个指针程序定位表尾节点的时间复杂度就为O(1)。
3. level：记录目前跳跃表内。层数最大的那个节点的层数（表头节点的层数不计算在内），通过这个属性可以再O(1)的时间复杂度内获取层高最好的节点的层数。
4. length：记录跳跃表的长度，即跳跃表目前包含节点的数量（表头节点不计算在内），通过这个属性，程序可以再O(1)的时间复杂度内返回跳跃表的长度。

3.2 zskiplistNode

1. 层（源码中的level数组）：节点中用L1、L2、L3等字样标记节点的各个层，L1代表第一层，L代表第二层，以此类推。 每个层都带有两个属性：① 前进指针：用于访问位于表尾方向的其他节点。② 跨度：用于记录了前进指针所指向节点和当前节点的距离（跨度越远、距离越大）。在上图中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。每次创建一个新跳跃表节点的时候，程序都根据幂次定律（powerlaw，越大的数出现的概率越小）随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”。
2. 后退（源码中的backward）指针：节点中用BW字样标记节点的后退指针，它指向位于当前节点的前一个节点，后退指针在程序从表尾向表头遍历时使用，与前进指针所不同的是每个节点只有一个后退指针，因此每次只能后退一个节点。
3. 分值（源码中的score）：各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。
4. 成员对象（源码中的ele）：各个节点中的o1、o2和o3是节点所保存的成员对象。在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的，分值相同的节点将按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面（靠近表头的方向），而成员对象较大的节点则会排在后面（靠近表尾的方向）。