Redis中數(shù)據(jù)結(jié)構(gòu)是什么

這篇文章主要介紹了Redis中數(shù)據(jù)結(jié)構(gòu)是什么，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

在實(shí)際開發(fā)，Redis使用會(huì)頻繁，那么在使用過程中我們?cè)撊绾握_抉擇數(shù)據(jù)類型呢？哪些場(chǎng)景下適用哪些數(shù)據(jù)類型。而且在面試中也很常會(huì)被面試官問到Redis數(shù)據(jù)結(jié)構(gòu)方面的問題：

• Redis為什么快呢？

• 為什么查詢操作會(huì)變慢了？

• Redis Hash rehash過程

• 為什么使用哈希表作為Redis的索引

當(dāng)我們分析理解了Redis數(shù)據(jù)結(jié)構(gòu)，可以為了我們?cè)谑褂?code>Redis的時(shí)候，正確抉擇數(shù)據(jù)類型使用，提升系統(tǒng)性能?！鞠嚓P(guān)推薦：Redis視頻教程】

Redis底層數(shù)據(jù)結(jié)構(gòu)

Redis 是一個(gè)內(nèi)存鍵值key-value 數(shù)據(jù)庫(kù)，且鍵值對(duì)數(shù)據(jù)保存在內(nèi)存中，因此Redis基于內(nèi)存的數(shù)據(jù)操作，其效率高，速度快；

其中，Key是String類型，Redis 支持的 value 類型包括了 String、List 、 Hash 、 Set 、 Sorted Set 、BitMap等。Redis 能夠之所以能夠廣泛地適用眾多的業(yè)務(wù)場(chǎng)景，基于其多樣化類型的value。

而Redis的Value的數(shù)據(jù)類型是基于為Redis自定義的對(duì)象系統(tǒng)redisObject實(shí)現(xiàn)的，

typedef struct redisObject{
    //類型
    unsigned type:4;
    //編碼
    unsigned encoding:4;
    //指向底層實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的指針
    void *ptr;
    ….. 
}

redisObject除了記錄實(shí)際數(shù)據(jù)，還需要額外的內(nèi)存空間記錄數(shù)據(jù)長(zhǎng)度、空間使用等元數(shù)據(jù)信息，其中包含了 8 字節(jié)的元數(shù)據(jù)和一個(gè) 8 字節(jié)指針，指針指向具體數(shù)據(jù)類型的實(shí)際數(shù)據(jù)所在位置：

其中，指針指向的就是基于Redis的底層數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)數(shù)據(jù)的位置，Redis的底層數(shù)據(jù)結(jié)構(gòu)：SDS，雙向鏈表、跳表，哈希表，壓縮列表、整數(shù)集合實(shí)現(xiàn)的。

那么Redis底層數(shù)據(jù)結(jié)構(gòu)是怎么實(shí)現(xiàn)的呢？

Redis底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)

我們先來看看Redis比較簡(jiǎn)單的SDS,雙向鏈表，整數(shù)集合。

SDS、雙向鏈表和整數(shù)集合

SDS，使用len字段記錄已使用的字節(jié)數(shù)，將獲取字符串長(zhǎng)度復(fù)雜度降低為O(1)，而且SDS是惰性釋放空間的，你free了空間，系統(tǒng)把數(shù)據(jù)記錄下來下次想用時(shí)候可直接使用。不用新申請(qǐng)空間。

整數(shù)集合，在內(nèi)存中分配一塊地址連續(xù)的空間，數(shù)據(jù)元素會(huì)挨著存放，不需要額外指針帶來空間開銷，其特點(diǎn)為內(nèi)存緊湊節(jié)省內(nèi)存空間，查詢復(fù)雜度為O(1)效率高，其他操作復(fù)雜度為O(N)；

雙向鏈表， 在內(nèi)存上可以為非連續(xù)、非順序空間，通過額外的指針開銷前驅(qū)/后驅(qū)指針串聯(lián)元素之間的順序。

其特點(diǎn)為節(jié)插入/更新數(shù)據(jù)復(fù)雜度為O(1)效率高，查詢復(fù)雜度為O(N)；

Hash哈希表

哈希表，其實(shí)類似是一個(gè)數(shù)組，數(shù)組的每個(gè)元素稱為一個(gè)哈希桶，每個(gè)哈希桶中保存了鍵值對(duì)數(shù)據(jù)，且哈希桶中的元素使用dictEntry結(jié)構(gòu)，

