解析Redis 跳跃表深入解读源码（redis 跳跃表源码）

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 中被广泛使用，它的实现原理也比较简单，