redis 是 key-value 型數(shù)據(jù)庫(kù)，key 的數(shù)據(jù)類型 string，value 的數(shù)據(jù)類型有五種（常見(jiàn)的）string、list、hash、set、zset。五種數(shù)據(jù)類型與底層數(shù)據(jù)結(jié)構(gòu)的對(duì)應(yīng)關(guān)系如下圖：
一、哈希表
redis 使用全局哈希表存儲(chǔ)庫(kù)中鍵值對(duì)關(guān)系，全局哈希表類似一個(gè)數(shù)組，每一個(gè)元素稱為一個(gè)哈希桶，桶中存儲(chǔ)兩個(gè)指針*key和*value，分別指向 key 和 value。這樣一來(lái)，即使值是一個(gè)集合也可以通過(guò)*value找到。
哈希沖突：數(shù)據(jù)量過(guò)大時(shí)，會(huì)出現(xiàn)多個(gè)值落在同一個(gè)桶中的情況。
鏈?zhǔn)焦?/strong>：同一個(gè)哈希桶中的多個(gè)元素用一個(gè)鏈表來(lái)保存，它們之間依次用指針連接。
redis 采用鏈?zhǔn)焦５姆绞浇鉀Q哈希沖突。但如果沖突過(guò)多，鏈過(guò)長(zhǎng)，導(dǎo)致效率降低。rehash操作解決這個(gè)問(wèn)題
1.rehash
rehash 操作是指增加現(xiàn)有的哈希桶的數(shù)量，使增多的 entry 元素在更多的桶之間分散保存。
操作流程：
- 使用兩個(gè)全局哈希表。哈希表 1 和哈希表 2，剛插入數(shù)據(jù)時(shí)，默認(rèn)使用哈希表 1，此時(shí)哈希表 2 并沒(méi)有被分配空間；
- 隨著數(shù)據(jù)增多，給哈希表 2 分配更大的空間，把哈希表1中的數(shù)據(jù)重新映射并拷貝到哈希表 2 中；
- 釋放哈希表 1 的空間；
2.漸進(jìn)式rehash
rehash 操作拷貝過(guò)程涉及大量數(shù)據(jù)拷貝，可能會(huì)造成 redis 主線程阻塞，采用漸進(jìn)式rehash解決。
原理：在數(shù)據(jù)拷貝時(shí)，Redis 仍然正常處理客戶端請(qǐng)求，每處理一個(gè)請(qǐng)求時(shí)，從哈希表 1 中的第一個(gè)索引位置開(kāi)始，順帶著將這個(gè)索引位置上的所有 entries 拷貝到哈希表2中；等處理下一個(gè)請(qǐng)求時(shí)，再順帶拷貝哈希表 1 中的下一個(gè)索引位置的 entries。
二、壓縮列表
壓縮列表類似一個(gè)數(shù)組，數(shù)組中每一個(gè)元素保存一個(gè)數(shù)據(jù)。表頭三個(gè)字段zlbytes、zltail 和zllen，分別表示列表長(zhǎng)度、列表尾的偏移量和列表中的 entry 個(gè)數(shù)，表尾zlend字段表示列表結(jié)束。
每個(gè) entry 中三個(gè)字段previous_entry_length、encoding、content，分別表示前一個(gè)節(jié)點(diǎn)的長(zhǎng)度、數(shù)據(jù)類型和編碼格式、節(jié)點(diǎn)的值。
面試題-壓縮列表相比傳統(tǒng)數(shù)組的優(yōu)勢(shì)是什么？
內(nèi)存節(jié)省到極致！
- 傳統(tǒng)數(shù)組。數(shù)組存儲(chǔ)不同長(zhǎng)度的字符時(shí)，會(huì)選擇最大的字符長(zhǎng)度作為每個(gè)節(jié)點(diǎn)的內(nèi)存大小。如果只有一個(gè)元素的長(zhǎng)度超大，但是其他的元素長(zhǎng)度都比較小，那么所有元素的內(nèi)存都用超大的數(shù)字就會(huì)導(dǎo)致內(nèi)存的浪費(fèi)；
- 壓縮列表。數(shù)組中每個(gè)節(jié)點(diǎn)的大小就是實(shí)際內(nèi)容的大??；
三、跳躍表
跳躍表是在鏈表的基礎(chǔ)上，增加多級(jí)索引，通過(guò)索引位置的跳轉(zhuǎn)，實(shí)現(xiàn)數(shù)據(jù)的快速定位。如下圖：
面試題-跳躍表相比紅黑樹(shù)等平衡樹(shù)的優(yōu)點(diǎn)是什么？
- 插入速度非?？焖?，因?yàn)椴恍枰M(jìn)行旋轉(zhuǎn)等操作來(lái)維護(hù)平衡性；
- 更容易實(shí)現(xiàn)；
- 支持無(wú)鎖操作；
