Redis之跳跃表

本文阅读 7 分钟
首页 代码,Java 正文

通过将有序集合的部分节点分层,由最上层开始一次向后查找,如果本层的next节点大于要查找的值或next节点为NULL,则从本节点开始,降低一层继续向后查找,依次类推,如果找到则返回节点;否则返回NULL。采用该原理查找节点,在节点数量比较多时,可以跳过一些节点,查询效率大大提升,这就是跳跃表的基本思想。

img 跳跃表有如下性质:

  • 跳跃表由很多层结构
  • 跳跃表有一个头节点,头节点中有一个64层的结构,每层的结构包含指向本层的下个节点的指针,指向本层下个节点中间所跨越的节点个数为本层的跨度
  • 除了头节点外,层数最多的节点的层高为跳跃表的高度(level)
  • 每层都是一个有序链表,数据递增
  • 除了header节点外,一个元素在上层有序链表中出现,则它一定会在下层有序链表中出现
  • 跳跃表每层最后一个节点指向NULL,表示本层有序链表的结束
  • 跳跃表拥有一个tail指针,指向跳跃表的最后一个节点。
  • 最底层的有序链表包含所有节点,最底层的节点个数为跳跃表的长度(length)(不包括头节点)
  • 每个节点包含一个后退指针,头节点和第一个节点指向NULL;其他节点指向最底层的前一个节点

跳跃表每个节点维护了多个指向其他节点的指针,所以在跳跃表进行查找、插入、删除操作时可以跳过一些节点,快速找到操作需要的节点。归根结底,跳跃表是以牺牲空间的形式来达到快速查找的目的。跳跃表和平衡树相比,实现方式更简单,只需要熟悉有序链表,就可以轻松的掌握跳跃表。

跳跃表节点结构

跳跃表节点的zskiplistNode 结构体如下:

typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

该结构体包含如下属性:

  • ele:用于存储字符串类型的数据。
  • score:用于存储排序的分值。
  • backward:后退指针,只能指向当前节点最底层的前一个节点,头节点和第一个节点----backward指向NULL,从后向前遍历跳跃表时使用。
  • level:为柔性数组。每个节点数组长度不一样,在生成跳跃表节点时,随机生成一个1~64的值,值越大出现的概率越低。 level数组的每项包含以下两个元素:
    - forward :指向本层下一个节点,尾节点forward指向NULL。 - span:forward指向的节点与本节点之间的元素个数。span值越大,跳过了节点个数越多。

跳跃表结构

除了跳跃表节点外,还需要一个跳跃表结构来管理节点,Redis使用zskiplist结构体,如下:

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

该结构体包含如下属性:

  • header:指向跳跃表节点。头节点是跳跃表的一个特殊节点,它的level数组元素个数为64。头节点在有序集合中不存储任何member和score值,ele值为NULL,score值为0;也不计入跳跃表的总长度。头节点在初始化时,64个元素的forward都指向NULL,span值都为0。
  • tail:指向跳跃表尾节点。
  • length:跳跃表长度,表示除头节点之外的节点总数。
  • level:跳跃表的高度。 通过跳跃表结构体的属性可知,程序可以在O(1)的时间复杂度下,快速获取到跳跃表的头节点、尾节点、长度和高度。

创建跳跃表

Redis5中节点层高最小值为1,最大值为64。 Redis通过函数随机生成一个1~64的值,作为新建节点的高度,值越大出现的概率越低。**节点层高确定之后便不会再修改。

跳跃表的每个节点都是有序集合的一个元素,在创建跳跃表节点时,待创建节点的层高、分值、member等都已确定。对于跳跃表的每个节点,我们需要申请内存来存储。

zskiplistNode 结构体的最后一个元素为柔性数组,申请内存时需要指定柔性数组的大小,一个节点占用的内存大小为zskiplistNode 的内存大小与level个zskiplistLevel的内存大小之和。 分配好空间后,进行节点变量初始化。

头节点是一个特殊的节点,不存储有序集合的member信息。头节点是跳跃表中第一个插入的节点,其level数组的每项forward都为NULL,span值都为0.

创建完头节点后,就可以创建跳跃表

  • 创建跳跃表结构体对象zsl。
  • 将zsl的头节点指针指向新创建的头节点。
  • 跳跃表层高初始化为1,长度初始化为0,尾节点指向NULL。

插入节点

插入节点的步骤:

  • 查找要插入的位置
  • 调整跳跃表高度
  • 插入节点
  • 调整backward

删除节点

删除节点的步骤:

  • 查找需要更新的节点
  • 设置span和forward

删除跳跃表

获取到跳跃表对象之后,从头节点的第0层开始,通过forward指针逐步向后遍历,每遇到一个节点便释放其内存。当所有节点的内存都被释放之后,释放跳跃表对象,即完成了跳跃表的删除操作。

redis之详解

本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://blog.csdn.net/qq_38571892/article/details/122128402
-- 展开阅读全文 --
Web安全—逻辑越权漏洞(BAC)
« 上一篇 03-13
Redis底层数据结构--简单动态字符串
下一篇 » 04-10

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复