解析Redis 跳跃表深入解读源码(redis 跳跃表源码)

2023-05-10 13:09:30 源码 跳跃 解读

Redis 跳跃表是 Redis 内部数据结构中非常重要的一种,它具有高效插入、删除,可以支持范围查找的特性,被用于实现有序集合等其他数据结构,因此 Redis 跳跃表有着很高的学习价值。

一、Redis 跳跃表概述

Redis 跳跃表是由一组节点组成的有序数据结构,它能够有效维护一个有序列表,具有高效插入、删除以及范围查找的特性,它在 Redis 中最常见的用法是用于实现有序集合。

二、Redis 跳跃表结构

Redis 跳跃表有一个头结点,该结点包含多个比较函数,其中最重要的比较函数是用于比较元素大小的,这样就能确定元素的排序。

每个跳跃表节点包含一下内容:

(1)Score:用于表示元素的大小

(2)Object :表示元素的值,可以是指针或者普通的数字

(3)Level:索引的层级深度,决定该节点出现在那些skiplist层上

(4)Backward :指向上一个节点的指针

(5)Forward :指向下一个节点的指针

最外围的一层指针称为header链表,指向第一层非空链表的第一个节点,称为首节点。

三、Redis 跳跃表操作

(1)插入

删除元素的操作非常简单,只需要将跳跃表中已有的节点连接在一起即可,它的实现原理与排序链表相似,它会从头结点开始,依次与每一层链表的首节点进行比较,直到找到合适的位置,插入新的节点。

(2)删除

它与插入类似,只需要从被删除节点开始,依次与每一层中首节点进行比较,直到找到被删除节点的上一个节点。

(3)搜索

搜索也是实现Redis跳跃表的关键,它会从头结点开始,然后下降到指定的层,然后从指定的节点开始向后顺序搜索,直到找到需要的元素或者到达表尾结束。

四、源码分析

// 创建一个跳跃表

t_skiplist *skiplistCreate(void)

{

int i;

t_skiplist *sl;

// 申请内存空间

if ((sl = zmalloc(sizeof(*sl))) == NULL)

return NULL;

// 设置头节点数据

sl->level = 1;

sl->length = 0;

// 初始化头结点

if ((sl->header = zmalloc(sizeof(*sl->header))) == NULL)

{

zfree(sl);

return NULL;

}

// 设置比较函数

sl->header->obj = NULL;

for (i = 0; i

{

sl->header->level[i].forward = NULL;

}

sl->tl = NULL;

return sl;

}

以上代码中的skiplistCreate函数就是用来创建一个新的跳跃表的。首先分配一个跳跃表的内存空间,并且为头结点分配空间用于保存一个可比较函数,用于比较元素大小。然后给每一层链表中最前头的节点赋值 NULL,表示该层链表尚未有任何元素。最后将尾节点置空,表示跳跃表的数据为空。

综上,Redis 跳跃表能够有效的维护一个有序列表,它因此在 Redis 中被广泛使用,它的实现原理也比较简单,

相关文章