zset 数据结构

标题首先明确一下几点基本常识：

• Redis常见的5种数据类型：String(字符串)、List(列表)、Hash(哈希)、Set(集合)、ZSet(有序集合)，这五种常见的数据类型，本质上对应着五种对象，即字符串对象、列表对象、哈希对象、集合对象、有序集合对象。
• 在Redis中，任意一个对象都具有五种属性

[1] type ====> 类型对应基本数据类型。例如Redis_String 对应字符串，Redis_List对应列表

[2] encoding ====> 编码。编码方式决定了对象的底层的数据结构，一个对象至少有两种编码方式

[3] prt ====> 指针。指向由编码决定的数据结构，数据结构中往往包含有所存的数据

[4] refcount ====> 引用计数。这个属性主要是为了实现redis中的内存回收机制

[5] lru ====> 最近最少使用。用来解决对象的空转时长，同时也会被用于当缓冲达到最大值，再向其中添加数据时，应该删除什么数据。

有序结合(ZSet)对象详解

上述说过，一个对象的底层的数据结构是由对象的编码方式决定的，而ZSet的编码方式有两种

• ziplist
• skiplist

本文将介绍Redis中有序结合(zset)的底层结构跳跃表及其结构定义。

ZipList

使用压缩连表时，要保证集合中的数据有序，会将key放在前面一位，然后将key所对应value放在key的后一位。这样就能够保证集合的有序。

当有序集合对象同时满足以下两个条件时，对象使用压缩链表编码：

1. 有序集合保存的元素数量小于128个；
2. 有序集合保存的所有元素成员的长度都小于64字节；

概述

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。

跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。 在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单,所以有不少程序都使用跳跃表来代替平衡树。

Redis使用跳跃表作为有序集合(zset)键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。

Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构，除此之外，跳跃表在Redis里面没有其他用途。

跳跃表

实现

跳跃表由zskiplistNode 和 zskiplist 两个结构定义，其中 zskiplistNode 表示跳跃表节点，用于 zskiplist 结构保存跳跃表节点的相关信息。

跳跃表结构如下：

最左侧是zskiplist结构，结构包含以下属性：

• header：表头节点
• tail：表尾节点
• level：记录跳跃表内，层数最大的节点的层数
• length：记录跳跃表长度

其中四个zskiplistNode 结构，包含如下属性：

• level：图中用 L1,L2,L3等字样标记节点的各个层，L1代表第一层，L2代表第二层…每个层带有两个属性：前进指针和跨度，前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。
• backward：节点中用 BW 字样标记节点的后退指针，指向位于当前节点的前个节点。
• score：各节点的1.0,2.0,3.0是节点所保存的分值，在跳跃表中，节点按各自所保存的分值从小到大排列。
• obj：各节点中的o1,o2,o3是节点所保存的成员对象

zskiplistNode

跳跃表节点定义如下：

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

层(Level)

跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快。

每次创建一个新跳跃表节点的时候，程序都根据幂次定律(power law，越大的数出现的概率越小）随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”。

前进指针

每个层都有一个指向表尾方向的前进指针(level[i].forward属性)，用于从表头向表尾方向访问节点。

跨度

层的跨度(level[i].span属性）用于记录两个节点之间的距离：

• 两个节点之间的跨度越大，它们相距得就越远。
• 指向NULL的所有前进指针的跨度都为0，因为它们没有连向任何节点。

后退指针

节点的后退指针(backward属性)用于从表尾向表头方向访问节点：跟可以一次跳过多个节点的前进指针不同，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。

分值和成员

节点的分值是一个double类型浮点数，跳跃表中所有节点都按分值从小到大排序。

节点的成员对象是一个指针，指向一个字符串对象，而字符串对象则保存着一个SDS值。

在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的：分值相同的节点将按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面（靠近表头的方向)，而成员对象较大的节点则会排在后面（靠近表尾的方向）。

zskiplist

仅靠多个跳跃表节点就可以组成一个跳跃表，如下图所示。

但通过使用一个zskiplist结构来持有这些节点，程序可以更方便地对整个跳跃表进行处理，比如快速访问跳跃表的表头节点和表尾节点，或者快速地获取跳跃表节点的数量(也即是跳跃表的长度）等信息。

跳跃表定义如下:

typedef struct zskiplist {
    // 表头节点和表尾节点
    structz skiplistNode *header, *tail;
    // 表中节点数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;
复制代码

header和tail指针分别指向跳跃表的表头和表尾节点，通过这两个指针，程序定位表头节点和表尾节点的复杂度为O(1)。

通过使用length属性来记录节点的数量，程序可以在O(1)复杂度内返回跳跃表的长度。

level属性则用于在O(1)复杂度内获取跳跃表中层高最大的那个节点的层数量，注意表头节点的层高并不计算在内。

小结

跳跃表是有序集合的底层实现之一，Redis的跳跃表由zskiplistNode 和 zskiplist 两个结构组成，其中 zskiplist 保存跳跃表信息，而zskiplistNode保存跳跃表节点。

为啥用跳表不用平衡树

1. 从内存占用上来比较，跳表比平衡树更灵活一些。平衡树每个节点包含 2 个指针（分别指向左右子树），而跳表每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。
2. 在做范围查找的时候，跳表比平衡树操作要简单。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。
3. 从算法实现难度上来比较，跳表比平衡树要简单得多。平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速。