Redis skiplist源码解析(支持范围查询)

2023-12-05 08:45

本文主要是介绍Redis skiplist源码解析(支持范围查询),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

跳表是一个多层的有序链表,在跳表中进行查询操作时,查询代码可以从最高层开始查询。层数越高,结点数越少,同时高层结点的跨度会比较大。因此,在高层查询结点时,查询一个结点可能就已经查到了链表的中间位置了。

这样一来,跳表就会先查高层,如果高层直接查到了等于待查元素的结点,那么就可以直接返回。如果查到第一个大于待查元素的结点后,就转向下一层查询。下层上的结点数多于上层,所以这样可以在更多的结点中进一步查找待查元素是否存在。

跳表的这种设计方法就可以节省查询开销,同时,跳表设计采用随机的方法来确定每个结点的层数,这样就可以避免新增结点时,引起结点连锁更新问题。

有些拗口,详细掰掰。

基础数据结构

zskiplist是一个多层的有序列表,是一个双向链表。

zskiplistNode:代表zskiplist里的每一个节点,包含了对象权重,权重越大越往后插入。

zskiplistLevel代表索引层级,每一层就是一个zskiplistLevel,插入时会采用随机分层方式决定当前元素插入到那一层去,或者直接加入一层。跨度是决定在当前层还要根据当前指针来计算还要跨过多少元素才可以插入。

/* ZSETs use a specialized version of Skiplists */
/** 跳跃表节点*/
typedef struct zskiplistNode {// 成员对象robj *obj;// 分值double score;// 后退指针struct zskiplistNode *backward;// 层struct zskiplistLevel {// 前进指针struct zskiplistNode *forward;// 跨度unsigned int span;} level[];} zskiplistNode;/** 跳跃表*/
typedef struct zskiplist {// 表头节点和表尾节点struct zskiplistNode *header, *tail;// 表中节点的数量unsigned long length;// 表中层数最大的节点的层数int level;} zskiplist;

查询元素过程(level->score->sds)

level层: 从头节点开始直接从层级最高的地方开始由上往下查询。

score权重:同一层比较的就是score大小,score越大越往后。

sds数据:发生score相等的场景,这个时候就会比较数据的大小。

zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range) {zskiplistNode *x;int i;/* If everything is out of range, return early. */if (!zslIsInRange(zsl,range)) return NULL;// 遍历跳跃表,查找符合范围 min 项的节点// T_wrost = O(N), T_avg = O(log N)x = zsl->header;for (i = zsl->level-1; i >= 0; i--) {/* Go forward while *OUT* of range. */while (x->level[i].forward &&!zslValueGteMin(x->level[i].forward->score,range))x = x->level[i].forward;}/* This is an inner range, so the next node cannot be NULL. */x = x->level[0].forward;redisAssert(x != NULL);/* Check if score <= max. */// 检查节点是否符合范围的 max 项// T = O(1)if (!zslValueLteMax(x->score,range)) return NULL;return x;
}/** 检测给定值 value 是否大于(或大于等于)范围 spec 中的 min 项。** 返回 1 表示 value 大于等于 min 项,否则返回 0 。** T = O(1)*/
static int zslValueGteMin(double value, zrangespec *spec) {return spec->minex ? (value > spec->min) : (value >= spec->min);
}/** 检测给定值 value 是否小于(或小于等于)范围 spec 中的 max 项。** 返回 1 表示 value 小于等于 max 项,否则返回 0 。** T = O(1)*/
static int zslValueLteMax(double value, zrangespec *spec) {return spec->maxex ? (value < spec->max) : (value <= spec->max);
}

插入元素过程

1、层数算法:随机生成每个结点的层数

过程:初始化层数为1,生成一个随机数,如果一个随机数的小于拟定的25%的概率,层数+1,直到拟定的最大层数64为止。

这个算法并不是真正意义上的二分查找法,它永远不会保证上层和下层1:2的比例,同时这个算法可以避免插入删除更新导致连续更新问题(一个元素改后面元素全部需要改),仅仅只需要修改下指针即可。

/* Returns a random level for the new skiplist node we are going to create.** 返回一个随机值,用作新跳跃表节点的层数。** The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL* (both inclusive), with a powerlaw-alike distribution where higher* levels are less likely to be returned. ** 返回值介乎 1 和 ZSKIPLIST_MAXLEVEL 之间(包含 ZSKIPLIST_MAXLEVEL),* 根据随机算法所使用的幂次定律,越大的值生成的几率越小。* ZSKIPLIST_P  指跳表结点增加层数的概率,值为 0.25* T = O(N)*/
int zslRandomLevel(void) {int level = 1;while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))level += 1;return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

 插入过程:和查询一样,sds数据从小到大,每一层从小到大,层数也是由小到大。

