Redis跳表介绍（redis为什么使用跳表而不是红黑树）

wptr33 2025-02-03 15:29 47 浏览

跳表的诞生可以简单用下面的例子来看：假设一个有序链表，查询某个节点的时间复杂度是O（n），那接下来在链表上层再建立一条链表，每两个结点提取一个结点到上一级，形成L1级缓存链表，如下：

这样当我们要找寻8时，先通过L1索引链表找到7，然后在向下一级链表遍历就找了8，这比直接遍历链表的效率提高了不少，同理，再添加一级L2索引，如图：

查找8的时候先从L2级索引链表开始遍历，遍历的节点个数进一步减少，查找的时间复杂度比单纯的链表遍历进一步提升。

以上是跳表的一个思想，实现起来不同的应用实现的方式不尽相同，这里看一下在Redis中是如何设计并实现跳表。

在Redis中，有序集合的实现方式采用了跳表。跳表是由zskiplistNode和skiplist两个结构定义,其中 zskiplistNode结构表示跳表节点, zskiplist结构则用于保存跳表节点的相关信息,比如节点的数量,以及指向表头节点和表尾节点的指针等等。结构图如下：

其中zskiplist和zskiplistNode结构如下：

typedef struct zskiplist {

    // 头节点，尾节点
    struct zskiplistNode *header, *tail;

    // 节点数量
    unsigned long length;

    // 目前表内节点的最大层数
    int level;

} zskiplist;

typedef struct zskiplistNode {

    // member 对象
    robj *obj;

    // 分值
    double score;

    // 后退指针
    struct zskiplistNode *backward;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 这个层跨越的节点数量
        unsigned int span;

    } level[];

} zskiplistNode;

当一个节点插入时，首先要计算出这个节点所在的level数，这是一个概率型的数据结构，元素的插入层数是随机指定的。Willam Pugh在论文中描述了它的计算过程如下：

指定节点最大层数 MaxLevel，指定概率 p，默认层数 lvl 为1
生成一个0~1的随机数r，若r<p，且lvl<MaxLevel ，则lvl ++
重复第 2 步，直至生成的r >p 为止，此时的 lvl 就是要插入的层数。

论文中生成随机层数的伪码：

具体的加入、删除等操作源码自行撸代码吧！

redis 集合

上一篇：带你走进 Redis（带你走进南京主持词作文）
下一篇：基于Python的Redis操作（python中redis的用法）

Redis跳表介绍（redis为什么使用跳表而不是红黑树）

相关推荐

C# 13 和 .NET 9 全知道 :13 使用 ASP.NET Core 构建网站 (1)

程序员的开源月刊《HelloGitHub》第 71 期

详细介绍一下Redis的Watch机制，可以利用Watch机制来做什么?

假如有100W个用户抢一张票，除了负载均衡办法，怎么支持高并发?

Java面试必考问题:什么是乐观锁与悲观锁

如何将AI助手接入微信（打开ai手机助手）

SparkSQL——DataFrame的创建与使用

redission YYDS spring boot redission 使用

一文带你了解Redis与Memcached? redis与memcached的区别

如何利用Redis进行事务处理呢? 如何利用redis进行事务处理呢英文