Fork me on GitHub

四、Redis-跳跃表

发表于

前言

自己一直秉持这样一句话，”过程是扎实的，结果肯定是必然的”

静心学习，沉淀。。。

跳跃表介绍

跳跃表(skiplist)是一种有序的数据结构，它通过在每个结点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。其支持平均O(logN)、最坏O(N)复杂度的节点查找。

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

跳跃表的实现

zskiplist
Redis中的跳跃表由 zskiplist 和 zskiplistNode 两个结构定义。

zskiplist 结构用于保存跳跃表节点信息(节点数量，指向表头结点和表尾节点的指针等)

zskiplistNode 结构用于表示跳跃表节点

image

图中最左边的即是 zskiplist ，zskiplist右边的是四个 zskiplistNode 结构

zskiplist

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

zskiplistNode

  • 层(level)：节点中L1，L2，L3等字样，L1代表第一层，L2代表第二层。每个层都有前进指针和跨度两个属性。
  • 后退指针：节点中使用 BW 表示，它指向位于当前节点的前一个节点。
  • 分值(score)：各个节点中的1.0、2.0等都是节点的分值，在跳跃表中，节点按各自所保存的分值从小到大排序。
  • 成员对象：各个节点的o1、o2、o3是节点的保存的成员对象

跳跃表节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct zskiplistNode{
    // 后退指针
    struct zskiplistNode *backward;
    
    // 分值
    double score;
    
    // 成员对象
    robj *obj;
    
    //层
    struct zskiplistLevel{
        // 前进指针
        struct zskiplistNode *forward;
        
        // 跨度
        unsigned int span;
    }level[];
} zskiplistNode;

层

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

创建一个新的跳跃表节点时，程序都根据幂次定律随机生成一个介于 1 和 32 之间的值作为 level 数组的大小，这个大小就是层的高度。

前进指针

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

跨度

每个层中的 level[i].span 称为层的跨度，两个节点之间跨度越大，它们相距就越远。

当我们查找某个节点的时候，将沿途访问的所有的层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位

后退指针

节点中的 backward 称为节点的后退指针，用于从表尾向表头方向访问，跟前进指针不同，因为每个结点只有一个后退指针，所以每次只能后退一至前一个节点。

分值和成员

节点的分值(score 属性)是一个 double 类型的浮点数，跳跃表中所有节点都是按照分值大小来排序的。

节点的成员对象( obj 属性)是一个指针，指向一个字符串对象。

在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的。

跳跃表

1
2
3
4
5
6
7
8
9
10
struct zskiplist{
    //表头节点和表尾节点
    struct skiplistNode *header,*tail;
    
    //表中节点的数量
    unsigned long length;
    
    //表中层数最大的节点的层数
    int level;
} zskiplist;