[[347595]]

本文轉(zhuǎn)載自微信公眾號(hào)「 SH的全棧筆記」，作者 SH 。轉(zhuǎn)載本文請(qǐng)聯(lián)系SH的全棧筆記公眾號(hào)。

如果你是一個(gè)有經(jīng)驗(yàn)的后端或者服務(wù)器開(kāi)發(fā)，那么一定聽(tīng)說(shuō)過(guò)Redis，其全稱叫Remote Dictionary Server。是由C語(yǔ)言編寫的基于Key-Value的存儲(chǔ)系統(tǒng)。說(shuō)直白點(diǎn)就是一個(gè)內(nèi)存數(shù)據(jù)庫(kù)，既然是內(nèi)存數(shù)據(jù)庫(kù)就會(huì)遇到如果服務(wù)器意外宕機(jī)造成的數(shù)據(jù)不一致的問(wèn)題。

這跟很多游戲服務(wù)器也是一樣的，感興趣的可以參考我之前的文章游戲服務(wù)器和Web服務(wù)器的區(qū)別。其數(shù)據(jù)首先會(huì)流向內(nèi)存，基于快速的內(nèi)存讀寫來(lái)實(shí)現(xiàn)高性能，然后定期將內(nèi)存的數(shù)據(jù)中的數(shù)據(jù)落地。Redis其實(shí)也是這么個(gè)流程，基于快速的內(nèi)存讀寫操作，單機(jī)的Redis甚至能夠扛住10萬(wàn)的QPS。

Redis除了高性能之外，還擁有豐富的數(shù)據(jù)結(jié)構(gòu)，支持大多數(shù)的業(yè)務(wù)場(chǎng)景。這也是其為什么如此受歡迎的原因之一，下面我們就來(lái)看一看Redis有哪些基礎(chǔ)數(shù)據(jù)類型，以及他們底層都是怎么實(shí)現(xiàn)的。

1. 數(shù)據(jù)類型

其基礎(chǔ)數(shù)據(jù)類型有String、List、Hash、Set、Sorted Set，這些都是常用的基礎(chǔ)數(shù)據(jù)類型，可以看到非常豐富，幾乎能夠滿足大部分的需求了。其實(shí)還有一些高級(jí)數(shù)據(jù)結(jié)構(gòu)，我們?cè)谶@章里暫時(shí)先不提，只聊基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。

2. String

String可以說(shuō)是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)了， 用法上可以直接和Java中的String掛鉤，你可以把String類型用于存儲(chǔ)某個(gè)標(biāo)志位，某個(gè)計(jì)數(shù)器，甚至狠一點(diǎn)，序列化之后的JSON字符串都行，其單個(gè)key限制為512M。其常見(jiàn)的命令為get、set、incr、decr 、mget。

2.1 使用

• get 獲取某個(gè)key，如果key不存在會(huì)返回空指針
• set 給key賦值，將key設(shè)置為指定的值，如果該key之前已經(jīng)有值了，那么將被新的值給覆蓋
• incr 給當(dāng)前的key的值+1，如果key不存在則會(huì)先給key調(diào)用set賦值為0，再調(diào)用incr。當(dāng)然如果該key的類型不能做加法運(yùn)算，例如字符串，就會(huì)拋出錯(cuò)誤
• decr 給當(dāng)前key的值-1，其余的同上
• mget 同get，只是一次性返回多條數(shù)據(jù)，不存在的key將會(huì)返回空指針
  
  

string相關(guān)命令

可能大多數(shù)的人只是到用一用的地步，這也無(wú)可厚非，但是如果是作為一個(gè)對(duì)技術(shù)有追求的開(kāi)發(fā)，或者說(shuō)你有想近大廠的想法，一定要有刨根問(wèn)底的精神。只有當(dāng)你真正知道一個(gè)東西的底層原理時(shí)，你遇到問(wèn)題時(shí)才能提供給你更多的思路去解決問(wèn)題。接下來(lái)我們就來(lái)聊一下Redis中String底層是如何實(shí)現(xiàn)的。

