Redis中有序集合的内部实现方式的详细介绍

目录
  • 有序集合的内部实现
  • 以压缩列表作为内部实现
  • 以跳跃表作为内部实现
  • 内部实现的转换
  • 总结

面试官:Redis中基本的数据类型有哪些?

我:Redis的基本数据类型有:字符串(string)、哈希(hash)、列表(list)、集合(set)、有序集合(zset)。

面试官:有序集合的内部实现方式是什么?

我还沉浸在上一个问题的沾沾自喜中,顿时表情凝固了,手心开始冒出冷汗。“这个。。没有太深入了解”,我支支吾吾的说到。

面试官:回去等消息吧。

这句话说的干净利落,然后就没有然后了。失败是成功的妈妈,我不气馁,决定马上恶补一下。

有序集合的内部实现

有序集合的内部实现有两种,分别是:压缩列表(ziplist)和跳跃表(skiplist)。接下来,我们分别进行详细的了解。

以压缩列表作为内部实现

当有序集合的元素个数小于zset-max-ziplist-entries(默认为128个),并且每个元素成员的长度小于zset-max-ziplist-value(默认为64字节)的时候,使用压缩列表作为有序集合的内部实现。

每个集合元素由两个紧挨在一起的两个压缩列表结点组成,其中第一个结点保存元素的成员,第二个结点保存元素的分支。压缩列表中的元素按照分数从小到大依次紧挨着排列,有效减少了内存空间的使用。

举个例子,我们使用zadd命令创建一个以压缩列表为实现的有序集合:

127.0.0.1:6379> zadd one-more-zset 1 one 2 two 3 three
(integer) 3
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "one"
2) "two"
3) "three"
127.0.0.1:6379> object encoding one-more-zset
"ziplist"

以跳跃表作为内部实现

当有序集合的元素个数大于等于zset-max-ziplist-entries(默认为128个),或者每个元素成员的长度大于等于zset-max-ziplist-value(默认为64字节)的时候,使用跳跃表作为有序集合的内部实现。

此时,在有序集合中其实包含了两个结构,一个是跳跃表,另一个是哈希表。

在跳跃表中,所有元素按照从小到大的顺序排列。跳跃表的结点中的object指针指向元素成员的字符串对象,score保存了元素的分数。通过跳跃表,Redis可以快速地对有序集合进行分数范围、排名等操作。

在哈希表中,为有序集合创建了一个从元素成员到元素分数的映射。键值对中的键指向元素成员的字符串对象,键值对中的值保存了元素的分数。通过哈希表,Redis可以快速查找指定元素的分数。

虽然有序集合同时使用跳跃表和哈希表,但是这两种数据结构都使用指针共享元素中的成员和分数,不会额外的内存浪费。

举个例子,我们使用zadd命令创建一个以跳跃表为实现的有序集合:

127.0.0.1:6379> zadd one-more-zset 1 long-long-long-long-long-long-long-long-long-long-long-long-long-long
(integer) 1
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "long-long-long-long-long-long-long-long-long-long-long-long-long-long"
127.0.0.1:6379> object encoding one-more-zset
"skiplist"

内部实现的转换

当一个有序集合是以压缩列表作为内部实现时,再向这个有序集合添加较长的元素成员,或向这个有序集合的元素个数过多时,那么这个有序集合就会转换为以跳跃表作为内部实现。但是,以跳跃表作为内部实现的有序集合不会转换为以压缩列表作为内部实现。

举个例子,我们先创建一个以压缩列表作为内部实现的有序集合:

127.0.0.1:6379> zadd one-more-zset 1 one 2 two 3 three
(integer) 3
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "one"
2) "two"
3) "three"
127.0.0.1:6379> object encoding one-more-zset
"ziplist"

然后,再向它添加一个较长成员的元素,它就是转换为以跳跃表作为内部实现:

127.0.0.1:6379> zadd one-more-zset 4 long-long-long-long-long-long-long-long-long-long-long-long-long-long
(integer) 1
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "one"
2) "two"
3) "three"
4) "long-long-long-long-long-long-long-long-long-long-long-long-long-long"
127.0.0.1:6379> object encoding one-more-zset
"skiplist"

然后,再把那一个较长成员的元素从有序集合中移除,有序集合依然是以跳跃表作为内部实现:

