快捷導(dǎo)航

redis的底層數(shù)據(jù)結(jié)構(gòu)詳解

更新時(shí)間：2025年02月19日 11:23:47 作者：nodelaynow

Redis性能高得益于其優(yōu)化的數(shù)據(jù)結(jié)構(gòu),Redis的數(shù)據(jù)結(jié)構(gòu)分為對(duì)外暴露的和內(nèi)部底層的兩種,對(duì)外暴露的數(shù)據(jù)結(jié)構(gòu)包括String、list、hash、set、zset等,而內(nèi)部底層的數(shù)據(jù)結(jié)構(gòu)則包括SDS、hashtable、ziplist、linkedlist、quicklist、intset、skiplist等

1. redis數(shù)據(jù)結(jié)構(gòu)層次

1.1 外部數(shù)據(jù)結(jié)構(gòu)

對(duì)外暴露的數(shù)據(jù)結(jié)構(gòu)即我們所使用的String，list，hash，set，zset等

1.2 內(nèi)部數(shù)據(jù)結(jié)構(gòu)

redis內(nèi)部有更為精細(xì)的實(shí)現(xiàn)，總的來說有以下幾種：

SDS，hashtable，ziplist，linkedlist，quicklist，intset，skiplist等

2. redis底層實(shí)現(xiàn)

2.1 String字符串類型的底層實(shí)現(xiàn)

字符串類型的底層實(shí)現(xiàn)主要依賴于SDS這種數(shù)據(jù)結(jié)構(gòu)，相較于傳統(tǒng)的C語(yǔ)言所表達(dá)的字符串，SDS內(nèi)部作出改動(dòng)，包含了len(字符串真實(shí)的長(zhǎng)度)，buf[](存放字符串?dāng)?shù)據(jù)的數(shù)組)，alloc(buf數(shù)組所擁有的實(shí)際長(zhǎng)度),flags。

不同字符串長(zhǎng)度會(huì)使用相同結(jié)構(gòu)但不同長(zhǎng)度的SDS數(shù)據(jù)結(jié)構(gòu)（內(nèi)部buf，alloc會(huì)不同），flags就是用來指定你用的是哪一種。

SDS除開長(zhǎng)度所導(dǎo)致的結(jié)構(gòu)不同，具體的編碼模式也會(huì)隨著傳值不同而不同，總的來說分為三種：RAW，EMBSTR，INT(寫作int類型但是實(shí)際上存儲(chǔ)的是long)。

當(dāng)外部傳來一個(gè)值為字符串類型的value時(shí)，redis會(huì)首先使用RAW接收，然后出于節(jié)省內(nèi)存考慮，轉(zhuǎn)化為INT或者EMBSTR類型的編碼方式。

這樣的好處是，當(dāng)我們?cè)噲D對(duì)字符串進(jìn)行increment這種操作時(shí)，int類型會(huì)自動(dòng)直接加1，而str會(huì)試圖轉(zhuǎn)化為int，然后再加1，而當(dāng)我們進(jìn)行append這類操作時(shí)，int類型會(huì)試圖轉(zhuǎn)化為str再執(zhí)行，而str會(huì)直接執(zhí)行，不然編碼方式不同，對(duì)于某些情況下的命令結(jié)果也會(huì)不同

2.2 Hash類型的底層實(shí)現(xiàn)

hash類型的底層實(shí)現(xiàn)主要分為兩種，ziplist和hashtable

ziplist是一塊存放于連續(xù)內(nèi)存的鏈表，基于內(nèi)存連續(xù)，它的讀取效率很高，尋找元素時(shí)直接遍歷，內(nèi)部不存儲(chǔ)前后節(jié)點(diǎn)這類數(shù)據(jù)，但是也正因?yàn)閮?nèi)存連續(xù)，它本身也會(huì)收到一些限制，實(shí)際上ziplist要滿足以下兩種條件才會(huì)被使用

長(zhǎng)度小于512
單個(gè)value小于64字節(jié)

如不滿足，強(qiáng)行使用，會(huì)導(dǎo)致涉及插入修改等發(fā)生的內(nèi)存拷貝成本較大，影響性能。