2.2 原理

2.2.1 結(jié)構(gòu)

我們知道Redis是用C語(yǔ)言寫的，但是Redis卻沒(méi)有直接使用，而是自己實(shí)現(xiàn)了一個(gè)叫SDS(Simple Dynamic String)的結(jié)構(gòu)來(lái)實(shí)現(xiàn)字符串，結(jié)構(gòu)如下。

struct sdshdr { 
  // 記錄buf中已使用的字節(jié)數(shù)量 
  int len; 
  // 記錄buf中未使用的字節(jié)數(shù)量 
  int free; 
  // 字節(jié)數(shù)組，用于保存字符串 
  char buf[]; 
} 

2.2.2 優(yōu)點(diǎn)

為什么Redis要自己實(shí)現(xiàn)SDS而不是直接用C的字符串呢?主要是因?yàn)橐韵聨c(diǎn)。

• 減少獲取字符串長(zhǎng)度開(kāi)銷 C語(yǔ)言中獲取字符串的長(zhǎng)度需要遍歷整個(gè)字符串，直到遇到結(jié)束標(biāo)志位\0，時(shí)間復(fù)雜度為O(n)，而SDS直接維護(hù)了長(zhǎng)度的變量，取長(zhǎng)度的時(shí)間復(fù)雜度為O(1)
• 避免緩沖區(qū)溢出 C語(yǔ)言中如果往一個(gè)字節(jié)數(shù)組中塞入超過(guò)其容量的字節(jié)，那么就會(huì)造成緩沖區(qū)溢出，而SDS通過(guò)維護(hù)free變量解決了這個(gè)問(wèn)題。向buf數(shù)組中寫入數(shù)據(jù)時(shí)，會(huì)先判斷剩余的空間是否足夠塞入新數(shù)據(jù)，如果不夠，SDS就會(huì)重新分配緩沖區(qū)，加大之前的緩沖區(qū)。且加大的長(zhǎng)度等于新增的數(shù)據(jù)的長(zhǎng)度
• 空間預(yù)分配&空間惰性釋放 C語(yǔ)言中，每次修改字符串都會(huì)重新分配內(nèi)存空間，如果對(duì)字符串修改了n次，那么必然會(huì)出現(xiàn)n次內(nèi)存重新分配。而SDS由于冗余了一部分空間，優(yōu)化了這個(gè)問(wèn)題，將必然重新分配n次變?yōu)樽疃喾峙鋘次，而數(shù)據(jù)從buf中移除的時(shí)候，空閑出來(lái)的內(nèi)存也不會(huì)馬上被回收，防止新寫入數(shù)據(jù)而造成內(nèi)存重新分配
• 保證二進(jìn)制安全 C語(yǔ)言中，字符串遇到\0會(huì)被截?cái)啵鳶DS不會(huì)因?yàn)閿?shù)據(jù)中出現(xiàn)了\0而截?cái)嘧址?，換句話說(shuō)，不會(huì)因?yàn)橐恍┨厥獾淖址绊憣?shí)際的運(yùn)算結(jié)果

可以結(jié)合下面的圖來(lái)理解SDS。

圖片來(lái)源于網(wǎng)絡(luò)，侵刪

總結(jié)一下就是上面列表的四個(gè)小標(biāo)題，為了減少獲取字符串長(zhǎng)度開(kāi)銷、避免緩沖區(qū)溢出、空間預(yù)分配&空間惰性釋放和保證二進(jìn)制安全。

3. List

List也是一個(gè)使用頻率很高的數(shù)據(jù)結(jié)構(gòu)，其涉及到的命令太多了，就不像String那樣一個(gè)一個(gè)演示了，感興趣的大家可以去搜一搜。命令有l(wèi)push、lpushx、rpush、rpushx、lpop、rpop、lindex、linsert、lrange、llen、lrem、lset、ltrim、rpoplpush、brpoplpush、blpop、brpop，其都是對(duì)數(shù)組中的元素的操作。

