redis數(shù)據(jù)庫查找key在內(nèi)存中的位置的方法

2020-10-29 21:51:10

字體：大中小

供稿：網(wǎng)友

一、預先需要了解的知識
1、redis 中的每一個數(shù)據(jù)庫，都由一個 redisDb 的結(jié)構(gòu)存儲。其中，redisDb.id 存儲著 redis 數(shù)據(jù)庫以整數(shù)表示的號碼。redisDb.dict 存儲著該庫所有的鍵值對數(shù)據(jù)。redisDb.expires 保存著每一個鍵的過期時間。
2、當redis 服務器初始化時，會預先分配 16 個數(shù)據(jù)庫（該數(shù)量可以通過配置文件配置），所有數(shù)據(jù)庫保存到結(jié)構(gòu) redisServer 的一個成員 redisServer.db 數(shù)組中。當我們選擇數(shù)據(jù)庫 select number 時，程序直接通過 redisServer.db[number] 來切換數(shù)據(jù)庫。有時候當程序需要知道自己是在哪個數(shù)據(jù)庫時，直接讀取 redisDb.id 即可。
3、既然我們知道一個數(shù)據(jù)庫的所有鍵值都存儲在redisDb.dict中，那么我們要知道如果找到key的位置，就有必要了解一下dict 的結(jié)構(gòu)了：

復制代碼代碼如下:

typedef struct dict {

// 特定于類型的處理函數(shù)
dictType *type;

// 類型處理函數(shù)的私有數(shù)據(jù)
void *privdata;

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

// 記錄 rehash 進度的標志，值為-1 表示 rehash 未進行
int rehashidx;

// 當前正在運作的安全迭代器數(shù)量
int iterators;
} dict;

由上述的結(jié)構(gòu)可以看出，redis 的字典使用哈希表作為其底層實現(xiàn)。dict 類型使用的兩個指向哈希表的指針，其中 0 號哈希表（ht[0]）主要用于存儲數(shù)據(jù)庫的所有鍵值，而1號哈希表主要用于程序?qū)?0 號哈希表進行 rehash 時使用，rehash 一般是在添加新值時會觸發(fā)，這里不做過多的贅述。所以redis 中查找一個key，其實就是對進行該dict 結(jié)構(gòu)中的 ht[0] 進行查找操作。
4、既然是哈希，那么我們知道就會有哈希碰撞，那么當多個鍵哈希之后為同一個值怎么辦呢？redis采取鏈表的方式來存儲多個哈希碰撞的鍵。也就是說，當根據(jù)key的哈希值找到該列表后，如果列表的長度大于1，那么我們需要遍歷該鏈表來找到我們所查找的key。當然，一般情況下鏈表長度都為是1，所以時間復雜度可看作o(1)。
二、當redis 拿到一個key 時，如果找到該key的位置。
了解了上述知識之后，我們就可以來分析redis如果在內(nèi)存找到一個key了。
1、當拿到一個key后， redis 先判斷當前庫的0號哈希表是否為空，即：if (dict->ht[0].size == 0)。如果為true直接返回NULL。
2、判斷該0號哈希表是否需要rehash，因為如果在進行rehash，那么兩個表中者有可能存儲該key。如果正在進行rehash，將調(diào)用一次_dictRehashStep方法，_dictRehashStep 用于對數(shù)據(jù)庫字典、以及哈希鍵的字典進行被動 rehash，這里不作贅述。
3、計算哈希表，根據(jù)當前字典與key進行哈希值的計算。
4、根據(jù)哈希值與當前字典計算哈希表的索引值。
5、根據(jù)索引值在哈希表中取出鏈表，遍歷該鏈表找到key的位置。一般情況，該鏈表長度為1。
6、當 ht[0] 查找完了之后，再進行了次rehash判斷，如果未在rehashing，則直接結(jié)束，否則對ht[1]重復345步驟。
到此我們就找到了key在內(nèi)存的中位置了。

上一篇：Redis和Memcache的區(qū)別總結(jié)

下一篇：返回列表