因此，哈希桶元素保存的并不是鍵值對(duì)值本身，而是指向具體值的指針，所以在保存每個(gè)鍵值對(duì)的時(shí)候會(huì)額外空間開銷，至少有增加24個(gè)字節(jié)，特別是Value為String的鍵值對(duì)，每一個(gè)鍵值對(duì)就需要額外開銷24個(gè)字節(jié)空間。當(dāng)保存數(shù)據(jù)小，額外開銷比數(shù)據(jù)還大時(shí)，這時(shí)為了節(jié)省空間，考慮換數(shù)據(jù)結(jié)構(gòu)。

那來看看全局哈希表全圖：

雖然哈希表操作很快，但Redis數(shù)據(jù)變大后，就會(huì)出現(xiàn)一個(gè)潛在的風(fēng)險(xiǎn)：哈希表的沖突問題和 rehash開銷問題，這可以解釋為什么哈希表操作變慢了？

當(dāng)往哈希表中寫入更多數(shù)據(jù)時(shí)，哈希沖突是不可避免的問題 ， Redis 解決哈希沖突的方式，就是鏈?zhǔn)焦?/strong>，同一個(gè)哈希桶中的多個(gè)元素用一個(gè)鏈表來保存，它們之間依次用指針連接，如圖所示：

當(dāng)哈希沖突也會(huì)越來越多，這就會(huì)導(dǎo)致某些哈希沖突鏈過長(zhǎng)，進(jìn)而導(dǎo)致這個(gè)鏈上的元素查找耗時(shí)長(zhǎng)，效率降低。

為了解決哈希沖突帶了的鏈過長(zhǎng)的問題，進(jìn)行rehash操作，增加現(xiàn)有的哈希桶數(shù)量，分散單桶元素?cái)?shù)量。那么rehash過程怎么樣執(zhí)行的呢？

Rehash

為了使rehash 操作更高效，使用兩個(gè)全局哈希表：哈希表 1 和哈希表 2，具體如下：

• 將哈希表 2 分配更大的空間，

• 把哈希表 1 中的數(shù)據(jù)重新映射并拷貝到哈希表 2 中；

• 釋放哈希表 1 的空間

但由于表1和表2在重新映射復(fù)制時(shí)數(shù)據(jù)大，如果一次性把哈希表 1 中的數(shù)據(jù)都遷移完，會(huì)造成 Redis 線程阻塞，無(wú)法服務(wù)其他請(qǐng)求。

為了避免這個(gè)問題，保證Redis能正常處理客戶端請(qǐng)求，Redis 采用了漸進(jìn)式 rehash。

每處理一個(gè)請(qǐng)求時(shí)，從哈希表 1 中依次將索引位置上的所有 entries 拷貝到哈希表 2 中，把一次性大量拷貝的開銷，分?jǐn)偟搅硕啻翁幚碚?qǐng)求的過程中，避免了耗時(shí)操作，保證了數(shù)據(jù)的快速訪問。

在理解完Hash哈希表相關(guān)知識(shí)點(diǎn)后，看看不常見的壓縮列表和跳表。

壓縮列表與跳表

壓縮列表，在數(shù)組基礎(chǔ)上，在壓縮列表在表頭有三個(gè)字段 zlbytes、zltail 和 zllen，分別表示列表長(zhǎng)度、列表尾的偏移量和列表中的 entry 個(gè)數(shù)；壓縮列表在表尾還有一個(gè) zlend，表示列表結(jié)束。

優(yōu)點(diǎn)：內(nèi)存緊湊節(jié)省內(nèi)存空間，內(nèi)存中分配一塊地址連續(xù)的空間，數(shù)據(jù)元素會(huì)挨著存放，不需要額外指針帶來空間開銷；查找定位第一個(gè)元素和最后一個(gè)元素，可以通過表頭三個(gè)字段的長(zhǎng)度直接定位，復(fù)雜度是 O(1)。

跳表 ，在鏈表的基礎(chǔ)上，增加了多級(jí)索引，通過索引位置的幾個(gè)跳轉(zhuǎn)，實(shí)現(xiàn)數(shù)據(jù)的快速定位，如下圖所示：

比如查詢33

特點(diǎn)：當(dāng)數(shù)據(jù)量很大時(shí)，跳表的查找復(fù)雜度為O(logN)。

綜上所述，可以得知底層數(shù)據(jù)結(jié)構(gòu)的時(shí)間復(fù)雜度：

Redis自定義的對(duì)象系統(tǒng)類型即為Redis的Value的數(shù)據(jù)類型，Redis的數(shù)據(jù)類型是基于底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，那數(shù)據(jù)類型有哪些呢？

Redis數(shù)據(jù)類型

String、List、Hash、Sorted Set、Set比較常見的類型，其與底層數(shù)據(jù)結(jié)構(gòu)對(duì)應(yīng)關(guān)系如下：