3.1 使用

List的用途我認(rèn)為主要集中在以下兩個(gè)方面。

當(dāng)作普通列表存儲(chǔ)數(shù)據(jù)(類似于Java的ArrayList)

用做異步隊(duì)列

普通列表這個(gè)自然不必多說(shuō)，其中存放的必然業(yè)務(wù)中需要的數(shù)據(jù)，下面來(lái)著重聊一下異步隊(duì)列。

啥玩意，List還能當(dāng)成隊(duì)列來(lái)玩?

List除了能被用做隊(duì)列，還能當(dāng)作棧來(lái)使用。在上面介紹了很多操作List命令，當(dāng)我們用rpush/lpop組合命令的時(shí)候，實(shí)際上就是在使用一個(gè)隊(duì)列，而當(dāng)我們用rpush/rpop命令組合的時(shí)候，就是在使用一個(gè)棧。lpush/rpop和lpush/lpop是同理的。

假設(shè)我們用的是rpush來(lái)生產(chǎn)消息，當(dāng)我們的程序需要消費(fèi)消息的時(shí)候，就使用lpop從異步隊(duì)列中消費(fèi)消息。但是如果采用這種方式，當(dāng)隊(duì)列為空時(shí)，你可能需要不停的去詢問(wèn)隊(duì)列中是否有數(shù)據(jù)，這樣會(huì)造成機(jī)器的CPU資源的浪費(fèi)。

所以你可以采取讓當(dāng)前線程Sleep一段時(shí)間，這樣的確可以節(jié)省一部分CPU資源。但是你可能就需要去考慮Sleep的時(shí)間，間隔太短，CPU上下文切換可能也是一筆不小的開(kāi)銷，間隔太長(zhǎng)，那么可能造成這條消息被延遲消費(fèi)(不過(guò)都用異步隊(duì)列了，應(yīng)該可以忽略這個(gè)問(wèn)題)。

除了Sleep，還有沒(méi)有其他的方式?

有，答案是blpop。當(dāng)我們使用blpop去消費(fèi)時(shí)，如果當(dāng)前隊(duì)列是空的，那么此時(shí)線程會(huì)阻塞住，直到下面兩種condition。

1. 達(dá)到設(shè)置的timeout時(shí)間
2. 隊(duì)列中有消息可以被消費(fèi)

比起Sleep一段時(shí)間，實(shí)時(shí)性會(huì)好一點(diǎn);比起輪詢，對(duì)CPU資源更加友好。

3.2 原理

在Redis3.2之前，Redis采用的是ZipList(壓縮列表)或者LinkedList(鏈表)。當(dāng)List中的元素同時(shí)滿足每個(gè)元素的小于64字節(jié)和List元素個(gè)數(shù)小于512個(gè)時(shí)，存儲(chǔ)的方式為ZipList。但凡有一個(gè)條件沒(méi)滿足就會(huì)轉(zhuǎn)換為L(zhǎng)inkedList。

而在3.2之后，其實(shí)現(xiàn)變成了QuickList(快速列表)。LinkedList由于是較為基礎(chǔ)的東西，此處就不贅述了。

3.2.1 ZipList

ZipList采用連續(xù)的內(nèi)存緊湊存儲(chǔ)，不像鏈表那樣需要有額外的空間來(lái)存儲(chǔ)前驅(qū)節(jié)點(diǎn)和后續(xù)節(jié)點(diǎn)的指針。按照其存儲(chǔ)的區(qū)域劃分，大致可以分為三個(gè)部分，每個(gè)部分也有自己的劃分，其詳細(xì)的結(jié)構(gòu)如下。

