redis中使用的數(shù)據(jù)結構有:
dict 字典,就是個哈希表,實現(xiàn)和HashMap類似,不做闡述;不同的是在哈希表resize()的時候是分步執(zhí)行的,后續(xù)篇幅再說明沿量。
sds 很多項目都對自己的字符串進行了封裝,作用類似于leveldb的slice。
linkedlist 雙端鏈表，迭代器的實現(xiàn)是通過鏈表的pre和next實現(xiàn)的，是個BidirctionalIterator和敬。代碼中只實現(xiàn)了ForwardIterator的功能寡键。
zipmap 已不再使用了
inset 一個緊致的有序整型數(shù)組。
ziplist 也是一個鏈表况既，但是它的內存是連續(xù)的，在數(shù)據(jù)量小的時候使用闸婴，增長到一定的大小會轉化成list或者skiplist
skiplist 跳躍表坏挠，實現(xiàn)在t_zset.c中
本文只闡述inset，ziplist邪乍，skiplist三種數(shù)據(jù)結構降狠。
1.ziplist
直接借用代碼注釋上ziplist的存儲結構：
/*
area |<---- ziplist header ---->|<----------- entries ------------->|<-end->|
size 4 bytes 4 bytes 2 bytes ? ? ? ? 1 byte
+---------+--------+-------+--------+--------+--------+--------+-------+
component | zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
+---------+--------+-------+--------+--------+--------+--------+-------+
^ ^ ^
address | | |
ZIPLIST_ENTRY_HEAD | ZIPLIST_ENTRY_END
|
ZIPLIST_ENTRY_TAIL
- zlbytes 記錄了整個ziplist占用的內存大小庇楞；
- zltail 記錄尾節(jié)點的相對于ziplist實例指針的偏移量榜配；
- zllen 是整個list的節(jié)點數(shù)量的無符號數(shù)，占2個字節(jié)吕晌，可以最大表示2**16-1蛋褥，實際使用保留了0xffff ffff ,即大于等于這個數(shù)的時候，已經不能通過此值來取得節(jié)點的數(shù)量了睛驳；
- zlend 固定為0xff烙心。
- entry 的結構并不是代碼中給的結構體zlentry。而是如下結構:
size 1/5 bytes 1/2/5 bytes ?
+---------------+---------------+-------+
component | pre_entry_len | cur_entry_len | value |
+---------------+---------------+-------+
這是個變長的結構乏沸，pre節(jié)點小于254則pre_entry_len占用1字節(jié)淫茵，否則5字節(jié),為什么不是255字節(jié)呢？255會和zlend產生沖突蹬跃；cur_entry_len中包含了編碼信息（以字符串編碼還是數(shù)字匙瘪，數(shù)字編碼能減少內存長度)和本節(jié)點的長度信息,數(shù)字格式編碼固定占用1字節(jié)；字符串格式編碼數(shù)據(jù)小于127字節(jié)占1字節(jié)蝶缀，小于0x3fff 占用2字節(jié)丹喻，否則5個字節(jié)。
因此ziplist有如下特點:
- 內存連續(xù)翁都，數(shù)據(jù)緊湊碍论。
- 查找效率o(n)
- 雙端查詢，可前后遍歷荐吵，類似于nodelist.
了解了數(shù)據(jù)結構骑冗，思考下如何對其增加一個節(jié)點p赊瞬，p的大小為sp。
- 1.ziplist長度發(fā)生變化贼涩，zlbytes要增加entry的內存大星山А；
- 2.zltail也要做相應改變遥倦，如果插入的是尾節(jié)點谤绳，則zltail等于ziplist到新節(jié)點p的距離，否則是原值加上新節(jié)點p的長度袒哥。
- 3.內存大小發(fā)生改變缩筛，需要realloc個更大的內存。
- 4.對于在新節(jié)點以后的節(jié)點堡称，后移sp個單位瞎抛。接下來要更新p以后的節(jié)點內容:
- 4.1如果p的前一個節(jié)點的長度和p節(jié)點的長度一樣長，那么皆大歡喜却紧。只需要更新p節(jié)點后一個節(jié)點的pre_entry_len值桐臊；
- 4.2如果比p節(jié)點的長度大(5字節(jié)對1字節(jié))，也ok晓殊，存下來断凶，浪費4個字節(jié)內存。
- 4.3如果比p節(jié)點的長度小(1字節(jié)對5字節(jié))巫俺，意味著p以后的節(jié)點長度會發(fā)生變化认烁，增加4個字節(jié)來存儲p的長度，zltail和ziplist也要同時加4;同時由于p->next節(jié)點長度發(fā)生變化介汹，p->next->next也要去做一次判斷却嗡，需要重復步驟4，直到不滿足4.3的情況為止嘹承。
經過以上步驟稽穆，就可以大概還原redis中的代碼實現(xiàn)了，也可以看出來ziplist的增刪代價是很大的赶撰，改變一個節(jié)點的復雜度最差是（n^2);一個節(jié)點改動，可能牽一發(fā)而動全身柱彻，所以ziplist是不適合大數(shù)據(jù)量的存儲的豪娜。
2.inset
inset 實際是一個整數(shù)數(shù)組，結構如下:
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;
其中encoding是編碼方式哟楷，有16位瘤载，32位，64位三種取值卖擅；length是inset集合中保存的元素個數(shù)鸣奔，contents為保存的數(shù)據(jù)墨技。下面是inset的特點和實現(xiàn)方式.
1.初始化的inset是16位編碼的，如果inset里面只保存了16位的數(shù)字挎狸，那么這個編碼方式將保持不變扣汪。
2.inset是有序不重復的，從小到大排列锨匆，每次插入/刪除會觸發(fā)inset的大小調整,length+1崭别。
3.如果插入了比當前編碼范圍更大的數(shù)字，會觸發(fā)intsetUpgradeAndAdd()恐锣，下面以16位-> 32位擴展為例茅主。
3.1 重新調整contents大小，大小為原(size+1)*2土榴，更新encoding的值為INTSET_ENC_INT32;
3.2 新數(shù)字肯定是位于數(shù)組開頭或者結尾诀姚，如果是在結尾，將原數(shù)組的每個數(shù)從原位置pos移到pos2的位置玷禽，否則是(pos+1)2赫段；
3.3 插入新的數(shù)據(jù)，intsetUpgradeAndAdd()過程結束
4.刪除不改變inset的編碼方式论衍，即如果原inset為32位瑞佩，刪光了inset里的16位不能表示的數(shù)字以后，inset也不會恢復到16位坯台，代價太大炬丸，即intsetUpgradeAndAdd()的過程是不可逆的。
5.在inset中查找一個數(shù)采用二分查找蜒蕾。
根據(jù)這些特點稠炬，寫出inset的實現(xiàn)，想必不難咪啡，inset的特點是在存儲的數(shù)據(jù)為小值的時候首启，占用的內存較小，但是只要插入了一個64位的數(shù)據(jù)撤摸，那么inset就沒有優(yōu)勢了毅桃，插入和刪除的時間復雜度都是o(n)，因此不適合做大數(shù)量的存儲准夷。
3.skiplist
跳表是一個特殊的有序鏈表钥飞，盜一張網(wǎng)圖吧。
結構如下
typedef struct zskiplist {
// 表頭節(jié)點和表尾節(jié)點
struct zskiplistNode *header, *tail;
// 表中節(jié)點的數(shù)量
unsigned long length;
// 表中層數(shù)最大的節(jié)點的層數(shù)
int level;
} zskiplist;
節(jié)點的結構
typedef struct zskiplistNode {
// 成員對象
robj *obj;
// 分值
double score;
// 后退指針
struct zskiplistNode *backward;
// 層
struct zskiplistLevel {
// 前進指針
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
簡述下跳表的特點
- 跳表是一個排序鏈表衫嵌，redis中以score的大小做排序读宙，增刪改查的效率均是o(logn)，由于其實現(xiàn)更易于理解和實現(xiàn)而被廣泛使用楔绞。
- 跳表是不穩(wěn)定的结闸，即同樣是創(chuàng)建一個跳表唇兑，插入若干相同的值，內部的數(shù)據(jù)結構可能是不一致的桦锄。
- 每個節(jié)點的大小不固定扎附，不固定的原因是節(jié)點的擁有的forward指針個數(shù)不定，這個數(shù)值是在節(jié)點創(chuàng)建的時候隨機選取的一個正整數(shù)察纯，redis實現(xiàn)默認最大層數(shù)是32帕棉。
- redis中的跳表增加了一個指向前節(jié)點的backward來往前遍歷;一個span，用于計算forward節(jié)點和本節(jié)點中間的跨度饼记，以方便zcount等命令來計算范圍內score的數(shù)量香伴。
如何插入一個數(shù)據(jù)?redis排序順序是從頭到尾，按照score從小到大具则。如果要增加一個值即纲，首先需要確定插入后的順序，假設跳表為skl 博肋，新節(jié)點為n低斋。
- 找到每一層比新節(jié)點score小，而且距離最近的節(jié)點匪凡，保存為update[]膊畴。
- 隨機產生新節(jié)點的層高眉反，對每一層的forward節(jié)點復制崭参，令n->level[i]->forward = update[i]->level[i]->forward，給新節(jié)點的所有forward指針賦值层坠。令update[i]->forward = n使新節(jié)點和其所有前置節(jié)點關聯(lián);實際上和雙向鏈表操作類似衬衬。
如何查找一個節(jié)點p?
場景1.根據(jù)score范圍查找內容买猖，對應zrange命令。查找左界和右界滋尉，中間的范圍及所求玉控。左界和右界算法類似，從head的頂層forward節(jié)點開始狮惜，如果比p的score小高诺，那么讓head = forward 繼續(xù)此步驟.如果等于score那么返回。如果小于那么代表需要找的左界在head和forward之間碾篡，跳到下一層重復此步驟懒叛。
場景2.根據(jù)內容查找score，對應zscore命令耽梅。redis不查找skiplist，而是額外使用了個hash表來達到o(1)的效率胖烛。
迭代器如何設計?
- 可知n->level[0]->forward的步長是1眼姐，循環(huán)forward可以遍歷整個跳表诅迷。
推薦跳表的leveldb版實現(xiàn)。
綜上众旗，redis的數(shù)據(jù)結構分析告一段落罢杉。
