redis數據結構和數據類型

1.動態字符串SIMPLE DYNAMIC STRING(SDS)

觀察上圖中的SDS結構，頭部包含字符串長度和分配的空間，可以以O（1）的時間復雜度計算出字符串長度，并且有了字符串長度后可以無視c語言的字符串缺陷（\0作為結尾標識，容易被誤判），可以動態擴容以及二進制安全。

2.intset

intset是一個集合，用于存儲整形數據，由于是set所以滿足元素唯一性，在不需要擴容的情況下，插入新元素時，底層采用二分法進行查找插入位置，效率為Ologn。

intset支持動態擴容，如果插入的元素大小大于當前編碼ecoding設計大小，那么就會進行inset升級，具體見下述流程。

當插入一個比int16大得元素，那么就涉及到了整體的擴容，但這種情況會造成相當大得空間浪費。

具體過程是：假設目前的編碼是int16，那么就升級為int32（如果int32能夠裝下新插入的數據，如果不夠就繼續升級），然后按照排列的倒敘對所有數據進行移動，最后再插入新元素。因為新加入的元素所需容量比剩余元素都大，并且所有元素都是int整形，那么新插入的元素一定是最大的，所以存儲在末尾。

intSet 是一個set，本身得元素必須是唯一的，為了保證整體數據的有序性，所以在插入元素的時候需要進行判斷：

判斷方式即對傳入數據的值進行查找，如果沒有查找到，那么就插入，否則直接返回（有相同元素）。這個特性使得在當set集合中存儲的元素是整數時，并且插入數據不超過set中默認設置的intset最大值時，intset作為set數據類型的數據結構，否則dict會作為set的數據結構。

查找的過程使用二分查找，根據intset存儲的整形數據的value進行查找插入位置，用于保證intset的有序性。

3.dict

3.1Dict的數據結構

dict數據結構會創建一個dictht表示字典的hashtable，里面有一個指向entry數組的指針、size數組大小、sizemask使用與運算“&”進行取余、used表示已有entry的數量。

需要注意，這里的dictEntry是一個鍵值對。

后續的set就是使用dict進行實現的，不過將dictEntry設置為了0。

3.2Dict的擴容

dict這個數據結構存儲了兩張表，一張表用于存儲所有的entry的指針，一張表用于rehash。

rehash的原因在于dict需要進行擴容，最初的大小為size，如果此時used（即已存儲的entry數量）已經大于size的值了（即負載因子>1），那么此時就會考慮dict的擴容，前提是后臺不忙碌的情況，當負載因子>5之后，dict不管后臺是否有處理過程，都會進行擴容。

此時會根據used的數量，找到離used最近的2^n，比如現在的used為5，那么擴容的size就為8，會在等待執行rehash的表創建相應的存儲容量，再將原本數據復制到新表中，最后將原表置空，從而完成擴容。

3.3Dict的收縮

如果負載因子<0.1，就會觸發收縮，如果當前size<4那么會將另一張等待rehash的空表大小置為4，否則，根據size找到離size最近的2^n來進行擴容，最后將源數據復制到新表，將原數據表置為rehash輔助表。

3.4總結

dict的數據結構包含兩張dictht表，記為ht(0)與ht(1)，ht(0)用于存儲當前數據，ht(1)用于rehash輔助來擴容與收縮。ht(0)與ht(1)會反復翻轉，來實現擴容與收縮。擴容與收縮都是根據負載因子來判斷的，最終都會找到離size最近的2^n作為新的存儲容量。

最后需要了解一個細節，rehash不是一次性轉移整張表，而是批量處理部分數據內容，因為數據量大的情況下，處理時間會很長

4.ZipList

4.1數據結構

ziplist的頭部會保存整個鏈表的長度、尾指針以及entry的數量，ziplist用于節省存儲空間

ziplist節省空間的原因在于不會存儲指針，entry中會記錄上一個節點的entry大小、entry中自身節點大小與編碼方式以及自身數據，這樣會比存指針和數據節省更多空間。這里的entry就是指一個節點。