• header ziplist的頭部信息
  • zlbytes 標(biāo)識(shí)ziplist所占用的內(nèi)存字節(jié)數(shù)
  • zltail 到ziplist尾節(jié)點(diǎn)的偏移量
  • zllen ziplist中的存儲(chǔ)的節(jié)點(diǎn)數(shù)量
• entries 存儲(chǔ)實(shí)際節(jié)點(diǎn)的信息
  • pre_entry_length 記錄了前一個(gè)節(jié)點(diǎn)的長(zhǎng)度，通過(guò)這個(gè)值可以快速的跳轉(zhuǎn)到上一個(gè)節(jié)點(diǎn)
  • encoding 顧名思義，存儲(chǔ)量元素的編碼格式
  • length 所存儲(chǔ)數(shù)據(jù)的長(zhǎng)度
  • content 保存節(jié)點(diǎn)的內(nèi)容
• end 標(biāo)識(shí)ziplist的末尾

如果采用鏈表的存儲(chǔ)方式，鏈表中的元素由指針相連，這樣的方式可能會(huì)造成一定的內(nèi)存碎片。而指針也會(huì)占用額外的存儲(chǔ)空間。而ZipList不會(huì)存在這些情況，ZipList占用的是一段連續(xù)的內(nèi)存空間。

但是相應(yīng)地，ZipList的修改操作效率較為低下，插入和刪除的操作會(huì)設(shè)計(jì)到頻繁的內(nèi)存空間申請(qǐng)和釋放(有點(diǎn)類似于ArrayList重新擴(kuò)容)，且查詢效率同樣會(huì)受影響，本質(zhì)上ZipList查詢?cè)鼐褪潜闅v鏈表。

3.2.2 QuickList

在3.2版本之后，list的實(shí)現(xiàn)就換成了QuickList。QuickList將list分成了多個(gè)節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)采用ZipList存儲(chǔ)數(shù)據(jù)。

4. Hash

其用法就跟Java中的HashMap中一樣，都是往map中去丟鍵值對(duì)。

4.1 使用

基礎(chǔ)的命令如下：

• hset 在hash中設(shè)置鍵值對(duì)
• hget 獲hash中的某個(gè)key值
• hdel 刪除hash中某個(gè)鍵
• hlen 統(tǒng)計(jì)hash中元素的個(gè)數(shù)
• hmget 批量的獲取hash中的鍵的值
• hmset 批量的設(shè)置hash中的鍵和值
• hexists 判斷hash中某個(gè)key是否存在
• hkeys 返回hash中的所有鍵(不包含值)
• hvals 返回hash中的所有值(不包含鍵)
• hgetall 獲取所有的鍵值對(duì)，包含了鍵和值

其實(shí)大多數(shù)情況下的使用跟HashMap是差不多的，沒(méi)有什么較為特殊的地方。

4.2 原理

hash的底層實(shí)現(xiàn)也是有兩種，ZipList和HashTable。但具體采用哪一種與Redis的版本無(wú)關(guān)，而與當(dāng)前hash中所存的元素有關(guān)。首先當(dāng)我們創(chuàng)建一個(gè)hash的時(shí)候，采用的ZipList進(jìn)行存儲(chǔ)。隨著hash中的元素增多，達(dá)到了Redis設(shè)定的閾值，就會(huì)轉(zhuǎn)換為HashTable。

其設(shè)定的閾值如下：

• 存儲(chǔ)的某個(gè)鍵或者值長(zhǎng)度大于默認(rèn)值(64)
• ZipList中存儲(chǔ)的元素?cái)?shù)量大于默認(rèn)值(512)

ZipList上面我們專門簡(jiǎn)單分析了一下，理解這個(gè)設(shè)定應(yīng)該也比較容易。當(dāng)ZipList中的元素過(guò)多的時(shí)候，其查詢的效率就會(huì)變得低下。而HashTable的底層設(shè)計(jì)其實(shí)和Java中的HashMap差不多，都是通過(guò)拉鏈法解決哈希沖突。具體的可以參考從基礎(chǔ)的使用來(lái)深挖HashMap這篇文章。