數(shù)據(jù)類型對(duì)應(yīng)特點(diǎn)跟其實(shí)現(xiàn)的底層數(shù)據(jù)結(jié)構(gòu)差不多，性質(zhì)也是一樣的,且

String，基于SDS實(shí)現(xiàn)，適用于簡(jiǎn)單key-value存儲(chǔ)、setnx key value實(shí)現(xiàn)分布式鎖、計(jì)數(shù)器(原子性)、分布式全局唯一ID。

List， 按照元素進(jìn)入List 的順序進(jìn)行排序的，遵循FIFO(先進(jìn)先出)規(guī)則，一般使用在 排序統(tǒng)計(jì)以及簡(jiǎn)單的消息隊(duì)列。

Hash， 是字符串key和字符串value之間的映射，十分適合用來表示一個(gè)對(duì)象信息 ，特點(diǎn)添加和刪除操作復(fù)雜度都是O(1)。

Set，是String 類型元素的無(wú)序集合，集合成員是唯一的，這就意味著集合中不能出現(xiàn)重復(fù)的數(shù)據(jù)。 基于哈希表實(shí)現(xiàn)的，所以添加，刪除，查找的復(fù)雜度都是 O(1)。

Sorted Set，  是Set的類型的升級(jí)， 不同的是每個(gè)元素都會(huì)關(guān)聯(lián)一個(gè) double 類型的分?jǐn)?shù)，通過分?jǐn)?shù)排序，可以范圍查詢。

那我們?cè)賮砜纯催@些數(shù)據(jù)類型，Redis Geo、HyperLogLog、BitMap？

Redis Geo， 將地球看作為近似為球體，基于GeoHash 將二維的經(jīng)緯度轉(zhuǎn)換成字符串，來實(shí)現(xiàn)位置的劃分跟指定距離的查詢。特點(diǎn)一般使用在跟位置有關(guān)的應(yīng)用。

HyperLogLog， 是一種概率數(shù)據(jù)結(jié)構(gòu)，它使用概率算法來統(tǒng)計(jì)集合的近似基數(shù) ， 錯(cuò)誤率大概在0.81%。 當(dāng)集合元素?cái)?shù)量非常多時(shí)，它計(jì)算基數(shù)所需的空間總是固定的，而且還很小，適合使用做 UV 統(tǒng)計(jì)。

BitMap ，用一個(gè)比特位來映射某個(gè)元素的狀態(tài)， 只有 0 和 1 兩種狀態(tài)，非常典型的二值狀態(tài)，且其本身是用 String 類型作為底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的一種統(tǒng)計(jì)二值狀態(tài)的數(shù)據(jù)類型  ，優(yōu)勢(shì)大量節(jié)省內(nèi)存空間，可是使用在二值統(tǒng)計(jì)場(chǎng)景。

在理解上述知識(shí)后，我們接下來討論一下根據(jù)哪些策略選擇相對(duì)應(yīng)的應(yīng)用場(chǎng)景下的Redis數(shù)據(jù)類型？

選擇合適的Redis數(shù)據(jù)類型策略

在實(shí)際開發(fā)應(yīng)用中，Redis可以適用于眾多的業(yè)務(wù)場(chǎng)景，但我們需要怎么選擇數(shù)據(jù)類型存儲(chǔ)呢？

主要依據(jù)就是時(shí)間/空間復(fù)雜度，在實(shí)際的開發(fā)中可以考慮以下幾個(gè)點(diǎn)：

• 數(shù)據(jù)量，數(shù)據(jù)本身大小

• 集合類型統(tǒng)計(jì)模式

• 支持單點(diǎn)查詢/范圍查詢

• 特殊使用場(chǎng)景

數(shù)據(jù)量，數(shù)據(jù)本身大小

當(dāng)數(shù)據(jù)量比較大，數(shù)據(jù)本身比較小，使用String就會(huì)使用額外的空間大大增加，因?yàn)槭褂霉１肀４骀I值對(duì)，使用dictEntry結(jié)構(gòu)保存，會(huì)導(dǎo)致保存每個(gè)鍵值對(duì)時(shí)額外保存dictEntry的三個(gè)指針的開銷，這樣就會(huì)導(dǎo)致數(shù)據(jù)本身小于額外空間開銷，最終會(huì)導(dǎo)致存儲(chǔ)空間數(shù)據(jù)大小遠(yuǎn)大于原本數(shù)據(jù)存儲(chǔ)大小。

