首页 > 数据库 >Redis的zset的zrem命令可以做到O(1)吗?

Redis的zset的zrem命令可以做到O(1)吗?

时间:2024-07-06 18:31:37浏览次数:15  
标签:zset 删除 复杂度 Redis 算法 dict LogN zrem 节点

事情是这样的,当我用zrem命令去移除value的时候,我知道他之前会做的几个步骤

  • 1、查找这个value对应的score(通过zset中的dict)
  • 2、根据这个score查找到跳表中的节点
  • 3、删除这个节点

我就想了一下为什么dict为什么要保存score呢?如果保存的是跳表中的节点,那么不就可以做到删除O(1)了吗?理由很简单,链表的删除节点就是O(1)。

带着这个疑问,我百思不得其解,不得不深入一个源码探究一下究竟。我终于找到了真正的答案。

我们先来看看主逻辑在这里插入图片描述
可见,算法复杂度LogN就是在skiplist中删除元素。我们进去看看。
在这里插入图片描述
在skiplist中删除元素,大体上,其实就是两步

  • 1、找到所有level上目标节点的“后一个节点”。
  • 2、进行节点删除。

其中#1的算法复杂度就是O(LogN),最大结果是常数32。为什么要#1?
是因为skiplist删除节点时,需要对每层链表都做节点删除操作,这个操作规定了算法复杂度就是O(LogN),因为最差就是每个层级都要判断是否存在这个节点,存在的话需要做删除。

因此,回到问题本身,如果用dict保存节点指针,那么也是需要保存LogN个指针,虽然查找时,可以O(1)拿到所有需要删除的节点,但删除时,算法复杂度也是O(LogN)。存储指针没办法降低算法复杂度反而多了32倍内存!
跳表本身的数据结构规定了必定如此。这个问题本身就不是一个问题。

最后,我们一起看看真正的删除逻辑。
在这里插入图片描述
人生总是如此,给自己造一个难题,钻进去后才发现其实那个问题本来就不存在,但不重要了,这个过程反而挺有意思。

标签:zset,删除,复杂度,Redis,算法,dict,LogN,zrem,节点
From: https://blog.csdn.net/hayre/article/details/140219355

相关文章

  • Redis的数据类型
    1、五种常见的数据类型       String            String类型的三种格式                字符串                int              ......
  • 深入刨析Redis存储技术设计艺术(一)
    一、RedisObject1.1、Redis数据存储1.2、RedisObject的数据结构redis的value都封装在redisObject中redisObject的底层实现:redisObject的数据结构如下:server.htypedefstructredisObject{ unsignedtype:4; unsignedencoding:4; unsignedlru......
  • Redis 清理日志文件的策略
    目录Redis清理日志文件的策略1.Redis日志文件2.日志清理策略定期归档压缩归档文件设置日志文件大小限制注意事项结论Redis清理日志文件的策略在使用Redis时,日志文件可能会不断增长,占用磁盘空间。为了保持良好的系统性能和合理利用磁盘空间,我们需要实施一定的......
  • Redis怎么删除某个目录下的数据
    目录Redis怎么删除某个目录下的数据介绍步骤步骤1:连接到Redis步骤2:列出目录下的所有键步骤3:删除目录下的所有键步骤4:验证数据是否删除成功总结Redis怎么删除某个目录下的数据介绍在使用Redis进行缓存或数据存储时,有时候我们需要删除特定目录下的数据。本......
  • redis7.2 安装部署
    #redis7.2安装部署https://redis.io/download/https://github.com/redis/redis/tree/7.2wgethttps://github.com/redis/redis/archive/7.2.3.tar.gzredis-7.2.3]#yum-yinstallgccgcc-c++systemd-develuseraddredis-s/sbin/nologin-M#编译,生成system......
  • 面试必会之Redis篇
    01-你们项目中哪里用到了Redis?在我们的项目中很多地方都用到了Redis,Redis在我们的项目中主要有三个作用:使用Redis做热点数据缓存/接口数据缓存使用Redis存储一些业务数据,例如:验证码,用户信息,用户行为数据,数据计算结果,排行榜数据等使用Redis实现分布......
  • Redis 7.x 系列【19】管道
    有道无术,术尚可求,有术无道,止于术。本系列Redis版本7.2.5源码地址:https://gitee.com/pearl-organization/study-redis-demo文章目录1.往返时间2.管道技术3.代码演示4.其他批处理4.1原生批处理命令4.2事务4.3脚本1.往返时间官方文档Redis是一种基......
  • 安装Redis出现的问题
    当我使用brew下载redis时系统:macOS14$brewinstallredis报错信息:Error:git:unknownorunsupportedmacOSversion::dunnoError:'git'mustbeinstalledandinyourPATH!Warning:YouareusingmacOS14.Wedonotprovidesupportforthispre-releaseve......
  • Redis快速上手
    Redis检查Redis是否安装$redis-server--versionRedisserverv=7.2.4sha=00000000:0malloc=libcbits=64build=2d86b7859915655e如果成功安装,则会显示Redis的版本号。启动RedisMac:终端输入:$redis-serverWin:终端输入:$redis-server.exe启动后显示版本号和端口......
  • Redis数据结构-字典的实现
    字典,又称符号表(symboltable)、关联数组(associativearray)或者映射(map),是一种用于保存键值对(key-valuepair)的抽象数据结构。在字典中,一个键(key)可以和一个值(value)进行关联(或者说将键映射为值),这些关联的键和值就被称为键值对。字典中的每个键都是独一无二的,程序可以在字典......