一、String底層——sds（Simple Dynamic String）

Redis 并沒(méi)有直接用 C 語(yǔ)言的字符串，而是自己搞了一個(gè) sds 的結(jié)構(gòu)體來(lái)表示字符串，這個(gè) sds 的全稱是 Simple Dynamic String，翻譯過(guò)來(lái)就是“簡(jiǎn)單的動(dòng)態(tài)字符串”。

1.sds相比C語(yǔ)言字符串的優(yōu)點(diǎn)

• 安全的二進(jìn)制存儲(chǔ)

資源。關(guān)于sds的擴(kuò)容和縮容下面會(huì)進(jìn)行詳細(xì)的介紹，這里先不贅述了。

在一些情況中，我們需要在字符串中存儲(chǔ)特殊字符，例如\0。如果使用C語(yǔ)言字符串，\0會(huì)被視為字符串結(jié)尾，這就導(dǎo)致了存儲(chǔ)的字符串不完整。為了存儲(chǔ)特殊字符，SDS會(huì)明確記錄字符串長(zhǎng)度而不是將\0視為字符串結(jié)尾，這樣我們就能夠在字符串里面存儲(chǔ)特殊字符了。這種記錄字符串長(zhǎng)度的方式被稱為“安全的二進(jìn)制存儲(chǔ)”。

• 減少 CPU 的消耗

C語(yǔ)言字符串是一個(gè)簡(jiǎn)單的char數(shù)組，沒(méi)有屬性來(lái)記錄字符串長(zhǎng)度。因此，每次需要獲取字符串長(zhǎng)度時(shí)，都需要從頭開(kāi)始一個(gè)一個(gè)字符地遍歷，直到遇到\0結(jié)束符。這樣的遍歷操作會(huì)消耗大量的CPU。SDS記錄字符串長(zhǎng)度，避免了這部分CPU消耗。

• 解決字符串的擴(kuò)縮容問(wèn)題

如C語(yǔ)言字符串的長(zhǎng)度需要在創(chuàng)建字符串時(shí)確定，如果需要在字符串后面添加數(shù)據(jù)，就需要重新分配char數(shù)組的空間，將新的字符串拷貝進(jìn)去，然后釋放原來(lái)的空間，這會(huì)消耗大量的資源。SDS解決了字符串?dāng)U展和縮放的問(wèn)題，這將在下面詳細(xì)介紹。

2.結(jié)構(gòu)

