redis数据库查找key在内存中的位置的方法

一、预先需要了解的知识
1、redis 中的每一个数据库，都由一个 redisDb 的结构存储。其中，redisDb.id 存储着 redis 数据库以整数表示的号码。redisDb.dict 存储着该库所有的键值对数据。redisDb.expires 保存着每一个键的过期时间。
2、当redis 服务器初始化时，会预先分配 16 个数据库（该数量可以通过配置文件配置），所有数据库保存到结构 redisServer 的一个成员 redisServer.db 数组中。当我们选择数据库 select number  时，程序直接通过 redisServer.db[number] 来切换数据库。有时候当程序需要知道自己是在哪个数据库时，直接读取 redisDb.id 即可。
3、既然我们知道一个数据库的所有键值都存储在redisDb.dict中，那么我们要知道如果找到key的位置，就有必要了解一下dict 的结构了：


代码如下:

typedef struct dict {

// 特定于类型的处理函数
dictType *type;

// 类型处理函数的私有数据
void *privdata;

// 哈希表（2个）
dictht ht[2];

// 记录 rehash 进度的标志，值为-1 表示 rehash 未进行
int rehashidx;

// 当前正在运作的安全迭代器数量
int iterators;
} dict;

由上述的结构可以看出，redis 的字典使用哈希表作为其底层实现。dict 类型使用的两个指向哈希表的指针，其中 0 号哈希表（ht[0]）主要用于存储数据库的所有键值，而1号哈希表主要用于程序对 0 号哈希表进行 rehash 时使用，rehash 一般是在添加新值时会触发，这里不做过多的赘述。所以redis 中查找一个key，其实就是对进行该dict 结构中的 ht[0] 进行查找操作。
4、既然是哈希，那么我们知道就会有哈希碰撞，那么当多个键哈希之后为同一个值怎么办呢？redis采取链表的方式来存储多个哈希碰撞的键。也就是说，当根据key的哈希值找到该列表后，如果列表的长度大于1，那么我们需要遍历该链表来找到我们所查找的key。当然，一般情况下链表长度都为是1，所以时间复杂度可看作o(1)。
二、当redis 拿到一个key 时，如果找到该key的位置。
了解了上述知识之后，我们就可以来分析redis如果在内存找到一个key了。
1、当拿到一个key后， redis 先判断当前库的0号哈希表是否为空，即：if (dict->ht[0].size == 0)。如果为true直接返回NULL。
2、判断该0号哈希表是否需要rehash，因为如果在进行rehash，那么两个表中者有可能存储该key。如果正在进行rehash，将调用一次_dictRehashStep方法，_dictRehashStep 用于对数据库字典、以及哈希键的字典进行被动 rehash，这里不作赘述。
3、计算哈希表，根据当前字典与key进行哈希值的计算。
4、根据哈希值与当前字典计算哈希表的索引值。
5、根据索引值在哈希表中取出链表，遍历该链表找到key的位置。一般情况，该链表长度为1。
6、当 ht[0] 查找完了之后，再进行了次rehash判断，如果未在rehashing，则直接结束，否则对ht[1]重复345步骤。
到此我们就找到了key在内存的中位置了。

赞 (0)

