Redis 哈希Hash底層數據結構

1. Redis 底層數據結構

Redis資料庫就像是一個哈希表,首先對key進行哈希運算得到哈希值再取模得到一個下標,每個元素是一個節點,節點之間形成鏈表。這感覺有點像Java中的HashMap。

不同的數據類型的實現方式是不一樣的,可以通過object encoding命令查看底層真正的數據存儲結構

同一種類型在不同的條件下所採用的數據結構也不一樣,例如:

Redis是鍵值對形式的資料庫,key可以是任意值(PS:最終都會轉成string),value有多種數據類型

詳見://redis.io/docs/manual/data-types/data-types-tutorial/

至此,已經很清楚,hash底層的結構是 ziplist 和 hashtable

那麼,什麼時候會從ziplist轉成hashtable呢?這個在redis.conf中有相關的配置,如下:

默認情況下:

  1. 當ziplist中entry的數量超過512的時候,會轉成hashtable
  2. 單個元素的值超過64位元組的時候,會轉成hashtable

2. hashtable

在Redis中hashtable就是字典dict

通過源碼,可以看到dict是這樣定義的:

3. redisDb 與 redisObject

通過源碼得知,redisDb代表redis資料庫,redisObject代表存到資料庫中的數據

字典dict的結構前面已經看過了,於是整個資料庫的結構大概就是下面這個樣子:

4. ziplist

ziplist是一種特殊編碼的雙鏈表,被設計成非常節省記憶體。它存儲字元串和整型值,其中整數被編碼為實際整數,而不是一系列字元。它允許在O(1)時間內在列表的任意一邊進行push和pop操作。但是,由於每個操作都需要重新分配ziplist所使用的記憶體,因此實際的複雜性與ziplist所使用的記憶體量有關。

ziplist的大體布局如下:

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

<uint32_t zlbytes>: 一個無符號整數,用於保存ziplist佔用的位元組數,包括zlbytes欄位本身的四個位元組。需要存儲這個值,以便能夠調整整個結構的大小,而不需要首先遍歷它。
<uint32_t zltail> : 列表中最後一個條目的偏移量。
<uint16_t zllen>  : 條目的數量。當有超過2^16-2個條目時,這個值被設置為2^16-1,我們需要遍歷整個列表來知道它包含多少項。
<uint8_t zlend> : 一個特殊的條目,表示 ziplist 的結尾

5. linkedlist

linkedlist是一個雙向鏈表

6. quicklist

quicklist = linkedlist + ziplist

7. 參考

//redisbook.com/index.html

//blog.itpub.net/70000430/viewspace-2787985/

//www.cnblogs.com/reecelin/p/13358432.html

//juejin.cn/post/6844904008591605767

Tags: