Redis的跳跃表

在Redis中,有一种高效的数据结构叫做有序集合(zset)

它是一种集合,其中每个成员(member)都会关联一个分数(score)。
zset既可以快速地通过member找到该成员对应的分数,又可以按照分数的大小进行范围查询,这对于实现排行榜等功能非常有用。那么zset是如何实现这样的功能的呢?答案是跳跃表(skiplist)。

1. zset的底层实现

思考这么几个问题:

  • zset是如何快速的根据成员取得对应的分数?
  • zset是如何快速的取得指定排行区间的所有成员和分数?
  • zsetzrevrange(逆序)又是如何实现的?
  • zset如何计算一个成员的排位?

  • 第一个问题我们很容易想到使用哈希表,实际上zset的底层实现,就是一个哈希表+跳跃表,看看结构:(对于元素数量少的情况,zset会使用另一种实现方式,我们这里不作讨论)
1
2
3
4
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;

哈希表(dict)大部分人都了解,那么对于这个跳跃表(zskiplist),又是怎样的结构呢?

2.跳跃表的结构和特性

跳跃表是一种有序链表+多层索引的结构,使得包含n个元素的有序序列的查找和插入操作的平均时间复杂度都是 O(logn)\Omicron \left(\log{n}\right)
跳跃表是按层建造的,最底层是一个普通的有序链表。
众所周知,如果是一个有序的数组,我们可以通过二分查找,很快的找到其中的某个元素。那么对于一个有序的链表,我们有没有办法也使用二分查找呢?
跳跃表的想法就是用空间换时间:在最底层的原始链表上面,加多一层索引,元素数量为原始链表的一半,如图所示:
image
这样查找的时候,原本要比较n个元素,通过使用索引,减少到 n2\frac{n}{2}
但是这样还不够,所以我们在上面再多加几层索引,如图所示:
image
理论上,对于元素数量为n的链表,我们可以建立 log2n\log_{2}{n} 层索引。
这样,我们就能通过从最高层开始,通过二分查找的方式,快速的查找某个数值在链表中的位置。

3.实现细节

Redis的跳跃表实现主要有两个结构:zskiplistNodezskiplist,其中zskiplistNode是跳跃表的结点,而zskiplist则记录整个表的一些信息,如结点的数量等。
image
上图展示了一个跳跃表的实例。左边代表着跳跃表的整体结构:zskiplist

zskiplist的代码如下:

1
2
3
4
5
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;

headertail:分别指向跳跃表头结点和尾结点,其中头结点在zskiplist创建时生成,并不实际存储数据。
length:跳跃表的长度,通过这个变量,可以在O(1)时间内获取长度。
level:当前跳跃表中最高的层,不包括头结点。

每次创建新结点的时候,redis根据幂次定律(越大的数出现概率越小)随机生成一个高度(介于1和32),作为当前结点的level数组的长度,也就是这个结点的高度。

结点zskiplistNode的代码如下:

1
2
3
4
5
6
7
8
9
typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned long span;
} level[];
} zskiplistNode;

ele:每个结点的成员,sdsredis内置的简单动态字符串结构(Simple Dynamic String)
score:每个结点的分数,是double类型
backward:回退指针,用于从表尾向表头遍历。用来实现zrevrange
level:每个层级上的索引。

注意level中的每一层,除了指向下一个结点的指针以外,还有一个span表示跨度,即下一个结点和当前结点的距离。(示例图中,箭头上面的数字)
这个跨度用来计算排行,由于redis的跳跃表并不是严格的按照每层数量减半的实现,所以在高层,每一次跨越几个原始结点,只能存储在这个span中,而在遍历的时候,通过计算跨度的和,就可以知道当前排在第几位了。

上图中红色和绿色都是zskiplistNode结构,其中headerbackward/ele/score都是没用的,所以省略了没画出来

4 与其他结构的对比

和红黑树这类平衡树结构相比,跳跃表的算法复杂度一样,而主要优势在于实现简单,且在并发环境下更加高效;
与哈希表相比,跳跃表支持有序数据的快速检索和范围查询,但牺牲了一些插入和删除操作的性能。
总的来说,跳跃表是一种空间换时间,以及用随机化处理平衡的高效数据结构。

参考资料:


Redis的跳跃表
https://blog.supersource.top/skip_list_in_redis/
作者
看热闹的咸鱼
发布于
2024年4月2日
许可协议