而不滿足時(shí)，我們會(huì)使用hashtable來實(shí)現(xiàn)，哈希表里面的hash搜索能保證時(shí)間復(fù)雜度接近O(1)，以鏈表數(shù)組的方式解決hash沖突，而當(dāng)哈希表需要進(jìn)行擴(kuò)容時(shí)，為了避免單次擴(kuò)容所導(dǎo)致的響應(yīng)時(shí)間劇烈增加，它將單次擴(kuò)容所需要的重哈希分散到后續(xù)對(duì)哈希表的增刪改查操作里，一步步進(jìn)行hash擴(kuò)容。

2.3 list類型的底層實(shí)現(xiàn)

list類型在redis3.2之前使用ziplist或者linkedlist去實(shí)現(xiàn)，而在3.2之后使用quicklist去實(shí)現(xiàn)。

quicklist是一種結(jié)合了ziplist和linkedlist兩者的鏈表數(shù)據(jù)結(jié)構(gòu)，內(nèi)部每個(gè)節(jié)點(diǎn)即為一個(gè)ziplist，這樣的設(shè)計(jì)實(shí)際上是對(duì)空間和時(shí)間的這種。

對(duì)于一個(gè)雙向列表而言，不僅需要保存內(nèi)部數(shù)據(jù)，還要維護(hù)前后指針，占用空間；當(dāng)列表長(zhǎng)度過長(zhǎng)時(shí)，也會(huì)產(chǎn)生碎片化問題，因此我們將部分?jǐn)?shù)據(jù)封裝在一個(gè)ziplist里，減少指針個(gè)數(shù)，并且減少內(nèi)存脆片，當(dāng)然ziplist本身也不宜設(shè)置過長(zhǎng)，找不到足夠大的連續(xù)空間給ziplist的話，存儲(chǔ)效率也會(huì)下降。具體長(zhǎng)度設(shè)置要取決于業(yè)務(wù)場(chǎng)景。

2.4 set類型的底層實(shí)現(xiàn)

set類型主要由hashtable和intset實(shí)現(xiàn)

當(dāng)內(nèi)部數(shù)據(jù)全為整數(shù)并且內(nèi)部數(shù)據(jù)量小于512個(gè)時(shí)，就使用intset去實(shí)現(xiàn)，intset本質(zhì)上是一個(gè)由整數(shù)實(shí)現(xiàn)的有序集合，內(nèi)部使用二分查找，和ziplist一樣，也是一塊連續(xù)的內(nèi)存空間，并且針對(duì)證書大小也進(jìn)行了不同的編碼來實(shí)現(xiàn)對(duì)內(nèi)存的優(yōu)化。

當(dāng)不滿足條件時(shí)，就會(huì)使用hashtable去實(shí)現(xiàn)，key即為存儲(chǔ)數(shù)據(jù)，因?yàn)槲覀儾魂P(guān)心value的值，所以value一般存儲(chǔ)為null值。

2.5 zset類型的底層實(shí)現(xiàn)

zset類型由skiplist(跳表)來實(shí)現(xiàn)，以 1 2 3 4 5 6 7 8 9 10中查找7為例，按照鏈表而言，要一個(gè)一個(gè)遍歷去查找，而對(duì)于跳表，每個(gè)節(jié)點(diǎn)內(nèi)部會(huì)隨機(jī)儲(chǔ)存下一個(gè)目標(biāo)以及跳過的層數(shù)，比如從1開始，跳到4，4<7，因此不需要關(guān)心1-4之間的數(shù)據(jù)，4跳到8，8>7，因此回溯到4，4跳到6，然后6跳到8，發(fā)現(xiàn)8>7，因此回溯到6，6跳到7，這就是跳表的基礎(chǔ)原理，每個(gè)節(jié)點(diǎn)內(nèi)部會(huì)儲(chǔ)存下一個(gè)節(jié)點(diǎn)以及能夠跳躍的節(jié)點(diǎn)。

那么是怎么設(shè)定每個(gè)節(jié)點(diǎn)能夠跳躍到哪些節(jié)點(diǎn)的呢？

每個(gè)節(jié)點(diǎn)在初始化時(shí)，會(huì)隨機(jī)設(shè)置一個(gè)level數(shù)組來表明自身的層級(jí)(隨機(jī)概率p由開發(fā)者設(shè)定)，最下面一層存儲(chǔ)下一個(gè)節(jié)點(diǎn)，第二層存儲(chǔ)下一個(gè)擁有二層數(shù)組的節(jié)點(diǎn)，第三層存儲(chǔ)下一個(gè)擁有三層數(shù)組的節(jié)點(diǎn)，最終打到尾節(jié)點(diǎn)上。