目錄
1.字元串（string）
1.1 redis的字元串類型：
1.2 string的編碼方式有三種:
1.3 string的預配置設定空間機制;
1.4對比C語言的字元串優點：
1.5 string的使用場景：
2.連結清單（list）
2.1 redis3.2版本之前連結清單結構：
2.2 redis3.2版本之前ziplist轉化為linklist條件 ：
2.3 linklist結構：
2.3.1 linklist缺點:
2.4 ziplist結構：
2.4.1 ziplist資料結構定義：
2.4.2 ziplist的連鎖更新問題：
2.4.3 ziplist使用場景：
2.5 redis版本3.2後的quicklist（快速連結清單）：
2.5.1 quicklist相關結構:
2.5.2 注意quicklist的插入：
2.5.3 quicklist的優點：
2.6 list應用場景：
3.哈希（hash）
3.1 hash資料結構：
3.2 hastable的實作：
3.3 hashtable如何解決hash沖突：
3.4 rehash過程:
3.4.1 觸發條件:
3.4.2 擴容過程：
3.4.3 擴容的意義：
3.5 hash應用場景：
4.無序集合（set）
4.1 set的資料結構：
4.2 使用intset結構的條件：
4.3 intset結構屬性：
4.4 intset更新過程；
4.5 intset優缺點:
4.6 set應用場景：
5 有序集合（zset）
5.1 zset的資料結構：
5.2 使用skiplist的條件：
5.3 skiplist結構：
5.4 skiplist查找過程：
5.5 skiplist的插入過程：
5.6 删除過程：
5.7 修改過程：
5.8 skiplist的優點：
5.9 zset的應用場景:
6. bitmap定義：
6.1 bitmap的優點：
6.2 bitmap的使用場景：
7. HyperLogLog定義：
7.1 HyperLogLog的使用場景：
8. GEO定義:
總結：
redis是由C語言編寫的,是以鍵值對(K-V)的方式來存儲資料，K的資料類型為字元串（string）類型，V的值則為下文中的5種資料類型
1.字元串（string）
1.1 redis的字元串類型：
是由SDS（simple dynamic string） 來實作的。
結構定義：
struct sdshdr{
int len; //buff中已使用的空間
int free; //buff中未使用的空間
char buff[]; //資料空間
}
1.2 string的編碼方式有三種:
int（整數類型，直接用redisObject存儲）, raw(大于39位元組長度) , embstr（小于等于39位元組長度）(redis 4.0之前的版本)
redisObject{
unsigned type : 4 //string ,list,hash,set,zset(4位 = 0.5位元組)
unsigned econding: 4 //redis内部編碼類型，如：hashtable,sds,ziplist skiplist等 （4位 = 0.5位元組）
unsigned lru ：//記錄對象最後一次被通路的時間（24位 = 3位元組）
int refcount: //用來記錄被使用的次數，當值為0時，則可回收空間 （32位 = 4位元組）
void *pre: //如果是int類型 則存儲值，如果是其它類型則存儲指向資料的指針（8位元組）
}
使用重點提示：在高并發的情況下，盡量使其長度小于等于39位元組，采用embstr類型，字元串SDS和redisObject一起配置設定（同時建立redisObject,sdshdr對象,配置設定空間連續），進而隻需要一次記憶體操作（raw需要2次），減少建立redisObject的記憶體配置設定次數來提高性能
知識點提示：39位元組長度 = embstr最小配置設定64位元組 - len free 8位元組 - /0 1個位元組（結束字元） - redisObject（16位元組）（
版本提示：在redis 5.0 後39位元組 -> 44 位元組，優化了SDS小記憶體使用,因為unsing int 可以表示很大的範圍，但是對于很短的sds則浪費了2個unsigned int（8個位元組的空間）
優化後為： struct __attribute__((_packed__)) sdshdr8(還有16，32, 64的使用){
uint8_t len;
uint8_t alloc；
unsigned char flags;
char buff [];
}
知識點提示：44位元組 = (變動)原來的len 8個位元組 - （uint8_t len uint8_t alloc unsigned char flags）3個位元組 + 39位元組
1.3 string的預配置設定空間機制;
在修改SDS時，會先檢查空間是否足夠，不足的會盡行擴容，防止緩沖區溢出。
擴容：當小于1M的時候，采用空間翻倍+1M，當大于1M，則每次+1M，上限為512M
縮短的時候，也不會立即縮短，而是采用惰性釋放空間，采用對應的API來釋放
1.4對比C語言的字元串優點：
使用起來更友善，C語言要碰到結束/0标志才用停止。
防止記憶體空間溢出，在使用之前會檢查空間大小
預配置設定空間機制
1.5 string的使用場景：
緩存，session共享，限流，計數器
2.連結清單（list）
2.1 redis3.2版本之前連結清單結構：
ziplist（壓縮清單）,linklist（雙向連結清單），redis3.2版本後使用quicklist（快速連結清單）
建立新清單時預設優先采用ziplist，節省記憶體空間
2.2 redis3.2版本之前ziplist轉化為linklist條件 ：
一：新添的字元串長度大于64位元組。二：鍵值對數量大于512，則會由redis_encoding_ziplist編碼轉換成redis_encoding_linklist編碼。以上2個條件的值在redis.conf中 list-max-ziplist-value 64 list-max-ziplist-entries 512可更改
2.3 linklist結構：
linklist是雙向連結清單，Node節點包含prev，next指針，使其可以雙向周遊，同時list還儲存了head，tail兩個指針，使其對于連結清單頭部與尾部的進行插入的操作複雜度都為O(1)，使用lpush,rpop指令具有高效性
連結清單節點:
struct listNode{
struct listNode *prev; //前置指針
struct listNode *next;//後置指針
void *value;//節點的值
}listNode;
連結清單：
struct list{
lsitNode *head;//表頭節點
listNode *tail; //表尾結點
unsigned long len; //連結清單節點數量
void *(*dup)(void *ptr);//節點值複制函數
void (*free)(void *ptr);//節點值釋放函數
int (*match)(void *ptr,void *key); //節點值對比函數
}
2.3.1 linklist缺點:
附加空間太高，prev next指針就占了16個位元組，每個節點的記憶體都是單獨配置設定的，容易産生記憶體碎片
2.4 ziplist結構：
是特殊編碼的連續記憶體塊組成的順序存儲結構，包含多個節點(entry)，每個節點都可以用來存儲一個整數或者一個字元串。
ziplist是通過上一個entry的長度 + 目前entry的長度來推算下一個entry的位置，犧牲讀性能，來擷取更低的記憶體空間的使用，存儲短字元串存儲指針比存儲entry長度更費記憶體，典型的“時間換空間”
2.4.1 ziplist資料結構定義：
zlbytes：unit32_t zilplist的長度（位元組）是一個32位的無符号整數，表示整個ziplist占用的記憶體位元組數，對ziplist進行記憶體重配置設定跟計算末端時使用
zltail：unit32_t 到達ziplist表尾結點的偏移量，通過這個偏移量，可以直接彈出表尾結點。
zilen：unit16_t iplist節點的數量，當值小于UINT16_MAX(65535) 就是節點數量，等于時，需要周遊整個ziplist才能計算出
entry: 節點 ，長度由内容決定 =zlentry
zllend‘：标記ziplist的末端
知識點提示：entries才是存儲節點的區域
typedef struct zlentry{
unsigned int preverawlensize,prevrawlen;// prevrawlen表示前一個節點的長度，preranlensize表示prevrawlen長度用1或者5位元組表示
unsigned int lensize, len ;//len表示目前節點的長度 lensize表示 目前節點所需位元組大小
unsigned int headersize// 表示目前節點header大小
unsigned char encoding;//節點的編碼方式
unsigned char *p//指向節點的指針
}zlentry
如何通過一個節點找到另一個節點？ 通過使用目前指針-前一個entry的長度，就可以擷取指向另一個節點的位址
zlentry中屬性值的作用：
prevrawlen：記錄前一個節點的所占用的位元組數，可以計算目前節點的前一個節點的位址，可以用來表尾向表頭節點周遊。
len/encoding：記錄目前content占有的記憶體位元組數及存儲類型，用來解析content
content：儲存了目前節點的值
prevrawlen：如果前一個節點prevranlen長度小于254位元組 則值為1。如果大于等于，那麼 将第一個位元組設定為254，後4個位元組用來表示實際長度
2.4.2 ziplist的連鎖更新問題：
在ziplist中，zlentry都會儲存上一個節點的長度prevrawlen，假設新插入了一個節點長度254，而下一個節點的長度為253，就會導緻由原來給的1位元組變為5位元組，使得下一個節點的整體長度發生改變，進而又影響到了下下節點，以此類似，會導緻想多米諾骨牌一樣發生連鎖更新反應，産生空間再配置設定。
2.4.3 ziplist使用場景：
資料量小的情況下，不适合修改操作。
2.5 redis版本3.2後的quicklist（快速連結清單）：
quicklsit實際上是ziplist跟linklist的混合體，結合了雙方的優點，是一個ziplist組成的雙向連結清單，quicklist分成N個quicklistNode中包含ziplist，prev，next.
未壓縮時結構圖
壓縮後(LZF算法)的結構圖
2.5.1 quicklist相關結構:
typedef struct quicklist {
quicklistNode *head; //指向頭節點的指針
quicklistNode *tail;//指向尾結點的指針
unsigned long count;//所有ziplist資料的個數總和
unsigned long len;//quicklist節點個數
int fill : 16;//ziplist中entry能儲存的數量,由list-max-ziplist-size配置項控制
unsigned int compress : 16//壓縮深度,由list-compress-depth配置項控制
}quicklist;
typedef struct quicklistNode{
struct quicklistNode *prev;//前節點指針
struct quicklistNode *next;//後節點指針
unsigned char *zl;//資料指針，目前節點如果沒有壓縮則指向ziplist結構，如果壓縮了，則指向quicklistLZF;
unsigned int sz; //指向ziplist實際占用的記憶體大小，即使壓縮了也是指向壓縮前的大小
unsigned int count：16 ;// ziplist包含的資料項個數
unsigned int encoding:2; //ziplist是否壓縮 1 ：ziplist ， 2：quicklistLZF
unsigned int container:2;//存儲類型，2表示使用ziplist存儲
unsigned int recompress : 1; //檢視已經壓縮後的資料，用來标記暫時解壓，後期再進行壓縮
unsigned int attemped_compress:1;
unsigned int extra :10;
}quciklistNode;
typedef struct quicklistLZF{
unsigned int sz; //壓縮後的ziplist大小
char compressed[];//柔性數組，用來存放壓縮後的ziplist位元組數組
}quicklistLZF;
2.5.2 注意quicklist的插入：
當要插入的資料沒有超過限制的大小時，則直接插入
當插入的資料大于要插入的ziplist位置時，如果相鄰的quicklist連結節點的ziplist沒有超過限制大小那麼就轉為插入相鄰quicklistNode的ziplist中，
當插入的資料大于要插入的ziplist位置時，如果相鄰的quicklist連結節點的ziplist也超過限制大小時，則建立一個quicklistNode插入
2.5.3 quicklist的優點：
中和了linklist，ziplist的優點，進一步的壓縮了清單，提高了性能。
2.6 list應用場景：
消息隊列，排行榜，評論清單，點贊清單
3.哈希（hash）
3.1 hash資料結構：
hashtable ，ziplist（上文已有說明）
當哈希對象儲存的鍵值對小于512，字元串長度小于64位元組時，使用ziplist，反之則使用hashtable
3.2 hastable的實作：
是由一個dict的結構體，類似hashmap中的資料結構
typedef struct dict {
dictType *type; //類型函數
void *privdate;//私有資料
dictht ht[2]; //哈希表
int rehashidx//rehash索引 當rehash不在進行時 = -1 ，正在進行時為0
} dict;
struct dictht{
dictEntry **table; //哈希數組
unsigned long size; //哈希表大小
unsigned long sizemask;/掩碼，用于計算索引值 = size -1
unsigned long used;//已有節點數量
}dictht;
struce dictEntry{
void *key; //key值
union{ //value值
void *val; //指針
unit64_tu64; //整數
int64_ts64;//整數
}v;
struct dictEntry *next; //下一個節點的指針
}dictEntry；
3.3 hashtable如何解決hash沖突：
取決于hash函數，需要均勻分布。redis預設的函數是siphash，均勻分布，性能佳。當出現hash沖突時，會采用數組+連結清單的方式來解決，被分到同一個哈希桶上的多個哈希表節點用next指針構成一個單連結清單，時間複雜度O（n）。
3.4 rehash過程:
3.4.1 觸發條件:
負載因子 = 哈希表已儲存的節點數量/哈希表大小
load_factor = ht[0].used/ ht[0].size
一，當負載因子大于等于1時，并且沒有執行bgsave或者bgrewriteaof指令，即沒有執行RDB快照或者沒有進行AOF的重寫。二：當負載因子大于等于5時，就會強制rehash
提示：當負載因子小于0.1時，執行收縮操作
3.4.2 擴容過程：
在将ht[0]的所有鍵值對移到ht[1]中時，采用的漸進式的rehash，防止資料量大的時候，會影響伺服器的使用。
在擴容期間，dict.rehashidx= 0，删改查的操作會同時作用在ht[0],ht[1]兩張表中，查找時會優先查找ht[0],找不到就到ht[1]中找，增加的操作隻會出現在ht[1]中,随着rehsh操作，将dict.dictht[0].table中的每個dictEntry重新計算哈希值跟索引值，移到dict.dictht[1].table中，知道dict.dictht[0].used = 0時，表示rehash完畢.ht[0]會變成空表，并将ht[1]設定為ht[0],重新建立一個ht[1],為下一次擴容做準備，rehashidx值變為-1.
擴容大小：當初始化，dict.dictht[0].table時，會将容量增大到 DICT_HT_INITIAL_SIZE會擴容到4個，其它情況，會擴容到dict.dictht[0].used*2的2^n
3.4.3 擴容的意義：
在哈希沖突增多的情況下，時間複雜度由O(1) -> O(n)，擴容的意義就是将時間複雜度逐漸趨于O(1)
3.5 hash應用場景：
使用者資訊，購物車
4.無序集合（set）
4.1 set的資料結構：
hashset（上文已有說明） intset
4.2 使用intset結構的條件：
集合儲存的所有元素都是整數值，儲存的元素數量不超過512個
4.3 intset結構屬性：
typedef struct intset{
unit32_t conding;//編碼方式 三種：INTSET_ENC_INT16 INTSET_ENC_INT32 INTSET_ENC_INT64
unit32_length;//集合包含的元素數量
int8_t contents[]; //儲存元素的數組，從小到大有序排列，不包含重複值 ,時間複雜度為O(1)
}intset;
提示：intset存儲的資料是有序的，查找的時候是通過二分查找來實作的
4.4 intset更新過程；
當要新增的元素已經超過設定的編碼方式時，就發生整數的更新過程.
首先了解舊的編碼方式，
然後确定新的編碼方式計算出要新增的記憶體大小，将新元素從尾部插入，
根據新的編碼方式，将之前的值充值，contents存在2種編碼格式設定的值，需要統一，從新插入的元素位置開始，從後向前（防止資料被覆寫）将之前的資料按照新的編碼方式來移動和設定。
4.5 intset優缺點:
優點：節省記憶體，隻在需要更新的時候進行更新操作 缺點：更新過程耗費資源，而且不支援降級
4.6 set應用場景：
交集，并集，差集，交友圈，社交圈，點贊，收藏
5 有序集合（zset）
5.1 zset的資料結構：
ziplist(上文已有說明) skiplist（跳表）
5.2 使用skiplist的條件：
有序集合的元素數量小于512，有序集合的元素長度小于64位元組時使用ziplist，否者使用skiplist
5.3 skiplist結構：
是一個有序的資料結構。它通過在每個節點中維持多個指向其它節點的指針，進而打到快速通路節點的目的，類似于二分查找，時間複雜度最快O(logn)，最慢0（N）。
typedef struct zskiplist{
struct zskiplistNode *header,*tail;//頭尾指針
unsigned long length;//節點數量
int level;//表中最大的節點的層數
}zskiplist
提示：可以通過以上屬性來快速找到頭尾節點，最大節點層數，實作時間負責度O(1)
type struct zskiplistNode{
sds ele;//節點存儲的具體指
double score;//節點對應的分值，節點都按照分值從小到大排序
struct zskiplistNode *backward//前向指針
struct zskiplistLevel{
struct zskiplistNode *forward; //每一層的後向指針
unsigned long span;//到下一個節點的跨度
}level[]; //雙向連結清單
}zskiplistNode;
提示：多個節點的分值可以相同，但是節點的成員對象必須唯一，然後按照對象的大小進行排序，對象小的排在前面（靠近表頭的方向），對象大的排在後面（靠在表尾的方向）。
資料結構圖
5.4 skiplist查找過程：
采用連結清單是想要保值修改時間複雜度低，那麼查找過程的時間複雜度如何優化呢？故而出現了跳表，類似于二分查找的實作思想。隻要保證整體上二分之一的機率就行，不用保證兩兩層級之間二分之一的機率
假設要找score為5的元素。
（1）首先從頭結點的最高層（也就是64層）開始查找，但是由于頭指針中儲存了目前跳表的最高層數，是以直接從頭結點的level層開始查找即可。如果zkiplistLevel的forward為NULL，則繼續向下。
（2）直到頭結點中第5層的zskiplistLevel的forward不為空，它指向了第6個節點的第5層，但是這個節點的score為6，大于5，是以還要從頭結點向低層繼續查找。
（3）頭結點中第4層的zskiplistLevel的forward指向第3個節點的第4層，這個節點的score為3，小于5，并且第一個節點的span=2，這個span的作用就是用來累加并計算最終目标節點的排名的。繼續從這個節點的forward向後周遊。它的forward指向第6個節點的第4層，這個節點的score為6，大于5，是以還要從前一個score為3的節點向低層繼續查找。
（4）第3個節點第3層的zskiplistLevel的forward指向第5個節點的第3層，而它的score正好為5，查找成功。并且第3個節點的span=2，再加上原來的span=2等于4，是以目标節點5的排名是4。
5.5 skiplist的插入過程：
（1）插入節點時，會随機配置設定一個小于64的層數，層數越小機率越大，層數越高機率越小
（2）查找小于待插入score分數值中最大的那個節點，如果score相同，則比較對象大小
（3）在找到的節點後面插入新的節點，同時更新前面節點的跨度跟跳表的最大層高
(4) 更新新節點的各層forward和backward指針
5.6 删除過程：
（1）（2）找位置方式同上
（3）找到待删除的節點，删除節點，更新前面節點的跨度跟跳表最大層高
（4）更新被删除的節點各層的forward和backward指針
5.7 修改過程：
找到要修改的節點位置，直接删除，然後插入修改後的新的節點
5.8 skiplist的優點：
并不是特别耗記憶體，隻要通過調整節點到更高level的機率，就能做到比B樹更少的記憶體消耗
sorted set可能會面對大量的zrange和zreverange操作，跳表作為單連結清單周遊的實作性能亞于其它平衡樹
實作和調試更簡單
5.9 zset的應用場景:
實時排行榜
6. bitmap定義：
-又稱位圖，以位為機關的存儲，内部還是采用String類型（最大長度為512M）存儲（上限為2^32），可以了解為一個bit數組來存儲特定資料的一種資料結構
6.1 bitmap的優點：
節省記憶體，适合處理大資料。可以實作快速排序，去重，快速查詢是否存在（布隆過濾器），能友善的通過位預算（AND,OR,XOR,NOT）高效對多個bitmap資料進行處理
6.2 bitmap的使用場景：
活躍使用者線上狀态，活躍使用者統計，使用者簽到等場景，适合大量的使用者，幾千萬上億級别
實時分析，存儲與對象ID相關的資訊
7. HyperLogLog定義：
-估算基數統計的算法，是LogLog算法的更新，在redis中實作HyperLogLog，隻需要12k記憶體就能統計2^64個資料，存在一定的誤差，誤差率在0.81%
7.1 HyperLogLog的使用場景：
可以用來統計頁面實時UV，注冊IP數，每日通路IP數，
8. GEO定義:
-資訊定位功能，支援存儲地理位置資訊，實作諸如附近位置、搖一搖這類依賴于地理位置資訊的功能
總結：
根據自己的需要查閱多方資料，參考多為大佬的心得所寫，記錄下來，以便後面随時再複習一遍。