```c
typedef struct sdshdr {
    // 記錄 buf 數(shù)組中已使用字節(jié)的數(shù)量
    // 等于 SDS 所保存字符串的長(zhǎng)度
    int len;
    
    // 記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量
    int free;
    
    // 字節(jié)數(shù)組，用于保存字符串
    char buf[];
} sdshdr;

len：記錄了當(dāng)前SDS保存的字符串的長(zhǎng)度，即buf數(shù)組中已使用的字節(jié)數(shù)。這個(gè)值不包括空字符\0。
free：記錄了當(dāng)前SDS中未使用的字節(jié)數(shù)。這個(gè)值加上len等于buf數(shù)組的總長(zhǎng)度。
buf：實(shí)際存儲(chǔ)字符串的字符數(shù)組，以\0結(jié)尾。

SDS的結(jié)構(gòu)體中使用了柔性數(shù)組（Flexible Array Member）的技術(shù)，即buf數(shù)組沒(méi)有指定大小，可以根據(jù)需要?jiǎng)討B(tài)分配內(nèi)存。這種技術(shù)使得SDS的內(nèi)存分配更加高效，因?yàn)镾DS可以根據(jù)實(shí)際需要?jiǎng)討B(tài)調(diào)整內(nèi)存大小，避免了頻繁的內(nèi)存分配和釋放操作。

3.擴(kuò)容

如果字符串對(duì)象的長(zhǎng)度超過(guò)了當(dāng)前分配的空間，Redis會(huì)分配一個(gè)新的空間，并將原有的字符串內(nèi)容復(fù)制到新的空間中。新的空間通常是原有空間的兩倍大小，這樣可以減少擴(kuò)容的次數(shù)。擴(kuò)容的過(guò)程中，Redis還會(huì)更新字符串對(duì)象的長(zhǎng)度屬性，以反映新的大小。

4.縮容

如果字符串對(duì)象的長(zhǎng)度變得比較短，Redis可能會(huì)嘗試縮減它的空間以節(jié)省內(nèi)存。Redis會(huì)根據(jù)當(dāng)前字符串對(duì)象的長(zhǎng)度和分配的空間大小來(lái)決定是否需要進(jìn)行縮容。如果當(dāng)前字符串長(zhǎng)度小于等于1/5的空間大小，Redis會(huì)嘗試將空間縮減到當(dāng)前長(zhǎng)度所需的大小。縮容的過(guò)程中，Redis會(huì)分配一個(gè)新的空間，并將原有的字符串內(nèi)容復(fù)制到新的空間中?？s容的過(guò)程中，Redis還會(huì)更新字符串對(duì)象的長(zhǎng)度屬性，以反映新的大小。

需要注意的是，由于Redis的動(dòng)態(tài)字符串實(shí)現(xiàn)使用了惰性空間釋放機(jī)制，所以即使執(zhí)行了縮容操作，分配的空間也不會(huì)立即被釋放。相反，Redis會(huì)保留這些空間以備后續(xù)使用，這樣可以減少頻繁的內(nèi)存分配和釋放操作，從而提高Redis的性能。

二、List底層——quickList、zipList

1.quickList及其優(yōu)化過(guò)程

Redis開(kāi)發(fā)了quickList這樣的數(shù)據(jù)結(jié)構(gòu)作為Redis List的底層邏輯，實(shí)際上它就是一個(gè)雙端鏈表。

（1）quickList大致結(jié)構(gòu)

• 缺點(diǎn)：
  存儲(chǔ)密度低： 如果每個(gè) Node 節(jié)點(diǎn)里面 Value 指針指向的數(shù)據(jù)很小，比如只存儲(chǔ)了一個(gè) int 值，那 next、prev 指針占了 Node 節(jié)點(diǎn)的絕大部分空間，真正存儲(chǔ)數(shù)據(jù)的有效負(fù)載就比較低。
  內(nèi)存碎片： 鏈表節(jié)點(diǎn)分配很多的話，就會(huì)出現(xiàn)很多不連續(xù)的內(nèi)存碎片。
  查詢效率低： 還有就是，鏈表查詢數(shù)據(jù)的時(shí)候，需要順著 next 或者 prev 指針鏈表的一端開(kāi)始查找，不像數(shù)組那樣，可以按照下標(biāo)隨機(jī)訪問(wèn)，所以說(shuō)雙端鏈表的查找效率比較低。

（2）引入zipList進(jìn)行優(yōu)化

為了優(yōu)化上面的問(wèn)題，把 Node 節(jié)點(diǎn)的 Value 指針，指向了一個(gè) ziplist 實(shí)例，ziplist 是一塊連續(xù)的空間，里面可以存儲(chǔ)多個(gè) List 元素。簡(jiǎn)單來(lái)說(shuō)，ziplist 實(shí)際上就是用一塊連續(xù)的內(nèi)存區(qū)域，實(shí)現(xiàn)了類似鏈表的效果。

存儲(chǔ)密度變高、內(nèi)存碎片變少：這樣，quicklist 和簡(jiǎn)單的鏈表結(jié)構(gòu)相比呢，Node 節(jié)點(diǎn)數(shù)量會(huì)更少，內(nèi)存碎片也就更少了，而且一個(gè) Node 里面存放了多個(gè)元素，next、prev 指針占的空間就幾乎可以忽略了，有效負(fù)載也高了。

掃描效率變高：ziplist 雖然是一塊連續(xù)的空間，但是呢，它還是不能像數(shù)組那樣隨機(jī)訪問(wèn)。查找元素的時(shí)候，也是要從頭開(kāi)始掃描，聽(tīng)上去查找方面并沒(méi)有什么提升。但是也正是 ziplist 是一塊連續(xù)的內(nèi)存空間，掃描的時(shí)候，不會(huì)像 Node 那樣有很多指針解析的開(kāi)銷，數(shù)據(jù)量少的時(shí)候，迭代起來(lái)還是挺快的。

鑒于zipList篇幅較多，放在后面一節(jié)單獨(dú)介紹。

（3）引入listPack進(jìn)行優(yōu)化

從 7.0 開(kāi)始，Redis 就用 listpack 這個(gè)結(jié)構(gòu)替換了 ziplist 結(jié)構(gòu)。開(kāi)發(fā)者希望設(shè)計(jì)一種簡(jiǎn)單點(diǎn)的、能夠替換 ziplist 的緊湊型數(shù)據(jù)結(jié)構(gòu)。

下面這張圖是 listpack 結(jié)構(gòu)，它和 ziplist 的結(jié)構(gòu)很類似，也是分為頭、中、尾三部分。先來(lái)看頭、尾兩部分：頭部里面的 tot-bytes 占了 4 個(gè)字節(jié)，存了 listpack 占用的總字節(jié)數(shù)，num-elements 占用 2 個(gè)字節(jié)，存了這個(gè) listpack 里面的元素個(gè)數(shù)；尾部是一個(gè)字節(jié)的 end-byte，它的值始終是 255。

看上去和zipList差不多，但實(shí)際上存放數(shù)據(jù)本身的element和zip的存放數(shù)據(jù)本身的entry是不一樣的。后面有介紹

2.zipList

首先來(lái)看隊(duì)頭里面的 zlbytes 值，它里面存了一個(gè) int 值，占了 4 個(gè)字節(jié)，里面存的是整個(gè) ziplist 占的總字節(jié)數(shù)。

然后是隊(duì)頭的第二部分 zltail 值，也是一個(gè) int 值，占了 4 字節(jié)，記錄了最后一個(gè) entry 在 ziplist 里面的偏移字節(jié)數(shù)。為什么要存 zltail 這個(gè)值呢？主要是為了實(shí)現(xiàn)逆序遍歷。如果我們已知一個(gè) ziplist 的首地址，就可以結(jié)合它的 zltail 值，計(jì)算出最后一個(gè) entry 的地址，對(duì)吧？而在 entry 里面呢，會(huì)記錄前一個(gè) entry 的長(zhǎng)度，這樣的話，我們就可以找到前一個(gè) entry 的地址，于是一個(gè)個(gè) entry 反著找，就能實(shí)現(xiàn) ziplist 的逆序遍歷了。（至于 entry 的具體結(jié)構(gòu)呢，馬上就會(huì)說(shuō)到，咱們一步一步來(lái)哈。）

隊(duì)頭的第三部分是 zllen 值，它是一個(gè) 2 字節(jié)的整數(shù)，記錄了整個(gè) ziplist 中的 entry 個(gè)數(shù)，也就是元素個(gè)數(shù)哈。所以，我們說(shuō)一個(gè) ziplist 最多存儲(chǔ) 2^16-1 個(gè)元素，沒(méi)問(wèn)題吧？其實(shí)呢，如果元素個(gè)數(shù)超過(guò)了 2^16 -1，ziplist 依舊能存得下，但是這個(gè)場(chǎng)景就比較低效了。在 zllen 值變成全 1 的時(shí)候呢，Redis 就不再認(rèn)為 zllen 表示的是元素個(gè)數(shù)，而是把它當(dāng)成一個(gè)溢出的標(biāo)識(shí)，這個(gè)時(shí)候要獲取元素個(gè)數(shù)的話，就需要遍歷整個(gè) ziplist。

接下來(lái)看 ziplist 的結(jié)尾，也就是圖里面的 zlend 部分，它占了 1 個(gè)字節(jié)，而且它的值始終是 255，用來(lái)標(biāo)識(shí) ziplist 結(jié)束。這就類似于 C 字符串的 \0 結(jié)束符，這只是個(gè)類比而已哦，ziplist 已經(jīng)明確地記錄了整個(gè) ziplist 長(zhǎng)度，所以它本身就是二進(jìn)制安全的。

3.zipList和listPack的區(qū)別

ziplist是一種緊湊的列表實(shí)現(xiàn)，它將所有元素都存儲(chǔ)在一塊連續(xù)的內(nèi)存區(qū)域中。每個(gè)節(jié)點(diǎn)中存儲(chǔ)了一個(gè)元素以及一個(gè)前向指針和一個(gè)后向指針。ziplist可以在不需要任何額外內(nèi)存分配的情況下插入、刪除元素，這使得它在內(nèi)存使用和性能方面都非常高效。但是，由于它是緊湊的，所以 在插入和刪除元素時(shí)需要移動(dòng)后續(xù)元素的位置， 這會(huì)導(dǎo)致操作效率的下降。另外，由于ziplist是一種非常緊湊的結(jié)構(gòu)，所以它的 節(jié)點(diǎn)大小是固定的， 這意味著無(wú)法存儲(chǔ)超過(guò)一定大小的元素。

listpack是一種更為靈活的列表實(shí)現(xiàn)，它將列表元素存儲(chǔ)在一個(gè)或多個(gè)包中，每個(gè)包都有自己的頭部和尾部指針。每個(gè)包可以包含多個(gè)元素，元素的大小可以不同，這使得listpack能夠存儲(chǔ)更大的元素。在插入和刪除元素時(shí)，listpack只需要修改相應(yīng)的指針，而不需要像ziplist一樣移動(dòng)元素的位置，因此效率更高。 另外，listpack還支持壓縮，這可以在不需要額外內(nèi)存分配的情況下，將多個(gè)包合并成一個(gè)更大的包，從而節(jié)省內(nèi)存。但相對(duì)于ziplist而言，listpack的內(nèi)存使用和性能都要稍微遜色一些。

綜上，ziplist和listpack各有優(yōu)缺點(diǎn)，需要根據(jù)具體的使用場(chǎng)景來(lái)選擇使用哪種數(shù)據(jù)結(jié)構(gòu)。如果需要存儲(chǔ)小型元素，且對(duì)內(nèi)存使用和性能有較高的要求，可以選擇ziplist；如果需要存儲(chǔ)大型元素或者元素大小不固定，且對(duì)內(nèi)存使用和性能有一定要求，可以選擇listpack。

4.quickList的結(jié)構(gòu)

quicklist 同時(shí)使用雙向鏈表結(jié)構(gòu)和 listpack 連續(xù)內(nèi)存空間，主要是為了達(dá)到空間和時(shí)間上的折中。引入listPack或者zipList能帶來(lái)內(nèi)存性能上的提升，但是quickList本身的雙端鏈表的插入和刪除效率是比較高的。

三、Hash底層——zipList/listPack或dict

哈希表底層數(shù)據(jù)少、鍵值對(duì)都比較短的時(shí)候用 listpack 存，數(shù)據(jù)量大了之后就用 dict 存。

1.dict

Redis中的Hash類型底層是通過(guò)實(shí)現(xiàn)一個(gè)哈希表（Hash table）來(lái)實(shí)現(xiàn)的，這個(gè)哈希表被稱為dict（字典）。dict是Redis中非常常用的數(shù)據(jù)結(jié)構(gòu)之一，它是一個(gè)高效的鍵值對(duì)存儲(chǔ)結(jié)構(gòu)。

dict實(shí)際上是一個(gè)由多個(gè)哈希表組成的數(shù)組，每個(gè)哈希表都有自己的哈希函數(shù)，并且可以根據(jù)需要進(jìn)行擴(kuò)展或收縮。當(dāng)需要在一個(gè)Hash類型的鍵值對(duì)中執(zhí)行操作時(shí)，Redis首先會(huì)根據(jù)鍵的哈希值找到對(duì)應(yīng)的哈希表，然后再在這個(gè)哈希表中查找相應(yīng)的鍵值對(duì)。

dict中的每個(gè)元素都是一個(gè)哈希表節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)包含一個(gè)key指針和一個(gè)value指針，這兩個(gè)指針?lè)謩e指向鍵和值的內(nèi)存地址。在dict中，鍵是唯一的，而值可以是任何Redis支持的數(shù)據(jù)類型。每個(gè)哈希表節(jié)點(diǎn)還包含一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針，這使得dict可以高效地處理哈希沖突。

哈希表的求值過(guò)程如下：

1. 首先，Redis會(huì)根據(jù)鍵的哈希值計(jì)算出所屬的哈希表，并在該哈希表中查找對(duì)應(yīng)的桶（bucket）。
2. 然后，Redis會(huì)在桶中遍歷所有的哈希表節(jié)點(diǎn)，查找與指定鍵相匹配的節(jié)點(diǎn)。
3. 如果找到了匹配的節(jié)點(diǎn)，Redis就會(huì)返回該節(jié)點(diǎn)的值指針；否則，Redis會(huì)返回null指針，表示指定的鍵不存在。

在哈希表中查找元素的時(shí)間復(fù)雜度通常是O(1)，這使得dict成為Redis中高效的數(shù)據(jù)結(jié)構(gòu)之一。但是，當(dāng)哈希表中的元素?cái)?shù)量增加時(shí)，可能會(huì)導(dǎo)致哈希沖突增多，從而影響查找效率。因此，Redis中的dict還實(shí)現(xiàn)了哈希表擴(kuò)容和收縮的功能，可以動(dòng)態(tài)地調(diào)整哈希表的大小以適應(yīng)不同的負(fù)載情況。

2.擴(kuò)容和漸進(jìn)式 Rehash

Redis的Hash類型使用哈希表（Hash table）來(lái)實(shí)現(xiàn)。當(dāng)哈希表中的元素?cái)?shù)量增多時(shí)，可能會(huì)導(dǎo)致哈希沖突增多，從而影響查找效率。為了解決這個(gè)問(wèn)題，Redis實(shí)現(xiàn)了哈希表擴(kuò)容的功能，可以動(dòng)態(tài)地調(diào)整哈希表的大小以適應(yīng)不同的負(fù)載情況。

哈希表擴(kuò)容分為以下幾個(gè)步驟：

1. 創(chuàng)建一個(gè)新的哈希表，大小是原哈希表的兩倍。
2. 將所有原哈希表中的元素重新分配到新哈希表中。
3. 當(dāng)有新的元素需要添加時(shí)，先在新哈希表中查找，如果找到了就直接添加。如果沒(méi)有找到，則在原哈希表中添加新元素，并在后續(xù)的rehash過(guò)程中將該元素移動(dòng)到新哈希表中。

在哈希表進(jìn)行擴(kuò)容時(shí)，需要對(duì)原有的鍵值對(duì)進(jìn)行rehash操作，即將鍵值對(duì)從原哈希表移動(dòng)到新哈希表。rehash過(guò)程分為多個(gè)步驟：

1. 從原哈希表中選取一個(gè)桶（bucket）。
2. 遍歷該桶中的所有節(jié)點(diǎn)，將節(jié)點(diǎn)對(duì)應(yīng)的鍵值對(duì)從原哈希表中移除，并插入到新哈希表中。
3. 重復(fù)以上兩個(gè)步驟，直到原哈希表中的所有桶都被rehash完畢。

在rehash過(guò)程中，需要保證原哈希表和新哈希表的并發(fā)訪問(wèn)。因此，Redis使用了兩個(gè)哈希表來(lái)實(shí)現(xiàn)平滑的哈希表擴(kuò)容，即在rehash過(guò)程中，同時(shí)使用原哈希表和新哈希表來(lái)進(jìn)行鍵值對(duì)的查找和插入操作。這種方式可以避免在rehash過(guò)程中出現(xiàn)大量的哈希沖突，從而使得哈希表擴(kuò)容操作更加高效。 當(dāng)所有的鍵值對(duì)都被rehash到新哈希表中后，Redis會(huì)將原哈希表釋放掉，從而完成哈希表擴(kuò)容的過(guò)程。

需要注意的是，在rehash過(guò)程中，可能會(huì)存在同時(shí)訪問(wèn)原哈希表和新哈希表的情況，如果在這種情況下進(jìn)行刪除操作，可能會(huì)導(dǎo)致數(shù)據(jù)丟失。因此，在rehash過(guò)程中，Redis禁止對(duì)哈希表進(jìn)行刪除操作。

四、Set底層——dict或intSet

Set 底層的結(jié)構(gòu)也是 dict；但是，在元素都是整數(shù)值的時(shí)候，Set 可以用一種更省空間的方式來(lái)存數(shù)據(jù)——intset。

• 一個(gè) Set 要用 intset 作為底層存儲(chǔ)的話，需要滿足兩個(gè)條件：
  一個(gè)就是前面說(shuō)的，元素都是整數(shù)類型；
  另一個(gè)條件是這個(gè) Set 里面的元素個(gè)數(shù)，要少于 set-max-intset-entries 配置指定的這個(gè)值，這個(gè)值默認(rèn)是 512。

Redis 之所以使用 intset 結(jié)構(gòu)來(lái)進(jìn)行優(yōu)化，主要是為了減少內(nèi)存碎片，提高查詢效率，這也體現(xiàn)了 Redis 在空間占用和耗時(shí)等方面的折中和思考。

intSet

Redis中的intset是一種特殊的數(shù)據(jù)結(jié)構(gòu)，用于保存整數(shù)類型的元素集合。它是一種緊湊的、高效的數(shù)據(jù)結(jié)構(gòu)，可以在內(nèi)存中節(jié)省空間，并且可以快速地執(zhí)行一些常見(jiàn)的操作，如判斷元素是否存在于集合中、獲取集合中的最大值和最小值等。

intset的底層實(shí)現(xiàn)是一個(gè)數(shù)組，數(shù)組中的每個(gè)元素都是一個(gè)整數(shù)類型的值。數(shù)組中的元素按照從小到大的順序排列，并且所有元素都是唯一的。當(dāng)向intset中添加新元素時(shí)，如果該元素已經(jīng)存在于intset中，則不會(huì)進(jìn)行任何操作，否則將該元素插入到正確的位置，同時(shí)更新intset的長(zhǎng)度信息。

intset的內(nèi)存布局比較緊湊，它的每個(gè)元素都是一個(gè)整數(shù)類型的值，可以使用不同的存儲(chǔ)空間來(lái)存儲(chǔ)不同大小的整數(shù)。具體來(lái)說(shuō)，intset中的元素可以分為三類：

• int16_t：可以用16位的有符號(hào)整數(shù)表示。
• int32_t：可以用32位的有符號(hào)整數(shù)表示。
• int64_t：可以用64位的有符號(hào)整數(shù)表示。

在intset中，每個(gè)元素的類型是動(dòng)態(tài)確定的，它的類型由元素的大小來(lái)決定。當(dāng)intset中所有元素都能夠用int16_t來(lái)表示時(shí)，intset的元素類型就是int16_t；當(dāng)存在某個(gè)元素?zé)o法用int16_t來(lái)表示時(shí)，intset的元素類型就變?yōu)閕nt32_t；當(dāng)存在某個(gè)元素?zé)o法用int32_t來(lái)表示時(shí)，intset的元素類型就變?yōu)閕nt64_t。

intset的實(shí)現(xiàn)比較簡(jiǎn)單，可以快速地執(zhí)行一些常見(jiàn)的操作，如判斷元素是否存在于集合中、獲取集合中的最大值和最小值等。在intset中查找元素的時(shí)間復(fù)雜度通常是O(log n)，這使得它成為Redis中高效的數(shù)據(jù)結(jié)構(gòu)之一。但是，由于intset只能存儲(chǔ)整數(shù)類型的元素，因此它的應(yīng)用場(chǎng)景比較受限。

五、ZSet底層——skipList

skiplist 是基于隨機(jī)算法的一種有序鏈表，其查詢效率與紅黑樹(shù)的查詢效率差不多，都是 O(logn)，但是 skiplist 的結(jié)構(gòu)遠(yuǎn)比復(fù)雜的紅黑樹(shù)簡(jiǎn)單很多。

1.基本結(jié)構(gòu)

使用 skiplist 查找數(shù)據(jù)的時(shí)候，會(huì)先從最高層，也就是上圖中的 level 2，開(kāi)始向后遍歷，這里發(fā)現(xiàn) level 2 層小于 48 的最大節(jié)點(diǎn)是 18 節(jié)點(diǎn)，那么向下一層來(lái)到 level 1，繼續(xù)從 18 節(jié)點(diǎn)向后遍歷。在 level 1 層中發(fā)現(xiàn)小于 48 的最大節(jié)點(diǎn)是 35，那么再向下一層來(lái)到 level 0，繼續(xù)從 35 節(jié)點(diǎn)向后迭代，最終找到 48 這個(gè)目標(biāo)節(jié)點(diǎn)。

跳躍表的基本思想是在鏈表中添加“跳躍指針”，這些指針可以讓查找操作快速跳過(guò)一些不必要的節(jié)點(diǎn)，從而提高查找的效率。跳躍表中的每個(gè)節(jié)點(diǎn)都包含多個(gè)指針，每個(gè)指針都指向鏈表中的另外一個(gè)節(jié)點(diǎn)。這些指針可以讓跳躍表中的節(jié)點(diǎn)形成多個(gè)層次，每個(gè)層次都是一個(gè)鏈表，最底層的鏈表就是跳躍表的主鏈表。

在跳躍表的插入和刪除操作中，需要維護(hù)跳躍表中各個(gè)節(jié)點(diǎn)之間的指針關(guān)系，保證跳躍表的各個(gè)層次之間的鏈表保持有序。 在跳躍表的查找操作中，可以通過(guò)跳躍指針快速地跳過(guò)一些不必要的節(jié)點(diǎn)，從而提高查找的效率。跳躍表的查找操作的時(shí)間復(fù)雜度通常是O(log n)，這使得它成為一種高效的數(shù)據(jù)結(jié)構(gòu)。

Redis中使用跳躍表來(lái)實(shí)現(xiàn)有序集合（Sorted Set）數(shù)據(jù)結(jié)構(gòu)，有序集合中的元素是有序的，并且每個(gè)元素都對(duì)應(yīng)一個(gè)分?jǐn)?shù)（score），可以根據(jù)分?jǐn)?shù)進(jìn)行排序。有序集合中的元素可以通過(guò)跳躍表快速地進(jìn)行查找和排序，同時(shí)還可以支持插入、刪除等操作，因此在Redis中廣泛應(yīng)用于排行榜、計(jì)數(shù)器等場(chǎng)景。

需要注意的是，在跳躍表中的節(jié)點(diǎn)數(shù)量越多，跳躍表中的跳躍指針就越多，這會(huì)占用更多的內(nèi)存空間。因此，在實(shí)際應(yīng)用中，需要根據(jù)數(shù)據(jù)規(guī)模和性能需求等因素來(lái)選擇合適的跳躍表節(jié)點(diǎn)數(shù)量。

2.跳躍步伐設(shè)計(jì)

在設(shè)計(jì)跳躍表的跳躍步伐時(shí)，需要考慮以下因素：

• 節(jié)點(diǎn)數(shù)量： 跳躍表中的節(jié)點(diǎn)數(shù)量越多，跳躍指針就需要跨越的節(jié)點(diǎn)數(shù)量就越多，因此跳躍步伐也需要相應(yīng)地增大。

• 節(jié)點(diǎn)分布： 跳躍表中節(jié)點(diǎn)的分布情況也會(huì)影響跳躍步伐的設(shè)計(jì)。如果節(jié)點(diǎn)分布比較均勻，每個(gè)節(jié)點(diǎn)之間的距離比較相近，跳躍步伐可以設(shè)置得比較小；如果節(jié)點(diǎn)分布比較不均勻，節(jié)點(diǎn)之間的距離比較大，跳躍步伐需要設(shè)置得相對(duì)較大。

• 目標(biāo)節(jié)點(diǎn)位置： 跳躍步伐的大小還需要根據(jù)目標(biāo)節(jié)點(diǎn)的位置來(lái)確定。如果目標(biāo)節(jié)點(diǎn)在跳躍表的靠近頭部或尾部的位置，跳躍步伐可以設(shè)置得比較小；如果目標(biāo)節(jié)點(diǎn)在跳躍表的中間位置，跳躍步伐需要設(shè)置得相對(duì)較大。

基于以上因素，跳躍表的跳躍步伐通常是根據(jù)概率分布來(lái)設(shè)計(jì)的，例如常見(jiàn)的設(shè)計(jì)方式是使用1/2的概率向前跳躍一步，1/4的概率向前跳躍兩步，1/8的概率向前跳躍三步，以此類推，直到概率降至非常小的程度為止。這種設(shè)計(jì)方式可以保證跳躍表的查找效率較高，并且可以保持跳躍表的平衡性，從而提高跳躍表的可擴(kuò)展性。

3.skipList和紅黑樹(shù)的對(duì)比

Skip List和紅黑樹(shù)都是常見(jiàn)的平衡數(shù)據(jù)結(jié)構(gòu)，它們都可以用于實(shí)現(xiàn)有序集合等類似的數(shù)據(jù)結(jié)構(gòu)，具有一定的相似性，但也有一些區(qū)別。

1. 實(shí)現(xiàn)復(fù)雜度

Skip List的實(shí)現(xiàn)相對(duì)簡(jiǎn)單，對(duì)于插入、刪除和查找等基本操作，時(shí)間復(fù)雜度都是O(log n)，并且具有較好的可擴(kuò)展性和高效性能。而紅黑樹(shù)的實(shí)現(xiàn)相對(duì)復(fù)雜，雖然也具有O(log n)的時(shí)間復(fù)雜度，但是在實(shí)際應(yīng)用中，它的性能可能會(huì)受到平衡因子的影響，而且在極端情況下，可能會(huì)退化為鏈表，從而影響性能。

2. 空間復(fù)雜度

Skip List的空間復(fù)雜度相對(duì)較高，因?yàn)槊總€(gè)節(jié)點(diǎn)都需要存儲(chǔ)多個(gè)指針，從而占用更多的內(nèi)存空間。而紅黑樹(shù)的空間復(fù)雜度相對(duì)較低，因?yàn)槊總€(gè)節(jié)點(diǎn)只需要存儲(chǔ)一個(gè)指針和一些顏色信息，占用較少的內(nèi)存空間。

3. 插入和刪除操作

在Skip List中，插入和刪除操作相對(duì)簡(jiǎn)單，只需要修改節(jié)點(diǎn)的指針即可，不需要進(jìn)行旋轉(zhuǎn)操作。而在紅黑樹(shù)中，插入和刪除操作需要進(jìn)行旋轉(zhuǎn)操作，這會(huì)增加實(shí)現(xiàn)的復(fù)雜度。

4. 查找操作

在Skip List中，查找操作的時(shí)間復(fù)雜度通常是O(log n)，這使得它成為一種高效的數(shù)據(jù)結(jié)構(gòu)。而在紅黑樹(shù)中，查找操作的時(shí)間復(fù)雜度同樣是O(log n)，但是在實(shí)際應(yīng)用中，由于紅黑樹(shù)的實(shí)現(xiàn)比較復(fù)雜，可能會(huì)影響查找的效率。

在實(shí)際應(yīng)用中，Skip List和紅黑樹(shù)可以根據(jù)具體的需求來(lái)選擇使用。如果需要實(shí)現(xiàn)一個(gè)高效、可擴(kuò)展的有序集合，可以選擇使用Skip List；如果需要實(shí)現(xiàn)一個(gè)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，并且對(duì)空間和時(shí)間的要求比較高，可以選擇使用紅黑樹(shù)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-602952.html

到了這里，關(guān)于Redis追本溯源（二）數(shù)據(jù)結(jié)構(gòu)：String、List、Hash、Set、Zset底層數(shù)據(jù)結(jié)構(gòu)原理的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！