5. Set

Set的概念可以與Java中的Set劃等號(hào)，用于存儲(chǔ)一個(gè)不包含重復(fù)元素的集合。

5.1 使用

其主要的命令如下，key代表redis中的Set，member代表集合中的元素。

• sadd sadd key member [...] 將一個(gè)或者多個(gè)元素加入到集合中，如果有已經(jīng)存在的元素會(huì)忽略掉。
• srem srem key member [...]將一個(gè)或者多個(gè)元素從集合中移除，不存在的元素會(huì)被忽略掉
• smembers smembers key返回集合中的所有成員
• sismember dismember key member判斷member在key中是否存在，如果存在則返回1，如果不存在則返回0
• scard scard key返回集合key中的元素的數(shù)量
• smove move source destination member將元素從source集合移動(dòng)到destination集合。如果source中不包含member，則不會(huì)執(zhí)行任何操作，當(dāng)且僅當(dāng)存在才會(huì)從集合中移出。如果destination已經(jīng)存在元素則不會(huì)對(duì)destination做任何操作。該命令是原子操作。
• spop spop key隨機(jī)刪除并返回集合中的一個(gè)元素
• srandmember srandmember key與spop一樣，只不過(guò)不會(huì)將元素刪除，可以理解為從集合中隨機(jī)出一個(gè)元素來(lái)。
• sinter 求一個(gè)或者多個(gè)集合的交集
• sinterstore sinterstore destination key [...]與sinter類似，但是會(huì)將得出的結(jié)果存到destination中。
• sunion 求一個(gè)或者多個(gè)集合的并集
• sunionstore sunionstore destination key [...]
• sdiff 求一個(gè)或者多個(gè)集合的差集
• sdiffstore sdiffstore destination key [...]與sdiff類似，但是會(huì)將得出的結(jié)果存到destination中。

5.2 原理

我們知道Java中的Set有多種實(shí)現(xiàn)。在Redis中也是，有IntSet和HashTable兩種實(shí)現(xiàn)，首先初始化的時(shí)候使用的是IntSet，而滿足如下的條件時(shí)，就會(huì)轉(zhuǎn)換成HashTable。

• 當(dāng)集合中保存的所有元素都是整數(shù)時(shí)
• 集合對(duì)象保存的元素?cái)?shù)量不超過(guò)512

上面已經(jīng)簡(jiǎn)單的介紹了HashTable了，所以這里只聊聊IntSet。

5.2.1 IntSet

intset底層是一個(gè)數(shù)組，既然數(shù)據(jù)結(jié)構(gòu)是數(shù)組，那么存儲(chǔ)數(shù)據(jù)就可以是有序的，這也使得intset的底層查詢是通過(guò)二分查找來(lái)實(shí)現(xiàn)。其結(jié)構(gòu)如下。

struct intset { 
  // 編碼方式 
  uint32_t encoding; 
  // 集合包含元素的數(shù)量 
  uint32_t length; 
  // 存儲(chǔ)元素的數(shù)組 
  int8_t contents[]; 
} 

與ZipList類似，IntSet也是使用的一連串的內(nèi)存空間，但是不同的是ZipList可以存儲(chǔ)二進(jìn)制的內(nèi)容，而IntSet只能存儲(chǔ)整數(shù);且ZipList存儲(chǔ)是無(wú)序的，IntSet則是有序的，這樣一來(lái)，元素個(gè)數(shù)相同的前提下，IntSet的查詢效率會(huì)更高。

6. Sorted

Set其與Set的功能大致類似，只不過(guò)在此基礎(chǔ)上，可以給每一個(gè)元素賦予一個(gè)權(quán)重。你可以理解為Java的TreeSet。與List、Hash、Set一樣，其底層的實(shí)現(xiàn)也有兩種，分別是ZipList和SkipList(跳表)。

