首页 > 数据库 >redis为什么一定要用跳表实现有序集合,却不用平衡树,红黑树或者B+树呢?

redis为什么一定要用跳表实现有序集合,却不用平衡树,红黑树或者B+树呢?

时间:2024-04-14 17:23:25浏览次数:19  
标签:redis 插入 跳表 红黑树 平衡 节点

平衡树vs跳表

平衡树必须满足所有节点的左右子树高度差不超过1,也就是平衡因子范围为[-1,1]。

但是对于范围查询来说,利用平衡树通过中序遍历达到和跳表一样的效果,但是平衡树的每一次插入或者删除操作都需要保证整棵树的绝对平衡,

只要不平衡就会通过旋转的方式来重新保持平衡,这个过程就非常耗时。

 

红黑树vs跳表

红黑树就是一种黑色平衡树,也就是说从任意节点到另外一个叶子节点,所经过的黑色节点是一样的。如果对红黑树进行

插入操作时,需要通过旋转和染色来保持黑平衡。这个过程相对于平衡树来说需要的开销要小一点。

但是红黑树在查找数据的过程中效率却比不了跳表。

 

 

B+树vs跳表

1.B+树可以包含多个子节点,能够有效减少树的高度。

2.每个非叶子节点存储多个key,叶子节点可以存储多个value,因此每个节点更能够存储更多的键。

3.拥有绝对的平衡,每个树的各个分支高度相差不大。

4.能够按照顺序访问。

5.插入数据可以让整棵树分布更加均匀,保证范围查询和删除效率。

B+树更适合用于数据库和文件系统,可以通过较少的IO定位到尽可能多的索引来获取查询数据。

但是对于redis来说,redis是内存数据库不需要存储大量的数据,也就是对于索引不需要通过B+树这种方式进行维护,

只需要按照概率进行随机维护就可以了,这样就能够节省内存。而且使用跳表进行插入操作的时候只需要通过索引将数据插入到

链表中去即可,不需要像B+树那样插入的时候发现失去平衡后还需要对节点进行分裂与合并。

 

标签:redis,插入,跳表,红黑树,平衡,节点
From: https://www.cnblogs.com/huwy-123/p/18134390

相关文章

  • 04_NET中使用Redis(ServiceStack.Redis)和Linux中安装Redis
    官网:Redis-TheReal-timeDataPlatformLinux安装Redis: 1.安装gcc安装gccyum-yinstallgcctcl如果出现Complete表示成功查看gcc版本gcc-v 2.升级gcc升级到gcc9.3:yum-yinstallcentos-release-sclyum-yinstalldevtoolset-9-gccdevtoolset-9-gcc-c++......
  • 15、数据库加固-redis 加固
    1.禁止网络访问Redis服务更改配置文件,使服务监听本地回环地址修改redis配置文件:vi安装路径/redis.conf确保:bind127.0.0.1(::1:表示ipv6回环地址)2.设置防火墙过滤浏览(与禁止网络访问相对应,两者设置一种即可)设置iptables防火墙,确保访问源安全允许某源地址访问服务器的......
  • kubesphere应用系列(二)部署有状态服务redis
    前言在Kubernetes中,服务(Service)可以被分为有状态服务和无状态服务,个人认为的区别:无状态服务是指不依赖于任何持久化状态的服务。它们通常是将请求处理为独立、无关的事务,并且在不同的请求之间不会保留任何信息或状态。无状态服务的每个请求都可以独立处理,而不需要与之前或之后......
  • springboot集成redis
    首先引入依赖<!--redis坐标--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency>在yml中引入redis数据库spring......
  • redis自学(33)哨兵的作用和工作原理
    新建sentinel.conf文件。输入下面的内容  1是端口号2是sentinel声明的ip3是sentinel监控的master的ip和端口号,mymaster是集群的名字,也可以理解成给主节点起的名字,可以任意起名字。Slave的信息是从master得到的。2是选举master时的quorum值4是slave与master断开的最长超时......
  • python - redis rdb备份文件导入本地
    1.安装 rdbtoolspipinstallrdbtools 2.安装 python-lzfpipinstallpython-lzf 3. rdb文件导出为json文件rdb--cjson路径名称/备份文件名称.rdb-fxx.json 4. 解析json文件withopen('文件路径/xx.json','r')asjson_file:res=json.loa......
  • 对于redis和数据库数据不一致性的解决方案
    对比两种方案:1)先更新数据库,然后删redis。此方案,如果先更新数据库,然后服务宕机没有删除缓存,那么redis中存的一直是脏数据。2)先删除redis,然后更新数据库此方案,如果数据库更新时间比较长,查询操作比较频繁,会导致取到数据库的脏数据。(并发量不高的情况下使用)3)先删除redis,然后再......
  • redis基础
    redis数据类型redis可以理解成一个全局的大字典,key就是数据的唯一标识符。根据key对应的值不同,可以划分成5个基本数据类型。redis={"name":"yuan","scors":["100","89","78"],"info":{"name":"rain"......
  • Redis--缓存雪崩、击穿、穿透
    本文转载自:https://xiaolincoding.com/redis/cluster/cache_problem.html 缓存异常会面临的三个问题:缓存雪崩、击穿和穿透。其中,缓存雪崩和缓存击穿主要原因是数据不在缓存中,而导致大量请求访问了数据库,数据库压力骤增,容易引发一系列连锁反应,导致系统奔溃。不过,一旦数据被重新......
  • redis
    什么是Redisredis是一种基于内存的数据库,因为对数据的读写是在内存当中完成的,所以读写速度非常快,常用于缓存、消息队列、分布式锁等场景redis提供了多种数据类型来支持不同的业务场景,比如说String、Hash、List、Set(集合)等等,并且对数据类型的操作都是原子性的,因为执行命......