1.簡(jiǎn)單動(dòng)態(tài)字符串
每個(gè)sds.h/sdshdr結(jié)構(gòu)表示一個(gè)SDS值，Redis是C語(yǔ)言寫的。
與C字符串的區(qū)別：
常數(shù)復(fù)雜度獲取字符串長(zhǎng)度
杜絕緩沖區(qū)溢出
C字符串不記錄長(zhǎng)度，如果兩個(gè)C字符串前后緊挨在一起，這時(shí)候擴(kuò)展前字符串時(shí)，后字符串就會(huì)被覆蓋。
- 減少修改字符串時(shí)內(nèi)存重分配的次數(shù)
結(jié)構(gòu)體的free，就是處理分配的空間大小，如果你要擴(kuò)展的話，可以探索是否有足夠空間，夠的話直接修改free，不夠再重分配，縮短一定不用重分配了，直接縮短就行了。
二進(jìn)制安全
兼容部分C字符串函數(shù)
2.鏈表
鏈表廣泛運(yùn)用與Redis的各個(gè)功能，例如：列表鍵、發(fā)布與訂閱、慢查詢、監(jiān)視器等。
3.字典
(1) 結(jié)構(gòu)體
字典所使用的的哈希表結(jié)構(gòu)：
我們存進(jìn)去的hash鍵值對(duì)是哈希表的節(jié)點(diǎn)
字典的結(jié)構(gòu)體：
整個(gè)關(guān)系是：字典>哈希表>鍵值對(duì)
(2)存入過(guò)程
先計(jì)算鍵值對(duì)的哈希值，根據(jù)哈希值模哈希表的節(jié)點(diǎn)數(shù)，得出鍵值對(duì)存入哪個(gè)節(jié)點(diǎn)中。解決哈希沖突的方法是拉鏈法
當(dāng)鍵值對(duì)越來(lái)越多的時(shí)候，為了維持負(fù)載因子在一定量，會(huì)進(jìn)行rehash操作。rehash過(guò)程采用的是漸進(jìn)式rehash
4.跳躍表
一種有序數(shù)據(jù)結(jié)構(gòu)，它通過(guò)在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其他結(jié)點(diǎn)的指針，從而達(dá)到快速訪問(wèn)節(jié)點(diǎn)的目的。
跳躍表支持平均Ologn，最壞On復(fù)雜度的查找復(fù)雜度，跳表實(shí)現(xiàn)比平衡二叉樹簡(jiǎn)單。
跳表只在有序集合鍵使用到了
(1)跳表的實(shí)現(xiàn)
跳表用了兩個(gè)結(jié)構(gòu)體定義，相對(duì)復(fù)雜的是節(jié)點(diǎn)的結(jié)構(gòu)體定義。
跳躍表節(jié)點(diǎn)
每個(gè)節(jié)點(diǎn)都有一個(gè)數(shù)組，我們稱作層，每一層都可以直接指向其他節(jié)點(diǎn)，只要層越多，訪問(wèn)節(jié)點(diǎn)速度越快。
每層都有一個(gè)前進(jìn)指針，還有個(gè)跨度，前進(jìn)指針用來(lái)指向下一個(gè)節(jié)點(diǎn)，跨度記錄前進(jìn)指針跨了幾個(gè)節(jié)點(diǎn)。
5.整數(shù)集合
數(shù)據(jù)結(jié)構(gòu)如圖：
整數(shù)集合是個(gè)集合，所以不會(huì)有重復(fù)值，只存放整數(shù)int8、int32、int64；
整數(shù)集合底層實(shí)現(xiàn)是個(gè)數(shù)組contents，而且排好序的
contents的類型不是int8，真正的類型是由encoding的值決定的。
升級(jí)與降級(jí)
升級(jí)過(guò)程：
1）根據(jù)新元素的類型，擴(kuò)展數(shù)組底層的空間大小，并為新元素分配空間；
2）將底層數(shù)組的所有元素?fù)Q成對(duì)應(yīng)的類型，并保證有序性的情況下放在正確的位置上；
3）將新元素放入底層數(shù)組中；
升級(jí)的好處：
提升靈活性
節(jié)約內(nèi)存
降級(jí)：整數(shù)集合不支持降級(jí)操作，一旦升級(jí)就不會(huì)降級(jí)。
6.壓縮列表
壓縮列表是列表鍵與哈希鍵的底層實(shí)現(xiàn)之一；
壓縮列表的結(jié)構(gòu)包括：zlbytes、zltail、zllen、entrys；其中entrys是個(gè)列表，zlbyte表示整個(gè)壓縮列表的大小，zltail是從壓縮列表首地址到最后一個(gè)entry的地址偏移量；
-
entry由previous_entry_length、encoding、content組成，其中：
- previous_entry_length保存上一個(gè)entry的長(zhǎng)度，大小有1字節(jié)或者5字節(jié)，可用這個(gè)值來(lái)計(jì)算上一個(gè)節(jié)點(diǎn)的首地址
encoding記錄了content的類型以及長(zhǎng)度
連鎖更新：我們往一個(gè)壓縮列表的首節(jié)點(diǎn)插入一個(gè)大于254字節(jié)的節(jié)點(diǎn)，這時(shí)，后面的那個(gè)節(jié)點(diǎn)的previous_entry_length就要從1字節(jié)編程5字節(jié)，這時(shí)就需要重分配內(nèi)存，而重分配后，該節(jié)點(diǎn)后一個(gè)結(jié)點(diǎn)的previous_entry_length也要從1字節(jié)變成5字節(jié)，會(huì)導(dǎo)致連鎖更新。