同時entry中存儲的內容content是可變長的，所以不會因為等長如intset浪費掉空間。

又由于ziplist中每個entry有上個節點的大小，所以可以通過地址計算進行順序以及逆序遍歷（順序遍歷通過當前entry起始地址加上本節點的大小計算下個節點的起始地址、逆序遍歷通過當前entry的起始地址-上個節點大小）

4.2連鎖更新問題

ziplist如果本節點的內容進行更新，假設現在使得后一個節點記錄的前一個節點的長度從1字節變為了5字節，也就是說當前節點的更新導致了下個節點的更新（因為后一個節點記錄了前一個節點的長度，而當前一個節點的長度大于254字節，就會使得后一個字節的前一個節點大小從1字節升級為5字節）。

在極端情況下就會出現一個節點更新，導致連鎖反應，后續節點都進行更新，更新需要使用到內核態，涉及到內核態與用戶態的切換，進行內存分配，資源開銷很大。

5.quicklist

quicklist的創建就是為了解決ziplist的自身問題，比如ziplist需要連續的存儲空間，那么當數據量很大時，內存分配很大的連續空間的難度會很高，所以為了解決這個問題，將ziplist拆分為多段，使用一個輔助節點來連接對應的ziplist段，每個輔助節點都有一個pre指針與next指針還有一個zip指針。

這個輔助接點就是quicklist節點。

整個數據結構稱為quicklist。

quicklist可以對每個ziplist進行壓縮，一般而言對中間節點進行壓縮，因為查詢是通過頭節點與尾節點進行查詢的。

6.SkipList

總結：跳表就是一個多指針鏈表，會在鏈表之間建立新的指針來增加遍歷的跨度，根據score的大小來具體判斷使用哪個跨度對應的指針，從而加速查找速度。

在redis中最多支持32級跳表

Redis 的跳表主要應用在 有序集合（ZSet） 的底層實現中（配合哈希表），它通過如下結構來維持元素的順序：

每個元素按照 score（分數）從小到大排列；
插入時按照 score 插入合適的位置；
查詢時可以快速跳躍查找，比如范圍查找、排名查找、按順序遍歷等。

7.RedisObject

8.String數據類型

string數據類型的基本編碼方式是RAW，redisobject與SDS是分塊存儲的，而當SDS的大小小于44字節時，此時RAW編碼會更改為EMBSTR。

如果存儲的字符串是整數類型，并且在long范圍以下，那么會在內存中創建一個空間用于存儲整形數據，然后將指針指向該空間即可。這種編碼方式是INT編碼

9.list數據類型

list數據結構底層實現使用了quicklist，lpush和rpush對應雙端隊列得隊首與隊尾，lpop與rpop同理。

10.set數據類型

set結構底層實現使用的是dict數據結構，dict數據結構存儲得是一個entry，也就是一個鍵值對。在set應用dict作為數據結構時，會將鍵值對中的值置為NULL

當存儲的值都為整數，并且存儲的數據量沒有超過set中設置的最大值時，使用的數據結構是intset

，否則使用dict

11.zset數據類型

zset這個數據類型存儲的內容是一個鍵值對，鍵存儲對應的value，而值存儲score。

zset的特性要求鍵值存儲、唯一鍵、可排序的特性。

所以對應的數據結構，滿足鍵值存儲的就只有dict字典。但是dict實際上是一個hash表，無法進行排序在zset中進行鍵值查詢。

而跳表本身包含score，在zset中用于范圍查詢和排序功能。

所以zset選擇將數據分別存儲在skipList和dict中，使用dict來進行查詢鍵值對，使用skipList來進行排序。

當zset中的數據量較少，單個數據的大小也較小，具體小于某個預設值時，為了節省空間，zset會轉換為一張ziplist壓縮表，ziplist本身不支持排序功能，但是其占用空間小，并且存儲的數據少，相應查詢時間也不會太長。相當于是一種時間換空間的策略，但是由于數據量少，這個時間的增長可以接收。

ziplist存儲的entry只能包含一個內容，所以在zset中，兩個連續的entry會分別存儲value和score

