一、Redis數(shù)據(jù)結構：
SDS
SDS（動態(tài)字符串）包含字符數(shù)組buf[]，字符數(shù)組現(xiàn)有長度len，字符數(shù)組分配空間的長度alloc，SDS類型flags。
總結：
1、C語言中使用char*實現(xiàn)字符串的不足，主要是因為使用“\0”表示字符串結束，操作時需遍歷字符串，效率不高，并且無法完整表示包含“\0”的數(shù)據(jù)，因而這就無法滿足Redis的需求。
2、Redis專門設計了SDS數(shù)據(jù)結構，在字符數(shù)組的基礎上，增加了字符數(shù)組長度和分配空間大小等元數(shù)據(jù)。這樣一來，需要基于字符串長度進行的追加、復制、比較等操作，就可以直接讀取元數(shù)據(jù)，效率也就提升了。而且，SDS不通過字符串中的“\0”字符判斷字符串結束，而是直接將其作為二進制數(shù)據(jù)處理，可以用來保存圖片等二進制數(shù)據(jù)。
3、SDS中是通過設計不同SDS類型來表示不同大小的字符串，并使用attribute ((packed))這個編程小技巧，來實現(xiàn)緊湊型內(nèi)存布局，達到節(jié)省內(nèi)存的目的。
Hash
哈希沖突：Redis采用了鏈式哈希，在不擴容哈希表的前提下，將具有相同哈希值的數(shù)據(jù)鏈接起來，以便這些數(shù)據(jù)在表中仍然可以被查詢到。
（但隨著鏈表長度的增加，Hash表在一個位置上查詢哈希項的耗時就會增加，所以引用了rehash）
Rehash指擴大Hash表空間，用一個hash表（ht[0]）復制到另一個hash表（ht[1]），然后將ht[1]設置為ht[0]
rehash開銷：Redis實現(xiàn)了漸進式rehash設計，進而緩解了rehash操作帶來的額外開銷對系統(tǒng)的性能影響。
1、 rehash擴容擴多大？
默認是原來空間的2倍
2、為什么有rehash開銷？（為什么要實現(xiàn)漸進式rehash？）
Hash表執(zhí)行rehash時，需將鍵從原來的位置拷貝到新的位置。而在鍵拷貝時，由于Redis主線程無法執(zhí)行其他請求，所以鍵拷貝會阻塞主線程，這樣就會產(chǎn)生rehash開銷。
3、漸進式rehash如何實現(xiàn)？
Redis并不會一次性把當前Hash表中的所有鍵，都拷貝到新位置，而是會分批拷貝，每次的鍵拷貝只拷貝Hash表中一個bucket中的哈希項
4、什么時候觸發(fā)rehash？
hash表承載的元素個數(shù)超過了它本身的大小或者hash表承載的元素個數(shù)是它本身大小的5倍
Sorted Set
Sorted Set采用跳表和哈希表
跳表高效支持范圍查詢、哈希表高效支持單點查詢。
跳表是一個多層的有序鏈表，每一層也是由多個結點通過指針連接起來的。
Ziplist、quicklist、Listpack
Ziplist不足：ziplist中元素個數(shù)多了，它的查找效率就會降低。而且如果在ziplist里新增或修改數(shù)據(jù)，ziplist占用的內(nèi)存空間還需要重新分配；更糟糕的是，ziplist新增某個元素或修改某個元素時，可能會導致后續(xù)元素的prevlen占用空間都發(fā)生變化，從而引起連鎖更新問題，導致每個元素的空間都要重新分配，這就會導致ziplist的訪問性能下降。
Quicklist：quicklist結構在ziplist基礎上，使用鏈表將ziplist串聯(lián)起來，鏈表的每個元素就是一個ziplist。這種設計減少了數(shù)據(jù)插入時內(nèi)存空間的重新分配，以及內(nèi)存數(shù)據(jù)的拷貝。同時，quicklist限制了每個節(jié)點上ziplist的大小，一旦一個ziplist過大，就會采用新增quicklist節(jié)點的方法。
Listpack：該結構沿用了ziplist緊湊型的內(nèi)存布局，把每個元素都緊挨著放置。listpack中每個列表項不再包含前一項的長度了，因此當某個列表項中的數(shù)據(jù)發(fā)生變化，導致列表項長度變化時，其他列表項的長度是不會受影響的，因而這就避免了ziplist面臨的連鎖更新問題。
Redis數(shù)據(jù)結構
鏈表
Redis鏈表為雙向無環(huán)鏈表
Redis中的list是個雙向無環(huán)鏈表，并使用了一個list來持有鏈表
雙向：鏈表節(jié)點帶有前驅、后繼指針獲取某個節(jié)點的前驅、后繼節(jié)點的時間復雜度為0(1)。
無環(huán): 鏈表為非循環(huán)鏈表表頭節(jié)點的前驅指針和表尾節(jié)點的后繼指針都指向NULL，對鏈表的訪問以NULL為終點。
帶表頭指針和表尾指針：通過list結構中的head和tail指針，獲取表頭和表尾節(jié)點的時間復雜度都為O(1)。
帶鏈表長度計數(shù)器:通過list結構的len屬性獲取節(jié)點數(shù)量的時間復雜度為O(1)。
多態(tài)：鏈表節(jié)點使用void*指針保存節(jié)點的值，并且可以通過list結構的dup、free、match三個屬性為節(jié)點值設置類型特定函數(shù)，所以鏈表可以用來保存各種不同類型的值。
字典
Redis字典使用散列表最為底層實現(xiàn)，一個散列表里面有多個散列表節(jié)點，每個散列表節(jié)點就保存了字典中的一個鍵值對。
Redis如何解決散列沖突
鏈式哈希和rehash
鏈式哈希：在不擴容哈希表的前提下，將具有相同哈希值的數(shù)據(jù)鏈接起來，以便這些數(shù)據(jù)在表中仍然可以被查詢到。
Rehash：用一個hash表（ht[0]）復制到另一個hash表（ht[1]），然后將ht[1]設置為ht[0]
跳躍表
跳躍表基于鏈表，每層都是有序雙向鏈表（有前進指針和后退指針）
跳躍表以空間換時間的方式提升了查找速度
Redis有序集合在節(jié)點元素較大或者元素數(shù)量較多時使用跳躍表實現(xiàn)
Redis的跳躍表實現(xiàn)由 zskiplist和 zskiplistnode兩個結構組成,其中 zskiplist用于保存跳躍表信息(比如表頭節(jié)點、表尾節(jié)點、長度),而zskiplistnode則用于表示跳躍表節(jié)點
Redis每個跳躍表節(jié)點的層高都是1至32之間的隨機數(shù)
在同一個跳躍表中,多個節(jié)點可以包含相同的分值,但每個節(jié)點的成員對象必須是唯一的跳躍表中的節(jié)點按照分值大小進行排序,當分值相同時,節(jié)點按照成員對象的大小進行排序。
整數(shù)集合
整數(shù)集合是Redis自己設計的一種存儲結構，集合鍵的底層實現(xiàn)之一。
整數(shù)集合的底層實現(xiàn)為數(shù)組，這個數(shù)組以有序、無重復的方式保存集合元素,在有需要時,程序會根據(jù)新添加元素的類型,改變這個數(shù)組的類型。
升級操作為整數(shù)集合帶來了操作上的靈活性,并且盡可能地節(jié)約了內(nèi)存。
整數(shù)集合只支持升級操作,不支持降級操作
升級指的是存儲一個int64數(shù)據(jù)類型的元素，將數(shù)組中int32的元素全部都變成int64位數(shù)據(jù)類型
