Redis跳表数据结构

-- 《Redis设计与实现》

t_zset.c

时间复杂：O(logN)

数据结构概述说明：

-每个跳表层高1~32层

-跳跃表是有序集合的实现之一

-按分数升序排序

其核心结构源代码如下：

typedef struct zskiplistNode {// 保存当前跳跃表的节点信息      sds ele;      double score;// 分值      struct zskiplistNode *backward;// 后退指针      struct zskiplistLevel {// 这是1~32层的节点          struct zskiplistNode *forward;// 前进指针          unsigned long span;// 跨度      } level[];  } zskiplistNode;  typedef struct zskiplist {// 保存整个跳跃表的头尾指针、长度、level      struct zskiplistNode *header, *tail; // 指向跳跃表头尾节点      unsigned long length;// 跳跃表长度      int level;// 记录跳跃表中最大的层数  } zskiplist;

让我们谈谈核心方法的实施方法

创建一个新的跳表(函数:zslCreate）

创建zskiplist，然后填写默认属性

2插入(函数:zslInsert）

从最大层数据开始，找到当前层的最大分数（<=当前要插入的节点(记录在updatete中)[i])记录跨度(记录在rank中)[i])。然后将新插入的节点的每层指向相同的下一个节点。

3内部删除函数(函数:zslDeleteNode）

删除相应的节点

其它自己看gitee~~~~~~~~~~~~~~

ps 图灵课堂老师从近一百套最新一线互联网公司面试题中精选而出，涵盖Java架构面试 所有技术栈，包括JVM，Mysql，并发，Spring，Redis，MQ，Zookeeper，Netty， Dubbo，Spring Boot，Spring Cloud，数据结构与算法，设计模式等相关技术领域的大 厂面试题及详解。 详情咨询客服获取全套面经试题。