Redis--原理--如何通过key找到value

落日映苍穹つ 2023-10-02 15:12 75阅读 0赞

原文网址：[Redis--原理--如何通过key找到value\_IT利刃出鞘的博客-CSDN博客][Redis--_--_key_value_IT_-CSDN]

## 简介 ##

本文介绍Redis是如何通过key找到value的。

## Redis的存储 ##

**redis的总的数据结构**

redis 中的每一个数据库，都由一个 redisDb 的结构存储。其中，redisDb.id 存储着 redis 数据库的号码（以整数表示）。redisDb.dict 存储着该库所有的键值对数据。redisDb.expires 保存着每一个键的过期时间。

**数据库号**

当redis 服务器初始化时，会预先分配 16 个数据库（该数量可以通过配置文件配置），所有数据库保存到结构 redisServer 的一个成员 redisServer.db 数组中。当我们选择数据库 select number 时，程序直接通过 redisServer.db\[number\] 来切换数据库。有时候当程序需要知道自己是在哪个数据库时，直接读取 redisDb.id 即可。

**字典结构**

一个数据库的所有键值都存储在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\] 进行查找操作。

**哈希碰撞**

既然是哈希，就会有哈希碰撞，那么当多个键哈希之后为同一个值怎么办呢？redis采取链表的方式来存储多个哈希碰撞的键。也就是说，当根据key的哈希值找到该列表后，如果列表的长度大于1，那么我们需要遍历该链表来找到我们所查找的key。当然，一般情况下链表长度都为是1，所以时间复杂度可看作O(1)。

## 根据key查找value的流程 ##

了解上述内容之后，本处分析redis如何通过key在内存中找到value。

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在内存中的位置了

## 其他网址 ##

[字典 — Redis 设计与实现][_ Redis]

[redis怎样找到key在内存中的位置\_agangdi的博客-CSDN博客][redis_key_agangdi_-CSDN]

[Redis--_--_key_value_IT_-CSDN]: https://knife.blog.csdn.net/article/details/121312160
[_ Redis]: https://redisbook.readthedocs.io/en/latest/internal-datastruct/dict.html#id4
[redis_key_agangdi_-CSDN]: https://blog.csdn.net/agangdi/article/details/21567199