數據庫查找key在內存中的位置的方法

數據庫查找key在內存中的位置的方法

　　一、預先需要了解的知識

　　1、redis 中的每一個(gè)數據庫，都由一個(gè) redisDb 的結構存儲。其中，redisDb.id 存儲著(zhù) redis 數據庫以整數表示的號碼。redisDb.dict 存儲著(zhù)該庫所有的鍵值對數據。redisDb.expires 保存著(zhù)每一個(gè)鍵的過(guò)期時(shí)間。

　　2、當redis 服務(wù)器初始化時(shí)，會(huì )預先分配 16 個(gè)數據庫（該數量可以通過(guò)配置文件配置），所有數據庫保存到結構 redisServer 的一個(gè)成員 redisServer.db 數組中。當我們選擇數據庫 select number 時(shí)，程序直接通過(guò) redisServer.db[number] 來(lái)切換數據庫。有時(shí)候當程序需要知道自己是在哪個(gè)數據庫時(shí)，直接讀取 redisDb.id 即可。

　　3、既然我們知道一個(gè)數據庫的所有鍵值都存儲在redisDb.dict中，那么我們要知道如果找到key的位置，就有必要了解一下dict 的結構了：

　　復制代碼 代碼如下:typedef struct dict {

　　// 特定于類(lèi)型的處理函數

　　dictType *type;

　　// 類(lèi)型處理函數的私有數據

　　void *privdata;

　　// 哈希表（2個(gè)）

　　dictht ht[2];

　　// 記錄 rehash 進(jìn)度的標志，值為-1 表示 rehash 未進(jìn)行

　　int rehashidx;

　　// 當前正在運作的安全迭代器數量

　　int iterators;

　　} dict;

　　由上述的結構可以看出，redis 的字典使用哈希表作為其底層實(shí)現。dict 類(lèi)型使用的兩個(gè)指向哈希表的指針，其中 0 號哈希表（ht[0]）主要用于存儲數據庫的所有鍵值，而1號哈希表主要用于程序對 0 號哈希表進(jìn)行 rehash 時(shí)使用，rehash 一般是在添加新值時(shí)會(huì )觸發(fā)，這里不做過(guò)多的贅述。所以redis 中查找一個(gè)key，其實(shí)就是對進(jìn)行該dict 結構中的 ht[0] 進(jìn)行查找操作。

　　4、既然是哈希，那么我們知道就會(huì )有哈希碰撞，那么當多個(gè)鍵哈希之后為同一個(gè)值怎么辦呢？redis采取鏈表的方式來(lái)存儲多個(gè)哈希碰撞的鍵。也就是說(shuō)，當根據key的哈希值找到該列表后，如果列表的長(cháng)度大于1，那么我們需要遍歷該鏈表來(lái)找到我們所查找的key。當然，一般情況下鏈表長(cháng)度都為是1，所以時(shí)間復雜度可看作o(1)。

　　二、當redis 拿到一個(gè)key 時(shí)，如果找到該key的位置。

　　了解了上述知識之后，我們就可以來(lái)分析redis如果在內存找到一個(gè)key了。

　　1、當拿到一個(gè)key后， redis 先判斷當前庫的0號哈希表是否為空，即：if (dict->ht[0].size == 0)。如果為true直接返回NULL。

　　2、判斷該0號哈希表是否需要rehash，因為如果在進(jìn)行rehash，那么兩個(gè)表中者有可能存儲該key。如果正在進(jìn)行rehash，將調用一次_dictRehashStep方法，_dictRehashStep 用于對數據庫字典、以及哈希鍵的字典進(jìn)行被動(dòng) rehash，這里不作贅述。

　　3、計算哈希表，根據當前字典與key進(jìn)行哈希值的計算。

　　4、根據哈希值與當前字典計算哈希表的索引值。

　　5、根據索引值在哈希表中取出鏈表，遍歷該鏈表找到key的位置。一般情況，該鏈表長(cháng)度為1。

　　6、當 ht[0] 查找完了之后，再進(jìn)行了次rehash判斷，如果未在rehashing，則直接結束，否則對ht[1]重復345步驟。

　　到此我們就找到了key在內存的中位置了。