初始化Sorted Set的時(shí)候，會(huì)采用ZipList作為其實(shí)現(xiàn)，其實(shí)很好理解，這個(gè)時(shí)候元素的數(shù)量很少，采用ZipList進(jìn)行緊湊的存儲(chǔ)會(huì)更加的節(jié)省空間。當(dāng)期達(dá)到如下的條件時(shí)，就會(huì)轉(zhuǎn)換為SkipList：

• 其保存的元素?cái)?shù)量的個(gè)數(shù)小于128個(gè)
• 其保存的所有元素長(zhǎng)度小于64字節(jié)

6.1 使用

下面的命令中，key代表zset的名字;4代表score，也就是權(quán)重;而member就是zset中的key的名稱。

• zadd zadd key 4 member用于增加元素
• zcard zcard key用于獲取zset中的元素的數(shù)量
• zrem zrem key member [...]刪除zset中一個(gè)或者多個(gè)key
• zincrby zincrby key 1 member給key的權(quán)重值加上score的值(也就是1)
• zscore zscore key member用于獲取指定key的權(quán)重值
• zrange zrange key 0 -1獲取zset中所有的元素，zrange key 0 -1 withscores獲取所有元素和權(quán)重，withscores參數(shù)的作用是決定是否將權(quán)重值也一起返回。其返回的元素按照從小到大排序，如果元素具有相同的權(quán)重，則會(huì)按照字典序排序。
• zrevrange zrevrange key 0 -1 withscores，其與zrange類似，只不過(guò)zrevrange按照從大到小排序。
• zrangebyscore zrangebyscore key 1 5，返回key中權(quán)重在區(qū)間(1, 5]范圍內(nèi)元素。當(dāng)然也可以使用withscores來(lái)將權(quán)重值一并返回。其元素按照從小到大排序。1代表min，5代表max，他們也可以分別是**-inf和inf**，當(dāng)你不知道key中的score區(qū)間時(shí)，就可以使用這個(gè)。還有一個(gè)類似于SQL中的limit的可選參數(shù)，在此就不贅述。

除了能夠?qū)ζ渲械脑靥砑訖?quán)重之外，使用ZSet還可以實(shí)現(xiàn)延遲隊(duì)列。

延遲隊(duì)列用于存放延遲任務(wù)，那什么是延遲隊(duì)列呢?

舉個(gè)很簡(jiǎn)單的例子， 你在某個(gè)電商APP中下訂單，但是沒(méi)有付款，此時(shí)它會(huì)提醒你，「訂單如果超過(guò)1個(gè)小時(shí)沒(méi)有支付，將會(huì)自動(dòng)關(guān)閉」;再比如在某個(gè)活動(dòng)結(jié)束前1個(gè)小時(shí)給用戶推送消息;再比如訂單完成后多少天自動(dòng)確認(rèn)收貨等等。

用人話解釋一遍，那就是過(guò)會(huì)才要干的事情。

那ZSet怎么實(shí)現(xiàn)這個(gè)功能?

其實(shí)很簡(jiǎn)單，就是將任務(wù)的執(zhí)行時(shí)間設(shè)置為ZSet中的元素權(quán)重，然后通過(guò)一個(gè)后臺(tái)線程定時(shí)的從ZSet中查詢出權(quán)重最小的元素，然后通過(guò)與當(dāng)前時(shí)間戳判斷，如果大于當(dāng)前時(shí)間戳(也就是該執(zhí)行了)就將其從ZSet中取出。

那，怎么取?

其實(shí)我看很多講Redis實(shí)現(xiàn)延遲隊(duì)列的博客都沒(méi)有把這個(gè)怎么取講清楚，到底該用什么命令，傳什么參數(shù)。我們使用zrangebyscore命令來(lái)實(shí)現(xiàn)，還記得-inf和inf嗎，其全稱是infinity，分別表示無(wú)限小和無(wú)限大。

