Redis中的數據結構與內部編碼

? 本篇文章主要是對 Redis 常見的數據結構進行講解，同時還對其所對應的不同的內部編碼進行講解。希望本篇文章會對你有所幫助。

文章目錄

一、五大數據結構

二、數據結構對應的編碼方式

String

hash

list

set

zset

🙋?♂??作者：@Ggggggtm?🙋?♂?

👀?專欄：Redis 👀

💥?標題：Redis中的數據結構與內部編碼 💥

????寄語：與其忙著訴苦，不如低頭趕路，奮路前行，終將遇到一番好風景???

? 我們知道，redis是支持不同的數據類型的，而不同的數據類型底層所采用的數據結構也有所差異，同時不同的數據結構也會有不同的操作指令。我們這里所說的不同的數據類型都是指的value的類型，而key的類型固定是string的。上篇文章講解到的type指令，其返回值是key所對應的value的數據類型！

一、五大數據結構

? ?Redis的鍵值對中，value所用到的五種主要的數據結構，它們分別是：

String（字符串）：最基本的類型，可以包含任何形式的數據，比如一個文本、JSON字符串或者二進制數據。

List（列表）：一個有序的字符串列表，元素的順序由插入順序決定，可以在兩端進行插入和刪除操作。

Set（集合）：一個不重復且無序的字符串集合，可對集合中的元素進行添加、刪除和判斷某個元素是否存在的操作。

Hash（哈希表）：類似于關聯數組，包含字段和與其對應的值，常用于存儲對象。

Zset（有序集合）：類似于集合，但每個元素都關聯一個分數，可以按照分數進行排序，適合構建排行榜等功能。

? 具體可看下圖：

??

? Redis 底層在實現上述數據結構的時候，會在源碼層面針對上述實現進行特定的優化，來達到節省時間或者節省空間的效果。簡單來說，數據結構的內部具體實現不是固定統一的，會根據不同的情況，redis會自動適配合適的數據結構。但是每個數據結構的底層實現有固定的幾種方式。

? 舉個例子，redis承諾現在我這有個hash表，你進行查詢、插入、刪除操作都保證O(1)的書簡復雜度。但是這個背后的實現，不一定就是一個標準的hash表。可能再特定場景下，使用別的數據結構實現。但是仍然保證時間復雜度符合承諾。

? 那么哦我們現在就會有兩個大致方向上的理解：

數據結構是指redis 承諾給你的。也可以理解成數據類型；
編碼方式是redis內部底層的實現；
一個數據結構有對應固定的編碼方式。

二、數據結構對應的編碼方式

? 實際上每種數據結構都有自己底層的內部編碼實現，而且是多種實現。這樣 Redis 會在合適的場景選擇合適的內部編碼。具體數據結構所對應的編碼方式如下：

數據結構內部編碼
string 1.raw
2.embstr
3.int
hash 1.hashtable
2.ziplist
list 1.linkedlist
2.ziplist
set 1.hashtable
2.intset
zset 1.skiplist
2.ziplist

? 下面我們來詳細解釋一下不同的內部編碼。

數據結構	內部編碼
string	1.raw 2.embstr 3.int
hash	1.hashtable 2.ziplist
list	1.linkedlist 2.ziplist
set	1.hashtable 2.intset
zset	1.skiplist 2.ziplist

String

? Redis中 String 的內部編碼有三種：int、raw、embstr。

int編碼

當字符串可以被解釋為整數時，Redis會將該字符串以int編碼進行存儲，節省內存空間。
int編碼使用64位有符號整數來表示，其范圍為-2^63到2^63-1。
當字符串的值處于int編碼的范圍內時，Redis會使用int編碼來存儲，這樣可以減少內存占用并提高性能。

raw編碼

當字符串無法被解釋為整數時，Redis會以raw編碼進行存儲。
raw編碼使用簡單動態字符串（SDS）來表示，SDS是一種帶有緩沖區的字符串表示形式，可以動態擴展和收縮，適用于存儲任意長度的字符串數據。
raw編碼適用于存儲包含非整數數據的字符串，如文本、JSON、XML等。

embstr編碼

embstr是一種特殊的內部編碼方式，用于存儲長度較短的字符串。
當字符串長度在一定范圍內（默認為39字節）時，Redis會使用embstr編碼來存儲，以進一步減少內存開銷。
embstr編碼實際上將字符串值和其他元數據一起存儲在一個連續的內存塊中，節省了額外指針和分配內存的開銷。

? SDS動態字符串可參考文章：Redis(設計與實現):01---數據結構之SDS動態字符串（raw、embstr、int、struct sdshdr）_sds類型的int與raw查詢速度的區別

hash

??Redis 中的 Hash 類型可以使用兩種內部編碼方式：hashtable 和 ziplist。

Hashtable：

Hashtable 是 Redis 中 Hash 類型的默認內部編碼方式。
當 Hash 中包含的鍵值對數量較多，或者鍵值對的值較大時，Redis 會自動將 Hash 內部編碼為 Hashtable。
Hashtable 使用哈希表來存儲鍵值對，可以快速進行數據查找，適合處理大規模的數據。

Ziplist：

Ziplist 是一種緊湊的數據結構，適合存儲小規模的數據。
當 Hash 中包含的鍵值對數量較少，且每個鍵值對的鍵和值的長度都較小時，Redis 會選擇使用 Ziplist 進行內部編碼。
Ziplist 使用一段連續的內存空間來存儲鍵值對，節約了內存的使用，但查找效率沒有哈希表高。
由于元素過少，通過遍歷，時間復雜度還是可以認為是 O(1)

