Redis 设计与实现——跳跃表

ゝ一纸荒年。 2022-09-08 15:44 127阅读 0赞

# 跳跃表 #

## 跳跃表概述 ##

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

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

## Redis 跳跃表的实现 ##

跳跃表是一种可以对有序链表进行近似二分查找的数据结构，redis 在两个地方用到了跳跃表，一个是实现**有序集合**，另一个是在**集群节点**中用作内部数据结构。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQnJlYWQgU2ly_size_20_color_FFFFFF_t_70_g_se_x_16]  
位于图片最左边的是 zskiplist 结构， 该结构包含以下属性：

*  header：指向跳跃表的表头节点。
 *  tail：指向跳跃表的表尾节点。
 *  level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
 *  length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。

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

位于 zskiplist 结构右方的是四个 zskiplistNode 结构， 该结构包含以下属性：

*  层（level）：节点中用 L1 、 L2 、 L3 等字样标记节点的各个层， L1 代表第一层， L2 代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。
 *  后退（backward）指针：节点中用 BW 字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。因为每个节点只有一个后退指针，所以每次只能后退至前一个节点。
 *  分值（score）：各个节点中的 1.0 、 2.0 和 3.0 是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。
 *  成员对象（obj）：各个节点中的 o1 、 o2 和 o3 是节点所保存的成员对象。

typedef struct zskiplistNode {
        
        sds ele;
        double score;
        struct zskiplistNode *backward; // 后退指针
        struct zskiplistLevel {
        
            struct zskiplistNode *forward; // 前进指针
            unsigned long span; // 跨度。记录两个节点之间的距离。跨度实际上是用来计算排位（rank）的： 在查找某个节点的过程中， 将沿途访问过的所有层的跨度累计起来， 得到的结果就是目标节点在跳跃表中的排位。
        } level[];
    } zskiplistNode;

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAQnJlYWQgU2ly_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/6f1dc6df47754d9eb65a31d7499c7694.png