127.0.0.1:6379> zrem one-more-zset long-long-long-long-long-long-long-long-long-long-long-long-long-long
(integer) 1
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "one"
2) "two"
3) "three"
127.0.0.1:6379> object encoding one-more-zset
"skiplist"

总结

在Redis中,有序集合的内部实现有压缩列表(ziplist)和跳跃表(skiplist)两种,当集合中的所有元素的成员长度较短并元素个数较少时,使用压缩列表作为内部实现,否则使用跳跃表和哈希表作为内部实现。当条件不满足时,压缩列表可以转换为跳跃表,但跳跃表不能转换为压缩列表。

到此这篇关于Redis中有序集合的内部实现方式的详细介绍的文章就介绍到这了,更多相关Redis有序集合的内部实现内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Redis有序集合类型的操作_动力节点Java学院整理

    今天我们说一下Redis中最后一个数据类型 "有序集合类型",回首之前学过的几个数据结构,不知道你会不会由衷感叹,开源的世界真好,写这些代码的好心人真的要一生平安哈,不管我们想没想的到的东西,在这个世界上都已经存在着,曾几何时,我们想把所有数据按照数据结构模式组成后灌输到内存中,然而为了达到内存共享的方式,不得不将这块内存单独部署,同时还要考虑怎么序列化,何时序列互的问题,烦心事太多太多...后来才知道有redis这么个玩意,能把高级的,低级的数据结构单独包装到一个共享内存中(Redi

  • 利用Redis的有序集合实现排行榜功能实例代码

    前言 游戏中存在各种各样的排行榜,比如玩家的等级排名.分数排名等.玩家在排行榜中的名次是其实力的象征,位于榜单前列的玩家在虚拟世界中拥有无尚荣耀,所以名次也就成了核心玩家的追求目标. 一个典型的游戏排行榜包括以下常见功能: 能够记录每个玩家的分数: 能够对玩家的分数进行更新: 能够查询每个玩家的分数和名次: 能够按名次查询排名前N名的玩家: 能够查询排在指定玩家前后M名的玩家. 更进一步,上面的操作都需要在短时间内实时完成,这样才能最大程度发挥排行榜的效用. 由于一个玩家名次上升x位将会引起x+

  • 使用Redis有序集合实现IP归属地查询详解

    工作中经常遇到一类需求,根据 IP 地址段来查找 IP 对应的归属地信息.如果把查询过程放到关系型数据库中,会带来很大的 IO 消耗,速度也不能满足,显然是不合适的. 那有哪些更好的办法呢?为此做了一些尝试,下面来详细说明. 构建索引文件 在 GitHub 上看到一个ip2region 项目,作者通过生成一个包含有二级索引的文件来实现快速查询,查询速度足够快,毫秒级别.但如果想更新地址段或归属地信息,每次都要重新生成文件,并不是很方便. 不过还是推荐大家看看这个项目,其中建索引的思想还是很值得学

  • Redis有序集合类型的常用命令小结

    一.有序集合类型 有序集合类型,大家从名字上应该就可以知道,实际上就是在集合类型上加了个有序而已.Redis中的有序集合类型,实际上是在集合类型上,为每个元素都关联一个分数,有序实际上说的是分数有序,我们根据分数的范围获取集合及其他操作.集合的元素依然是不能够相同的,但是分数可以相同. 下面列举有序集合和类型和列表类型的相似处: ①两者都是有序的(废话!) ②两者都可以获得某一范围的元素 下面列举区别: ①列表是链表实现的,靠近两边的数据读取极快,而元素过多后获取中间元素的速度则会很慢:有序集合

  • Redis中有序集合的内部实现方式的详细介绍

    目录 有序集合的内部实现 以压缩列表作为内部实现 以跳跃表作为内部实现 内部实现的转换 总结 面试官:Redis中基本的数据类型有哪些? 我:Redis的基本数据类型有:字符串(string).哈希(hash).列表(list).集合(set).有序集合(zset). 面试官:有序集合的内部实现方式是什么? 我还沉浸在上一个问题的沾沾自喜中,顿时表情凝固了,手心开始冒出冷汗.“这个..没有太深入了解”,我支支吾吾的说到. 面试官:回去等消息吧. 这句话说的干净利落,然后就没有然后了.失败是成功的

  • 详解PHP多个进程配合redis的有序集合实现大文件去重

    1.对一个大文件比如我的文件为 -rw-r--r-- 1 ubuntu ubuntu 9.1G Mar 1 17:53 2018-12-awk-uniq.txt 2.使用split命令切割成10个小文件 split -b 1000m 2018-12-awk-uniq.txt -b 按照字节切割 , 支持单位m和k 3.使用10个php进程读取文件 , 插入redis的有序集合结构中 , 重复的是插不进去的 ,因此可以起到去重的作用 <?php $file=$argv[1]; //守护进程 uma

  • php使用redis的有序集合zset实现延迟队列应用示例

    本文实例讲述了php使用redis的有序集合zset实现延迟队列.分享给大家供大家参考,具体如下: 延迟队列就是个带延迟功能的消息队列,相对于普通队列,它可以在指定时间消费掉消息. 延迟队列的应用场景: 1.新用户注册,10分钟后发送邮件或站内信. 2.用户下单后,30分钟未支付,订单自动作废. 我们通过redis的有序集合zset来实现简单的延迟队列,将消息数据序列化,作为zset的value,把消息处理时间作为score,每次通过zRangeByScore获取一条消息进行处理. <?php

  • python redis连接 有序集合去重的代码

    python redis连接 有序集合去重的代码如下所述: # -*- coding: utf-8 -*- import redis from constant import redis_ip, redis_db, redis_pw, redis_zset_name pool = redis.ConnectionPool(host=redis_ip, db=redis_db, password=redis_pw) # pool = redis.ConnectionPool(db=6, passw

  • 使用go操作redis的有序集合(zset)

    我就废话不多说了,大家还是直接看代码吧~ package main import ( "fmt" "github.com/garyburd/redigo/redis" ) func main() { // 连接redis数据库,指定数据库的IP和端口 conn, err := redis.Dial("tcp", "36.99.16.197:6379") if err != nil { fmt.Println("Con

  • redis中的配置以及密码设置方式

    目录 前言 参数介绍 bind protected-mode requirepass 总结 上线部署 线下调试 前言 redis默认情况下是没有密码的,这很容易导致服务器被攻击,被挖矿! 今天就给大家简单讲解一下自己在配置redis过程中所学习的,方便大家以后快速的上手. 注意:如果想快速配置则不需要看参数介绍,直接看总结!!! 参数介绍 redis中主要有三个参数来进行安全控制的,也是我们最常用的三个. bind ①这个参数默认值是127.0.0.1,也就是只允许redis所在机器访问redi

  • JQuery中阻止事件冒泡几种方式及其区别介绍

    JQuery 提供了两种方式来阻止事件冒泡. 方式一:event.stopPropagation(); 复制代码 代码如下: $("#div1").mousedown(function(event){ event.stopPropagation(); }); 方式二:return false; 复制代码 代码如下: $("#div1").mousedown(function(event){ return false; }); 但是这两种方式是有区别的.return

  • spring四种依赖注入方式的详细介绍

    平常的java开发中,程序员在某个类中需要依赖其它类的方法,则通常是new一个依赖类再调用类实例的方法,这种开发存在的问题是new的类实例不好统一管理,spring提出了依赖注入的思想,即依赖类不由程序员实例化,而是通过spring容器帮我们new指定实例并且将实例注入到需要该对象的类中.依赖注入的另一种说法是"控制反转",通俗的理解是:平常我们new一个实例,这个实例的控制权是我们程序员,而控制反转是指new实例工作不由我们程序员来做而是交给spring容器来做. spring有多种

  • java 线程中start方法与run方法的区别详细介绍

    线程中start方法与run方法的区别 在线程中,如果start方法依次调用run方法,为什么我们会选择去调用start方法?或者在java线程中调用start方法与run方法的区别在哪里?  这两个问题是两个非常流行的初学者级别的多线程面试问题.当一个Java程序员开始学习线程的时候,他们首先会学着去继承Thread类,重载run方法或者实现Runnable接口,实现run方法,然后调用Thread实例的start方法.但是当他拥有一些经验之后,他通过查看API文档或者其他途径会发现start

随机推荐