redis性能為何如此突出？

1. 純內(nèi)存操作，內(nèi)存操作本身就很快。
2. 鍵值對(duì)是按一定的數(shù)據(jù)結(jié)構(gòu)來(lái)組織的，操作鍵值對(duì)最終就是對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行增刪改查操作，所以高效的數(shù)據(jù)結(jié)構(gòu)是 Redis 快速處理數(shù)據(jù)的基礎(chǔ)。

redis類型有哪些？

1. string 字符串
2. list 列表
3. hash 哈希
4. set 集合
5. sorted set 有序集合

底層數(shù)據(jù)結(jié)構(gòu)有哪些及分別對(duì)應(yīng)了哪些類型？

1. 簡(jiǎn)單動(dòng)態(tài)字符串
2. 雙向鏈表
3. 壓縮列表
4. 哈希表
5. 跳躍表
6. 整數(shù)數(shù)組

類型對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)

String 類型的底層實(shí)現(xiàn)只有簡(jiǎn)單動(dòng)態(tài)字符串。而 List、Hash、Set 和 Sorted Set (四種類型稱為集合類型)，兩種底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，特點(diǎn)是一個(gè)鍵對(duì)應(yīng)了一個(gè)集合的數(shù)據(jù)。

鍵和值用什么結(jié)構(gòu)去組織，怎么快速找到鍵的？

一個(gè)全局哈希表(可以理解為數(shù)組)，數(shù)組的key是計(jì)算出來(lái)的哈希值，元素是哈希桶，哈希桶保存了鍵值指針，*key和*value，所以在查找鍵的速度還是很快的。

全局哈希表

全局哈希表帶來(lái)的問(wèn)題

1. hash沖突

我們知道hash值計(jì)算必然會(huì)產(chǎn)生沖突的問(wèn)題，redis采用了下拉式解決哈希沖突，也稱之為鏈?zhǔn)焦！?/p>

哈希沖突解決方式

這種解決方式在數(shù)據(jù)量可能會(huì)引起哈希表沖突過(guò)多，會(huì)導(dǎo)致某個(gè)鏈上效率低下。

哈希表沖突多，鏈上效率變慢？

redis采用rehash，默認(rèn)使用兩張哈希表，當(dāng)?shù)?張哈希表沖突過(guò)多時(shí)，采用rehash，rehash分三步:

• 給哈希表 2 分配更大的空間，例如是當(dāng)前哈希表 1 大小的兩倍；
• 把哈希表 1 中的數(shù)據(jù)重新映射并拷貝到哈希表 2 中；
• 釋放哈希表 1 的空間。
  至此，哈希表1留作下次的rehash時(shí)使用。

redis單線程，如果rehash(第二步)到2表數(shù)據(jù)量大時(shí)造成嚴(yán)重阻塞？

是的，所以redis采用了漸進(jìn)式rehash，簡(jiǎn)單來(lái)說(shuō)就是在第二步拷貝數(shù)據(jù)時(shí)，Redis 仍然正常處理客戶端請(qǐng)求，每處理一個(gè)請(qǐng)求時(shí)，從哈希表 1 中的第一個(gè)索引位置開始，順帶著將這個(gè)索引位置上的所有 entries 拷貝到哈希表 2 中；等處理下一個(gè)請(qǐng)求時(shí)，再順帶拷貝哈希表 1 中的下一個(gè)索引位置的 entries。如下圖所示：

漸進(jìn)式rehash

什么是壓縮列表？

壓縮列表

• zlbytes(列表長(zhǎng)度)
• zltail(列表尾的偏移量)
• zllen列表的 entry 個(gè)數(shù)
• zlend(列表結(jié)束)
  查找第一個(gè)元素和最后一個(gè)元素O(1)，其他元素O(N)

什么是跳表？

增加多級(jí)索引。

跳表

結(jié)構(gòu)復(fù)雜度

回歸題目答案總結(jié)

• 單元素操作是基礎(chǔ)
  如：(hash類型HGET、HSET 和 HDEL，Set 類型的 SADD、SREM、SRANDMEMBER)，都為O(1),如果同時(shí)添加多個(gè)元素此時(shí)為O(N)

• 范圍操作很耗時(shí)
  如：Hash 類型的 HGETALL 和 Set 類型的 SMEMBERS，或者范圍類如List 類型的 LRANGE 和 ZSet 類型的 ZRANGE。O(N),可以嘗試使用SCAN解決，避免一次返回所有數(shù)據(jù)阻塞。

• 統(tǒng)計(jì)操作通常高效
  集合類型對(duì)集合中所有元素個(gè)數(shù)的記錄，例如 LLEN 和 SCARD。這類操作復(fù)雜度只有 O(1)，壓縮列表、雙向鏈表、整數(shù)數(shù)組這些數(shù)據(jù)結(jié)構(gòu)時(shí)，記錄了總數(shù)

• 例外情況有幾個(gè)
  壓縮列表和雙向鏈表都會(huì)記錄表頭和表尾的偏移量。這樣一來(lái)，對(duì)于 List 類型的 LPOP、RPOP、LPUSH、RPUSH 這四個(gè)操作來(lái)說(shuō)，它們是在列表的頭尾增刪元素，這就可以通過(guò)偏移量直接定位，所以它們的復(fù)雜度也只有 O(1)，可以實(shí)現(xiàn)快速操作