由于我們并不知道延遲隊(duì)列當(dāng)中的score(也就是任務(wù)執(zhí)行時(shí)間)的范圍，所以我們可以直接使用-inf和inf，完整命令如下。

zrangescore key -inf inf limt 0 1 withscores 

還是有點(diǎn)用，那ZSet底層是咋實(shí)現(xiàn)的呢?

上面已經(jīng)講過(guò)了ZipList，就不贅述，下面聊聊SkipList。

6.2 原理

6.2.1 SkipList

SkipList存在于zset(Sorted Set)的結(jié)構(gòu)中，如下：

struct zset { 
  // 字典 
  dict *dict; 
  // 跳表 
  zskiplist *zsl; 
} 

而SkipList的結(jié)構(gòu)如下：

struct zskiplist { 
  // 表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn) 
  struct zskiplistNode *header, *tail; 
  // 表中節(jié)點(diǎn)的數(shù)量 
  unsigned long length; 
  // 表中層數(shù)最大的節(jié)點(diǎn)的層數(shù) 
  int level; 
} 

不知道大家是否有想過(guò)，為什么Redis要使用SkipList來(lái)實(shí)現(xiàn)ZSet，而不用數(shù)組呢?

首先ZSet如果數(shù)組存儲(chǔ)的話，由于ZSet中存儲(chǔ)的元素是有序的，存入的時(shí)候需要將元素放入數(shù)組中對(duì)應(yīng)的位置。這樣就會(huì)對(duì)數(shù)組進(jìn)行頻繁的增刪，而頻繁的增刪在數(shù)組中效率并不高，因?yàn)樯婕暗綌?shù)組元素的移動(dòng)，如果元素插入的位置是首位，那么后面的所有元素都要被移動(dòng)。

所以為了應(yīng)付頻繁增刪的場(chǎng)景，我們需要使用到鏈表。但是隨著鏈表的元素增多，同樣的會(huì)出現(xiàn)問(wèn)題，雖然增刪的效率提升了，但是查詢的效率變低了，因?yàn)椴樵冊(cè)貢?huì)從頭到尾的遍歷鏈表。所有如果有什么方法能夠提升鏈表的查詢效率就好了。

于是跳表就誕生了?；趩捂湵?，從第一個(gè)節(jié)點(diǎn)開(kāi)始，每隔一個(gè)節(jié)點(diǎn)，建立索引。其實(shí)也是單鏈表。只不是中間省略了節(jié)點(diǎn)。

例如存在個(gè)單鏈表 1 3 4 5 7 8 9 10 13 16 17 18

抽象之后的索引為 1 4 7 9 13 17

如果要查詢16只需要在索引層遍歷到13，然后根據(jù)13存儲(chǔ)的下層節(jié)點(diǎn)(真實(shí)鏈表節(jié)點(diǎn)的地址)，此時(shí)只需要再遍歷兩個(gè)節(jié)點(diǎn)就可以找到值為16的節(jié)點(diǎn)。

所以可以重新給跳表下一個(gè)定義，鏈表加多級(jí)索引的結(jié)構(gòu)，就是跳表

在跳表中，查詢?nèi)我鈹?shù)據(jù)的時(shí)間復(fù)雜度是O(logn)。時(shí)間復(fù)雜度跟二分查找是一樣的。可以換句話說(shuō)，用單鏈表實(shí)現(xiàn)了二分查找。但這也是一種用空間換時(shí)間的思路，并不是免費(fèi)的。

End

關(guān)于Redis的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)和其底層的原理就簡(jiǎn)單的聊到這里，之后的幾篇應(yīng)該會(huì)聊聊Redis的高可用和其對(duì)應(yīng)的解決方案，感興趣的可以持續(xù)關(guān)注，公眾號(hào)會(huì)比其他的平臺(tái)都先更新。