相关推荐

  • 浅谈redis采用不同内存分配器tcmalloc和jemalloc

    我们知道Redis并没有自己实现内存池,没有在标准的系统内存分配器上再加上自己的东西.所以系统内存分配器的性能及碎片率会对Redis造成一些性能上的影响. 在Redis的 zmalloc.c 源码中,我们可以看到如下代码: /* Double expansion needed for stringification of macro values. */ #define __xstr(s) __str(s) #define __str(s) #s #if defined(USE_TCMALLOC

  • Redis教程(十一)：虚拟内存介绍

    一.简介: 和大多NoSQL数据库一样,Redis同样遵循了Key/Value数据存储模型.在有些情况下,Redis会将Keys/Values保存在内存中以提高数据查询和数据修改的效率,然而这样的做法并非总是很好的选择.鉴于此,我们可以将之进一步优化,即尽量在内存中只保留Keys的数据,这样可以保证数据检索的效率,而Values数据在很少使用的时候则可以被换出到磁盘.     在实际的应用中,大约只有10%的Keys属于相对比较常用的键,这样Redis就可以通过虚存将其余不常用的Keys和Val

  • Redis教程(十四)：内存优化介绍

    一.特殊编码: 自从Redis 2.2之后,很多数据类型都可以通过特殊编码的方式来进行存储空间的优化.其中,Hash.List和由Integer组成的Sets都可以通过该方式来优化存储结构,以便占用更少的空间,在有些情况下,可以省去9/10的空间.     这些特殊编码对于Redis的使用而言是完全透明的,事实上,它只是CPU和内存之间的一个交易而言.如果内存使用率方面高一些,那么在操作数据时消耗的CPU自然要多一些,反之亦然.在Redis中提供了一组配置参数用于设置与特殊编码相关的各种阈值,如

  • 降低PHP Redis内存占用

    降低PHP Redis内存占用

    1.降低redis内存占用的优点 1.有助于减少创建快照和加载快照所用的时间 2.提升载入AOF文件和重写AOF文件时的效率 3.缩短从服务器进行同步所需的时间 4.无需添加额外的硬件就可以让redis存贮更多的数据 2.短结构 Redis为列表.集合.散列.有序集合提供了一组配置选项,这些选项可以让redis以更节约的方式存储较短的结构. 2.1.ziplist压缩列表(列表.散列.有续集和) 通常情况下使用的存储方式 当列表.散列.有序集合的长度较短或者体积较小的时候,redis将会采用一种

  • 将MongoDB作为Redis式的内存数据库的使用方法

     基本思想 将MongoDB用作内存数据库(in-memory database),也即,根本就不让MongoDB把数据保存到磁盘中的这种用法,引起了越来越多的人的兴趣.这种用法对于以下应用场合来讲,超实用: 置于慢速RDBMS系统之前的写操作密集型高速缓存 嵌入式系统 无需持久化数据的PCI兼容系统 需要轻量级数据库而且库中数据可以很容易清除掉的单元测试(unit testing) 如果这一切可以实现就真是太优雅了:我们就能够巧妙地在不涉及磁盘操作的情况下利用MongoDB的查询/检索功能.可

  • redis数据库查找key在内存中的位置的方法

    一.预先需要了解的知识1.redis 中的每一个数据库,都由一个 redisDb 的结构存储.其中,redisDb.id 存储着 redis 数据库以整数表示的号码.redisDb.dict 存储着该库所有的键值对数据.redisDb.expires 保存着每一个键的过期时间.2.当redis 服务器初始化时,会预先分配 16 个数据库(该数量可以通过配置文件配置),所有数据库保存到结构 redisServer 的一个成员 redisServer.db 数组中.当我们选择数据库 select n

  • C#查找对象在ArrayList中出现位置的方法

    本文实例讲述了C#查找对象在ArrayList中出现位置的方法.分享给大家供大家参考.具体分析如下: 我们可以通过IndexOf方法来查找对象在ArrayList中的位置 ArrayList alcollect = new ArrayList(); // Add individual items to the collection string str = "learn csharp"; alcollect.Add(str); //find position of object Con

  • javascript 折半查找字符在数组中的位置(有序列表)

    复制代码 代码如下: /** * 折半查找字符在数组中的位置(有序列表) * @param array 被检索的数组 * @param x 要查找的字符 * @type int * @returns 字符在数组中的位置,没找到返回-1 */ function binarySearch(array,x){ var lowPoint=1; var higPoint=array.length; var returnValue=-1; var midPoint; var found=false; whi

  • Android手机内存中文件的读写方法小结

    本文实例总结了Android手机内存中文件的读写方法.分享给大家供大家参考.具体分析如下: 如何对手机内存中的文件数据进行读写呢? Context提供了领个方法来打开该应用程序的数据文件夹中的文件I/O流,具体如下: FileInputStream openFileInput(String name) 打开应用程序的数据文件夹下的name文件对应的数据流 FileOutputSream openFileOutput(String name, int mode) 打开应用程序数据文件夹下的name

  • Python 查找字符在字符串中的位置实例

    如下所示: str_1='wo shi yi zhi da da niu ' char_1='i' nPos=str_1.index(char_1) print(nPos) 运行结果:7 ========是使用find========== str_1='wo shi yi zhi da da niu ' char_1='i' nPos=str_1.find(char_1) print(nPos) 结果:5 ========如何查找所有'i'在字符串中位置呢?=========== #开挂模式 s

  • C#搜索文字在文件及文件夹中出现位置的方法

    C#搜索文字在文件及文件夹中出现位置的方法

    本文实例讲述了C#搜索文字在文件及文件夹中出现位置的方法.分享给大家供大家参考.具体如下: 在linux中查询文字在文件中出现的位置,或者在一个文件夹中出现的位置,用命令: 复制代码 代码如下: grep -n '需要查询的文字' * 就可以了.今天做了一个C#程序,专门用来找出一个指定字符串在文件中的位置,与一个指定字符串在一个文件夹中所有的出现位置. 一.程序代码 using System; using System.Collections.Generic; using System.Lin

  • Java解析word,获取文档中图片位置的方法

    Java解析word,获取文档中图片位置的方法

    前言(背景介绍): Apache POI是Apache基金会下一个开源的项目,用来处理office系列的文档,能够创建和解析word.excel.ppt格式的文档. 其中对word文档的处理有两个技术,分别是HWPF(.doc)和XWPF(.docx).如果你对这两个技术熟悉的话,就应该能明白使用java解析word文档的痛楚所在. 其中两个最大的问题在于: 第一是这两个类并没有统一的父类和接口(隔壁的XSSF和HSSF投过来鄙视的眼光),所以没法进行同一格式的接口式编程: 第二是官方API中并

  • java保证对象在内存中唯一性的实现方法

    前言 刚看到这个题目的朋友第一反应肯定是好奇,之后再细细思考下就会发现这个题目眼熟了. 就算是同一个答案,如果提问的方式不同, 往往会对回答造成干扰或者影响, 上学的时候老师也说过差不多的话, 学过设计模式的人看到这个题目之后肯定不会陌生:请描述java中单例设计模式的实现步骤,那估计就能答出来了. 而java中的单例模式,相信只要是你看过一些java视频教程,肯定就能写出来的. 所以我们在平时学习的时候要注意举一反三,掌握其精髓,这样在面试或者工作的时候才能应对自如,久而久之,就成为了大神级别

  • 更改SQL Server 2005数据库中tempdb位置的方法

    了解SQL Server 2005数据库的朋友可能都知道,tempdb系统数据库是一个全局资源,可供连接到SQL Server 2005实例的所有用户使用.我们有时候为了操作方便,常常会更改一下tempdb数据库的位置,那么该如何操作呢?本文我们就来介绍这一更改的过程. 获得tempdb的原始位置: select [name],[physical_name] from sys.master_files where database_id=db_id(N'tempdb') 更改tempdb数据库位

  • Redis数据库的使用场景介绍（避免误用Redis）

    Redis 是目前 NoSQL 领域的当红炸子鸡,它象一把瑞士军刀,小巧.锋利.实用,特别适合解决一些使用传统关系数据库难以解决的问题.但是 Redis 不是银弹,有很多适合它解决的问题,但是也有很多并不适合它解决的问题.另外,Redis 作为内存数据库,如果用在不适合的场合,对内存的消耗是很可观的,甚至会让系统难以承受. 我们可以对系统存储使用的数据以两种角度分类,一种是按数据的大小划分,分成大数据和小数据,另一种是按数据的冷热程度划分,分成冷数据和热数据,热数据是指读或写比较频繁的数据,反之

随机推荐