【Redis】跳跃表

Metadata

title: 【Redis】 跳跃表
date: 2023-07-09 08:32
tags:
  - 行动阶段/完成
  - 主题场景/数据存储
  - 笔记空间/KnowladgeSpace/ProgramSpace/BasicsSpace
  - 细化主题/数据存储/Redis
categories:
  - 数据存储
keywords:
  - 数据存储/Redis
description: 【Redis】 跳跃表

概述

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

如果一个有序集合中包含的元素数量比较多，又或者有序集合中元素的成员是较长的字符串，Redis 就会使用跳跃表来作为有序集合键的底层实现。Redis 只有在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中作为内部数据结构。

跳跃表是有序集合的底层实现之一。
Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点。
每个跳跃表节点的层高都是1至32之间的随机数。
在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。
跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。

跳跃表的实现

Redis 的跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个数据结构定义。

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

跳跃表由 zskiplist 组织，通过多个跳跃表节点 zskiplistNode 组成一个跳跃表。值得注意的是，记录 level 时，表头节点的层高不会记录在内。

跳跃表节点

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

跳跃表的时间复杂度

操作	时间复杂度
插入新节点和分值	“平均O(logN),最坏O(N),N为跳跃表长度”
删除给定成员和分值	“平均O(logN), 最坏O(N),N为跳跃表长度”
返回给定成员和分值节点的排位	“平均O(logN), 最坏O(N),N为跳跃表长度”
释放给定跳跃表	“O(N),N为跳跃表的长度”
删除给定排位范围内节点	“O(N),N为被删除节点数”
“给定分值范围,返回是否有节点”	O(1)
“给定分值范围,返回第一个符合节点”	“平均O(logN), 最坏O(N),N为跳跃表长度”

跳跃表 API

函数	作用	时间复杂度
zslCreate	创建-一个新的跳跃表	O(1)
zslFree	“释放给定跳跃表,以及表中包含的所有节点”	“0(N),N为跳跃表的长度”
zslInsert	将包含给定成员和分值的新节点添加到跳跃表中	“平均O(logN),最坏o(M), N为跳跃表长度”
zslDelete	删除跳跃表中包含给定成员和分值的节点	“平均 O(logN),最坏o(N, N为跳跃表长度”
zslGetRank	返回包含给定成员和分值的节点在跳跃表中的排位	“平均 O(logN),最坏O(N),N为跳跃表长度”
zslGetElementByRank	返回跳跃表在给定排位上的节点	“平均O(logM), 最坏O(N), N为跳跃表长度”
zslIsInRange	“给定一个分值范围(range), 比如0 到15, 20到28,诸如此类,如果跳跃表中有至少一个节点的分值在这个范围之内,那么返回1,否则返回0”	“通过跳跃表的表头节点和表尾节点, 这个检测可以用0(1)复杂度完成”
zslFirstInRange	“给定一个分值范围,返回跳跃表中第一个符合这个范围的节点”	“平均O(logN), 最坏O(M)。N为跳跃表长度”
zslLastInRange	“给定一个分值范围,返回跳跃表中最后一个符合这个范围的节点”	“平均O(logN),最坏0(N)。N为跳跃表长度”
zslDeleteRangeByScore	“给定一个分值范围,删除跳跃表中所有在这个范围之内的节点”	“O(N),N为被删除节点数量”
zslDeleteRangeByRank	“给定一个排位范围,删除跳跃表中所有在这个范围之内的节点”	“O(N),N为被删除节点数量”