redis key值如何定位到value

问题：

我想往redis中设置一个缓存，其中key是由两部分组成

• 业务标识，REDIS_CACHE_XXX，这是固定不变的
• 用户名，user_name，根据业务使用不同而不同

现在key可能有两种情况

• REDIS_CACHE_XXX_user_name
• user_name_REDIS_CACHE_XXX

请问这两种key的查询性能有区别吗？

错误思路：

认为key是匹配是字符串匹配，那么差异性大的(user_name)放前面，可以快速匹配返回

实际

redis底层定位实际上是hash定位的，无论key怎么声明，在没有hash碰撞的时候，查询性能都是O(1)

本质就是一个分布式hashMap

引申问题

数据库联合索引/索引（仅对于B+树索引），为什么要尽量把索引建立在有区别度的索引上

提示：索引需要排序，按照的是字符串的自然顺序，不能进行hash

---

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 设计与实现