第五章 跳跃表

• 跳跃表是一种有序的数据结构，通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
• 跳跃表支持平均O(logN),最坏O(n)复杂度节点查找，还可以通过顺序性操作来批量处理节点。
• redis使用跳跃表作为有序集合键的底层实现之一，第一种场景：有序集合包含的元素数量比较多，或者有序集合中元素的成员是比较长的字符串时；第二种场景：集群节点中用作内部的数据结构；

5.1跳跃表的实现

• 跳跃表由zskiplistNode和zskiplist两个结构定义，其中zskiplistNode结构用于表示跳跃表的节点，而zskiplist结构用于保存跳跃表节点的相关信息，如：节点数量，指向表头节点和表尾节点的指针

WechatIMG62.jpeg

• 最左边是zskiplist结构，包含以下属性： 右方4个是zskiplistNode结构，包含以下属性：
  • header：指向跳跃表的表头节点。
  • tail：指向跳跃表的表尾节点
  • level：记录跳跃表内，层数最大的那个节点层数（表头节点层数不计算在内）
  • length：记录跳跃表长度，也就是跳跃表中节点数量（表头节点不计算在内）
• 右方4个是zskiplistNode结构，包含以下属性：
  • 层(level): 用 L1（第一层），L2（第二层）标记各个层，level数组可以包含多个元素，每个元素包含一个指向其他节点的指针，通过这些层来加快访问其他节点的速度，层数越多访问越快。每次创建一个新的节点时，程序会根据幂次定律（越大的数出现的概率越小）随机生成一个介于1-32之间的值作为level数组的大小，这个大小就是层的高度；�每个层带有两个属性：
    • 前进指针：用于访问位于表尾方向的其他节点；从表头向表尾进行遍历时，会沿着前进指针进行
    • 跨度：记录了前进指针所指向节点和当前节点的距离。两个节点之间跨度越大，相距的越远；指向null的所有指针的跨度都为0；跨度实际上是用于计算排位的：在查找某个节点，将沿途访问过的所有层跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。
  • 后退指针（BW）：指向位于当前节点的前一个节点；从表尾向表头进行遍历时使用。
  • 分值(score)：是一个double类型的浮点数，各个节点中1.0，2.0是节点所保存的分值。表中，节点按各自所保存的分值从小到大排列；
  • 成员对象(obj)：他是一个指针，指向一个字符串对象，字符串对象则保存一个SDS值，节点中的o1，o2是节点所保存的成员对象。

5.1.1 跳跃表节点

结构定义

typedef struct zskiplistNode{
    //后退指针
    struct zskiplistNode *backward;
     //分值
    double score;
     //成员对象
    rob *obj;
     //层
    struct zskiplistLevel{
         //前进指针
        struct zskiplistNode *forward;
         //跨度
        unsigned int span;
    } level[];
}zskiplistNode;

WechatIMG63.jpeg

5.1.2 跳跃表

多个跳跃表节点就可以组成一个跳跃表，通过zskiplist结构来持有这些节点；

结构定义

 typedef struct zskiplist{
    //表头节点和表尾节点
    structz skiplistNode *header ,*tail;

    //表中节点的数量
    unsigned long length;

    //表中层数最大的节点的层数
    int level;
} zskiplist；

header 和 tail 分别指向表头和表尾节点，定位表头或表尾节点的时间复杂度是O(1);
length属性来记录节点的数量，时间复杂度为O(1);
level属性获取跳跃表中最大的节点层的数量，时间复杂度为O(1);

跳跃表API

函数:作用	时间复杂度
zslCreate:创建一个新的跳跃表	O(1)
zslFree:释放给定的跳跃表，以及表中包含的所有节点	O(n)
zslInsert:将包含给定成员和分值的新节点添加到跳跃表中	平均O(logN),最坏O(N)
zslDelete:删除跳跃表中包含给定成员和分值的节点	平均O(logN),最坏O(N)
zslGetRank:返回包含给定成员和分值的节点在跳跃表中的排位	平均O(logN),最坏O(N)
zslGetElementByRank:返回跳跃表在给定排位上的节点	平均O(logN),最坏O(N)
zslIsInRange:给定一个分值范围（range），比如0-15，如果给定的分值范围包含在跳跃表的分值范围内，就返回1，否则返回0；	通过表头和表尾节点检测，可以用 O(1)完成
zslFirstInRange:给定一个分值范围，返回表中第一个符合这个范围的节点	平均O(logN),最坏O(N)
zslLastInRange:给定一个分值范围，返回表中最后一个符合这个范围的节点	平均O(logN),最坏O(N)
zslDeleteRangeByScore:给定一个分值范围，删除跳跃表中所有在这个范围的节点	O(N)
zslDeleteRangeByRank:给定一个排位范围，删除跳跃表中所有在这个范围的节点	O(N)