/* Insert (element,score) pair in ziplist. ** 将 ele 成员和它的分值 score 添加到 ziplist 里面** ziplist 里的各个节点按 score 值从小到大排列** This function assumes the element is not yet present in the list. ** 这个函数假设 elem 不存在于有序集*/
unsigned char *zzlInsert(unsigned char *zl, robj *ele, double score) {// 指向 ziplist 第一个节点(也即是有序集的 member 域)unsigned char *eptr = ziplistIndex(zl,0), *sptr;double s;// 解码值ele = getDecodedObject(ele);// 遍历整个 ziplistwhile (eptr != NULL) {// 取出分值sptr = ziplistNext(zl,eptr);redisAssertWithInfo(NULL,ele,sptr != NULL);s = zzlGetScore(sptr);if (s > score) {/* First element with score larger than score for element to be* inserted. This means we should take its spot in the list to* maintain ordering. */// 遇到第一个 score 值比输入 score 大的节点// 将新节点插入在这个节点的前面,// 让节点在 ziplist 里根据 score 从小到大排列zl = zzlInsertAt(zl,eptr,ele,score);break;} else if (s == score) {/* Ensure lexicographical ordering for elements. */// 如果输入 score 和节点的 score 相同// 那么根据 member 的字符串位置来决定新节点的插入位置if (zzlCompareElements(eptr,ele->ptr,sdslen(ele->ptr)) > 0) {zl = zzlInsertAt(zl,eptr,ele,score);break;}}/* Move to next element. */// 输入 score 比节点的 score 值要大// 移动到下一个节点eptr = ziplistNext(zl,sptr);}/* Push on tail of list when it was not yet inserted. */if (eptr == NULL)zl = zzlInsertAt(zl,NULL,ele,score);decrRefCount(ele);return zl;
}

这篇关于Redis skiplist源码解析(支持范围查询)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/456892

相关文章

C#使用StackExchange.Redis实现分布式锁的两种方式介绍

《C#使用StackExchange.Redis实现分布式锁的两种方式介绍》分布式锁在集群的架构中发挥着重要的作用,:本文主要介绍C#使用StackExchange.Redis实现分布式锁的... 目录自定义分布式锁获取锁释放锁自动续期StackExchange.Redis分布式锁获取锁释放锁自动续期分布式

MySQL 中的 JSON 查询案例详解

《MySQL中的JSON查询案例详解》:本文主要介绍MySQL的JSON查询的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 的 jsON 路径格式基本结构路径组件详解特殊语法元素实际示例简单路径复杂路径简写操作符注意MySQL 的 J

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

Redis Pipeline(管道) 详解

《RedisPipeline(管道)详解》Pipeline管道是Redis提供的一种批量执行命令的机制,通过将多个命令一次性发送到服务器并统一接收响应,减少网络往返次数(RTT),显著提升执行效率... 目录Redis Pipeline 详解1. Pipeline 的核心概念2. 工作原理与性能提升3. 核

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

redis过期key的删除策略介绍

《redis过期key的删除策略介绍》:本文主要介绍redis过期key的删除策略,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录第一种策略:被动删除第二种策略:定期删除第三种策略:强制删除关于big key的清理UNLINK命令FLUSHALL/FLUSHDB命

java解析jwt中的payload的用法

《java解析jwt中的payload的用法》:本文主要介绍java解析jwt中的payload的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java解析jwt中的payload1. 使用 jjwt 库步骤 1:添加依赖步骤 2:解析 JWT2. 使用 N