5種基本數(shù)據(jù)結(jié)構(gòu)
redis用ANSI C實(shí)現(xiàn)
string，list，hash，set，zset
String VS ArrayList
redis String使用最廣泛，用法和map差不多，set和get
底層數(shù)據(jù)結(jié)構(gòu)是動(dòng)態(tài)數(shù)組，類java的ArrayList
預(yù)分配一定空間，超過(guò)capacity之后擴(kuò)容，如果字符串長(zhǎng)度小于1M，每次擴(kuò)容翻倍，超過(guò)1M每次擴(kuò)容1M，最大長(zhǎng)度512M
Redis字符串是“SDS”(simple dynamic String)
struct SDS<T> {
T capacity; // 容量，len和capacity 來(lái)控制擴(kuò)容
T len; // 長(zhǎng)度
byte flags; // 特殊標(biāo)記位
byte[] content; // value
}
注意： 這里長(zhǎng)度是T，泛型，而不是int
原因： redis內(nèi)存做了極致優(yōu)化，在內(nèi)容很小的時(shí)候，長(zhǎng)度可以用short和byte表示。
- embstr VS raw
- redis內(nèi)部的兩種字符串存儲(chǔ)形式（編碼方式），raw和embstr，內(nèi)容很短用embstr，超過(guò)44字節(jié)，使用raw。
- 為什么是44，因?yàn)閮?nèi)存分配malloc是64，為了保證連續(xù)，redis數(shù)據(jù)結(jié)構(gòu)有一部分留給頭結(jié)構(gòu)（19字節(jié)，尾結(jié)構(gòu)1字節(jié)）。【embstr的頭和content一體】，所以一次分配剩下44字節(jié)可用。超過(guò)之后認(rèn)為不適合用embstr存儲(chǔ)。
List VS LinkedList
簡(jiǎn)單理解：相當(dāng)于java中的linkedList，因?yàn)槭擎湵?，所以插入和刪除比較快
-
深入理解：應(yīng)該是quicklist的一個(gè)結(jié)構(gòu)
- 在數(shù)據(jù)很少的情況下，是一塊連續(xù)的內(nèi)存，ziplist（省去前后指針的空間）
- 數(shù)據(jù)很多的情況下是quicklist，是多個(gè)ziplist用前后指針相連
- image.png
單個(gè)ziplist長(zhǎng)度上限通常是 8KB（由配置參數(shù)指定）
當(dāng)元素都是整數(shù)且個(gè)數(shù)較少的時(shí)候，用intset數(shù)據(jù)結(jié)構(gòu)，比ziplist還要省空間。
Hash VS HashMap
redis的hash是：數(shù)組 + 鏈表（hashmap是數(shù)組 + 鏈表 + 紅黑樹）
redis的hash是漸進(jìn)式rehash，保留新舊兩個(gè)結(jié)構(gòu)，慢慢去hash（性能更好）
注意，redis中hash是一個(gè)字典，整個(gè)redis數(shù)據(jù)庫(kù)的key-value也有一個(gè)全局字典，這就是為什么string用起來(lái)和hash差不多，另外，帶過(guò)期事件的key也是一個(gè)字典，zset中存儲(chǔ)value和score的映射關(guān)系也是字典。
-
hash攻擊
- 黑客利用hash算法的偏向性，讓所有插入碰撞，導(dǎo)致查詢效率從O(1)退化為O(n)，性能降低的一種攻擊方式。
Set VS HashSet
- redis的set結(jié)構(gòu)的底層也是字典，不過(guò)所有的value都是null
ZSet
- 內(nèi)部實(shí)現(xiàn)是 skipList
- 類似于java的sortedSet和hashMap