可以使用基于整數(shù)數(shù)組和壓縮列表實(shí)現(xiàn)了 List、Hash 和 Sorted Set ，因?yàn)?strong>整數(shù)數(shù)組和壓縮列表在內(nèi)存中都是分配一塊地址連續(xù)的空間，然后把集合中的元素一個(gè)接一個(gè)地放在這塊空間內(nèi)，非常緊湊，不用再通過額外的指針把元素串接起來，這就避免了額外指針帶來的空間開銷。而且采用集合類型時(shí)，一個(gè) key 就對(duì)應(yīng)一個(gè)集合的數(shù)據(jù)，能保存的數(shù)據(jù)多了很多，但也只用了一個(gè) dictEntry，這樣就節(jié)省了內(nèi)存。

集合類型統(tǒng)計(jì)模式

Redis集合類型統(tǒng)計(jì)模式常見的有：

• 聚合統(tǒng)計(jì)（ 交集、差集、并集統(tǒng)計(jì) ）：  對(duì)多個(gè)集合進(jìn)行聚合計(jì)算時(shí)，可以選擇Set；

• 排序統(tǒng)計(jì)（要求集合類型能對(duì)元素保序）： Redis中List 和 Sorted Set是有序集合，List是按照元素進(jìn)入 List 的順序進(jìn)行排序的，Sorted Set 可以根據(jù)元素的權(quán)重來排序；

• 二值狀態(tài)統(tǒng)計(jì)（ 集合元素的取值就只有 0 和 1 兩種 ）：Bitmap 本身是用 String 類型作為底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的一種統(tǒng)計(jì)二值狀態(tài)的數(shù)據(jù)類型 ， Bitmap通過 BITOP 按位 與、或、異或的操作后使用 BITCOUNT 統(tǒng)計(jì) 1 的個(gè)數(shù)。

• 基數(shù)統(tǒng)計(jì)（ 統(tǒng)計(jì)一個(gè)集合中不重復(fù)的元素的個(gè)數(shù) ）：HyperLogLog 是一種用于統(tǒng)計(jì)基數(shù)的數(shù)據(jù)集合類型 ，統(tǒng)計(jì)結(jié)果是有一定誤差的，標(biāo)準(zhǔn)誤算率是 0.81% 。需要精確統(tǒng)計(jì)結(jié)果的話，用 Set 或 Hash 類型。

Set類型，適用統(tǒng)計(jì)用戶/好友/關(guān)注/粉絲/感興趣的人集合聚合操作，比如

• 統(tǒng)計(jì)手機(jī)APP每天的新增用戶數(shù)

• 兩個(gè)用戶的共同好友

Redis中List 和 Sorted Set是有序集合，使用應(yīng)對(duì)集合元素排序需求 ，比如

• 最新評(píng)論列表

• 排行榜

Bitmap二值狀態(tài)統(tǒng)計(jì)，適用數(shù)據(jù)量大，且可以使用二值狀態(tài)表示的統(tǒng)計(jì)，比如：

• 簽到打卡，當(dāng)天用戶簽到數(shù)

• 用戶周活躍

• 用戶在線狀態(tài)

HyperLogLog 是一種用于統(tǒng)計(jì)基數(shù)的數(shù)據(jù)集合類型， 統(tǒng)計(jì)一個(gè)集合中不重復(fù)的元素個(gè)數(shù) ，比如

• 統(tǒng)計(jì)網(wǎng)頁(yè)的 UV ， 一個(gè)用戶一天內(nèi)的多次訪問只能算作一次

支持單點(diǎn)查詢/范圍查詢

Redis中List 和 Sorted Set是有序集合支持范圍查詢，但是Hash是不支持范圍查詢的

特殊使用場(chǎng)景

消息隊(duì)列，使用Redis作為消息隊(duì)列的實(shí)現(xiàn)，要消息的基本要求消息保序、處理重復(fù)的消息和保證消息可靠性，方案有如下：

• 基于 List 的消息隊(duì)列解決方案

• 基于 Streams 的消息隊(duì)列解決方案

基于位置 LBS 服務(wù)，使用Redis的特定GEO數(shù)據(jù)類型實(shí)現(xiàn)，GEO 可以記錄經(jīng)緯度形式的地理位置信息，被廣泛地應(yīng)用在 LBS 服務(wù)中。  比如:打車軟件是怎么基于位置提供服務(wù)的。

Redis之所以那么快，是因?yàn)槠浠趦?nèi)存的數(shù)據(jù)操作和使用Hash哈希表作為索引，其效率高，速度快，而且得益于其底層數(shù)據(jù)多樣化使得其可以適用于眾多場(chǎng)景，不同場(chǎng)景中選擇合適的數(shù)據(jù)類型可以提升其查詢性能。

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“Redis中數(shù)據(jù)結(jié)構(gòu)是什么”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來學(xué)習(xí)!