12.hash數據類型

底層就是使用dict，完全適配，沒什么好說的。

13.redis數據結構以及對應的數據類型總結

redis數據結構有SDS，這是redis自帶一種字符串存儲結構，其避免了c語言的字符串問題，同時支持空間的動態擴充，能以O（1）時間復雜度讀取字符串長度以及具有二進制安全；

有intset，這是一種相對靈活的整形數組，所有元素存儲大小都是相同的，如果某個元素大于當前存儲元素的最大空間，那么intset會進行動態升級。在intset中會在頭部記錄存儲的數據數量、尾部指針、當前的數據存儲空間大小（8、16、32）。支持存儲空間動態擴張、插入有序、底層使用了二分法來插入數據，所以元素是有序的，讀取速度快，缺點是需要連續的存儲空間，并且伴隨相當一部分的空間浪費；

有dict字典，這是一個典型的哈希表，通過hash code得到散列值，再將散列值與掩碼進行與運算得到具體的存儲位置。與經典哈希不同的點就在于使用與運算進行裝填。dict包含兩張ht，一張ht用于存放數據，一張ht用于rehash進行擴容與緊縮。擴容與緊縮都是根據負載因子來進行的，當負載因子大于1并且無后臺操作時，或者負載因子大于5時，進行擴容，當負載因子<0.1時進行緊縮。擴容與緊縮都是找當前離size最近的2^n來作為新的size，比如原本size為5，現在就取8；

有zipList壓縮鏈表，壓縮鏈表特點是每個節點包含上一個節點的長度以及自身長度，可以看作是一個可變長的列表，雖然不支持隨機訪問，但是支持順序、逆序訪問。由于沒有使用指針，并且每個數據內容都裝滿了存儲空間（除了存儲的輔助信息外），存儲的密度非常高，基本不會出現空間浪費。缺點是需要申請連續的存儲空間，當所需連續空間較大時，操作系統難以分配所需空間，同時還有可能出現連鎖更新，即一個節點擴容，導致下個節點的encoding部分增大，剛好又引起下下一個節點的encoding部分增大，從而出現連鎖反應；

quicklist快速鏈表，快速鏈表就是使用輔助接點將ziplist穿起來，并且輔助結點有pre behind、zip三個指針。quicklist解決了ziplist的問題，使得一個很長的數據內容能夠切成多篇進行存儲。quicklist是list數據類型的底層實現。同時quicklist能夠將ziplist的中間部分進行壓縮，因為list數據類型基本只會對隊首與隊尾進行操作，通過壓縮中間部分內容可以節省存儲空間；

skiplist跳表，跳表可以看作是一個多指針鏈表，鏈表中不同的節點間建立指針來加快查詢速度，跳表的查詢速度基本與紅黑樹相當。并且在跳表中維護了一個score值，根據score值來進行查詢，所以跳表的數值是有序的。目前學到的數據結構中，就skiplist和intset是有序的，intset底層使用二分查找實現有序插入，而skiplist根據score來進行有序插入；

redisobject，所有redis數據存儲的頂層封裝就是redisobject，包含對應的數據編碼方式，數據指針等。

在數據類型中學習了String、list、set、zset、hash

String使用SDS進行存儲，沒什么好說的；

list使用quicklist實現，quicklist通過多個輔助節點和多個ziplist組合而成，將中間ziplist進行壓縮，留下首尾節點（可以調整首尾節點的數量），可見list結構不支持順序檢索、但是存儲密度大、只需對首尾進行操作；

set集合底層使用dict字典數據結構，數據包含多個內容，比如Sadd text 01,02,03，這里就插入01、02、03三個數，顯然01、02、03數據的結構不是一個鍵值對，所以使用dict時會保留鍵，而將值置空；

zset底層使用跳表和dict數據結構實現，跳表用于根據score進行范圍查詢，通過key查value(對應score)就需要使用到dict。同時需要注意zset的鍵唯一性是由dict實現的；

最后hash由dict實現沒什么好說的。