? 總結來說，當 Hash 數據較大或者鍵值對較復雜時，Redis 會使用 Hashtable 進行內部編碼以獲得更好的性能；而當 Hash 數據較小且簡單時，Redis 會選擇使用 Ziplist 進行內部編碼以節約內存空間。

? 具體底層實現細節可參考文章：Redis(設計與實現):06---數據結構之壓縮列表（ziplist、struct ziplist）_4位長,介于0至12之間的無符號整數Redis(設計與實現):03---數據結構之字典（hashtable、struct dictht、struct dictEntry、struct dict）-CSDN博客

list

? 在 Redis 中，List 類型可以使用三種不同的內部編碼方式：linkedlist、ziplist 和 quicklist。

Linkedlist（雙向鏈表）：

linkedlist 內部編碼主要適用于 List 包含的元素數量較多，或者元素的大小較大的情況。它通過指針將元素連接在一起，支持快速的插入和刪除操作，適合處理大規模的數據。

Ziplist（壓縮列表）：

ziplist 內部編碼適用于 List 包含的元素數量較少，且每個元素的大小都比較小時。Ziplist 使用緊湊的數據結構來存儲元素，節約了內存的使用，但查找和修改操作的效率沒有 linkedlist 高。

Quicklist（快速列表）：

quicklist 是 Redis 為了優化 List 類型而引入的一種內部編碼方式。它實際上是將多個 ziplist 連接在一起形成的一個雙向鏈表結構。quicklist 既具備了 ziplist 節約內存空間的優點，又能夠快速地處理大規模的數據，同時還兼顧了快速的插入和刪除操作。

? 綜上所述，Redis 根據 List 中元素的數量和大小來選擇合適的內部編碼方式：linkedlist 適用于大規模數據的場景，ziplist 適用于節約內存的場景，而 quicklist 則是為了兼顧以上兩種場景而設計的一種高效內部編碼方式。大部分場景下都是使用的quicklist。

set

??在 Redis 中，Set 類型可以使用兩種不同的內部編碼方式：hashtable 和 intset。

Hashtable（哈希表）：

當 Set 中的元素數量較多，或者元素較長時，Redis 會選擇使用 hashtable 內部編碼。這種編碼方式使用了哈希表結構來存儲元素，它提供了較快的查找、插入和刪除操作，適用于處理較大規模的數據。

Intset（整數集合）：

當 Set 中的所有元素都是整數，并且數量較少時，Redis 會選擇使用 intset 內部編碼。intset 使用緊湊的數組結構來存儲整數元素，節省了內存空間的使用，并且提供了高效的操作，適用于存儲小規模的整數數據集。

? 在實際使用中，Redis 根據 Set 的特點（元素數量、元素類型等）來動態地選擇合適的內部編碼方式，以提高性能和節約內存空間。通過使用合適的內部編碼方式，Redis 能夠更好地滿足不同場景下對 Set 數據類型的需求。

? intset底層實現可參考文章：Redis(設計與實現):04---數據結構之整數集合（intset、struct intset）

zset

??在 Redis 中，有序集合（Sorted Set）類型可以使用兩種不同的內部編碼方式：skiplist 和 ziplist。

Skiplist（跳躍表）：

當有序集合中的成員數量較多或者成員較長時，Redis 會選擇使用 skiplist 內部編碼。跳躍表是一種基于鏈表的數據結構，它可以提供快速的插入、刪除和查找操作。
Skiplist 編碼方式適用于處理較大規模的有序集合數據，因為它能夠保持較高的性能并且具有良好的平衡性能。

Ziplist（壓縮列表）：

當有序集合中的成員數量較少且每個成員都比較短小精悍時，Redis 會選擇使用 ziplist 內部編碼。壓縮列表是一種緊湊的數據結構，可以節省內存空間，適用于存儲較小規模的有序集合數據。
Ziplist 內部編碼方式對于小型的有序集合數據具有較好的存儲效率和操作性能。

? 根據有序集合的實際情況，Redis 會動態地選擇合適的內部編碼方式，以便在不同場景下提供最佳的性能和內存利用率。

? skiplist底層實現原理可參考文章：Redis(設計與實現):05---數據結構之跳躍表（skiplist、struct zskiplistNode、struct zskiplist）_skiplist和zskiplistnode

? 可以看到每種數據結構都有至少兩種以上的內部編碼實現，例如list數據結構包含了linkedlist和ziplist 兩種內部編碼。同時有些內部編碼，例如ziplist，可以作為多種數據結構的內部實現，可以通過object encoding命令查詢內部編碼：

? ?Redis這樣設計有兩個好處：

可以改進內部編碼，而對外的數據結構和命令沒有任何影響，這樣一旦開發出更優秀的內部編碼，無需改動外部數據結構和命令，例如Redis 3.2提供了quicklist，結合了ziplist和linkedlist兩者的優勢，為列表類型提供了一種更為優秀的內部編碼實現，而對用戶來說基本無感知。
多種內部編碼實現可以在不同場景下發揮各自的優勢，例如ziplist 比較節省內存，但是在列表元素比較多的情況下，性能會下降，這時候Redis 會根據配置選項將列表類型的內部實現轉換為linkedlist，整個過程用戶同樣無感知。