Redis数据结构——跳跃表-skiplist

青旅半醒 2021-09-23 16:12 424阅读 0赞

跳跃表简介：

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

跳跃表支持评价O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树来得更简单，所以有不少程序都是用跳跃表来代替平衡树。

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

Redis只在两个地方用到了跳跃表。一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。

**1、跳跃表的实现**

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppbnd1ZmVpeWFuZw_size_16_color_FFFFFF_t_70][]

上图最左边的就是zskiplist结构，该结构包含以下属性：

*   header：指向跳跃表的表头表头节点
 *  tail：指向跳跃表的表尾节点。
 *  level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）。
 *  记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内）。位于zskiplist结构右方的四个zskiplistNode结构，该结构包含一下属性：

1）层：如图L1、L2、L3等标记节点的各个层。每层都有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点。跨度记录了前进指针所指向节点和当前节点的距离。图里的箭头表示前进指针，数字表示跨度。

2）后退指针：BW标记的后退指针，指向位于当前节点的前一个节点。后退指针用于表尾向表头遍历使用。

3）分值：在跳跃表中，节点按照各自所保存的分值从小到大排列。

4）成员对象：各个节点的o1、o2等是节点所保存的成员对象。

**1.1、跳跃表节点定义：**

/* ZSETs use a specialized version of Skiplists */
    typedef struct zskiplistNode {
    //成员对象
    robj *obj;
    //分值
    double score;
    //后退指针
    struct zskiplistNode *backward;
    //层
        struct zskiplistLevel {
            struct zskiplistNode *forward;//前进指针
            unsigned int span;//跨度
        } level[];
    } zskiplistNode;

1.2、跳跃表定义：

仅靠多个跳跃表节点就可以组成一个跳跃表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppbnd1ZmVpeWFuZw_size_16_color_FFFFFF_t_70 1][]

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

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

![2020011221374086.png][]

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

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

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

**重点回顾：**

1.  跳跃表是有序集合的底层实现之一
2.  Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成，zskiplistNode用于表示跳跃表节点，zskiplist用于表示跳跃表信息。
3.  每个跳跃表节点的层高都是1到32之间的随机数
4.  在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点成员对象必须是唯一的。
5.  跳跃表节点按照分值大小排序，当分值相同，节点按照成员对象的大小进行排序。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppbnd1ZmVpeWFuZw_size_16_color_FFFFFF_t_70]: /images/20210923/a238c786e9c34c239cf7252d2ce1e864.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppbnd1ZmVpeWFuZw_size_16_color_FFFFFF_t_70 1]: /images/20210923/52207841cd4541799e7566f555f4eee3.png
[2020011221374086.png]: /images/20210923/268086a3c599452ebf45fd970ce03ac9.png