Redis 底层数据结构之跳跃表

实现一个有序集合有多种方式:数组、链表、平衡树等,每种方式都有其优缺点:

  • 数组查询效率高,但需要申请连续的内存空间,且插入删除需要移动大量元素;
  • 链表不需要申请连续空间,插入删除效率高,但查询效率低;
  • 平衡树或红黑树效率较高但实现复杂,不容易维护。

Redis 中的有序集合 zset 支持快速查找,并支持范围查询,底层使用跳跃表实现,跳跃表对比平衡树或红黑树,查询效率相当,但原理及实现方式简单得多,便于维护。

跳跃表的基本原理

跳跃表基于有序链表,通过空间换时间的方式,支持快速查找,其基本原理是在有序链表的基础上建立分层索引,每一层索引也是有序链表。

一个普通的有序链表实例:

在有序数组中,我们可以通过下标访问的方式使用二分查找提高查询效率,对于有序链表来说,我们如何建立索引,来达到二分查找的效果呢?一个简单的方式是:从完整链表中,选取部分节点构建一个新的链表作为索引,索引节点拥有两个方向的指针,一个指向同层索引的下一个节点,一个指向低一层的原始节点,按照这个规则建立几层索引后,最上层索引节点数远小于原始节点数:

这样一来,我们在查询某个节点的时候,先从一层索引开始查找,查找到合适的位置,然后下降到低一层索引,以此类推,实现了一种 n 分查找的模式,这就是跳跃表的基本原理。

Redis 中的跳跃表

基本结构
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;    /* 指向同层索引的下个节点 */
        unsigned long span;    /* 跳过的节点个数 */
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;    /* 原始节点总数 */
    int level;    /* 跳跃表高度,即节点最大层数 */
} zskiplist;

ele 用于存储字符串类型数据,score 存储排序的分值。由于高一层索引中的节点必然存在于低一层索引中,所以 zskiplistNode 使用 level 数组来聚合垂直方向的索引节点,同时增加 backward 指针指向前一个节点,用于支持反向遍历,一个典型的 Redis 跳跃表结构如下:

索引的维护

很显然,节点的插入和删除需要重新维护索引,如果不维护索引,在极端情况下,两个节点间插入的新节点越来越多,最终跳跃表会退化为有序单链表。

根据 Redis 跳跃表节点的定义可知,level 数组的大小决定了每个节点在各层索引中是否存在,新加入节点的高度由 zslRandomLevel 给定:

#define ZSKIPLIST_MAXLEVEL 32
#define ZSKIPLIST_P 0.25

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

level 初始值为 1,在循环中每次生成一个随机值,并取低 16 位和 0.25 倍的 0xFFFF 相比较,来决定高度是否加 1,节点层高最大不超过 32。层数为 i 时,概率为 (1-p)*p^(i-1),通过等比数列计算公式可知,层高在默认参数下的期望值为 1/(1-p) = 1.33。

为新节点分配空间并初始化后,需要修改各层索引的指针并更新跳跃表的 level 信息。


参考资料:

  1. Redis 5 设计与源码分析 —— 陈雷