1. 首頁 > 生活百科 > >

二 京東云開發者| Redis數據結構-List、Hash、Set及Sorted Set的結構實現( 二 )

生活百科


  • 雙端：鏈表節點帶有prev和next指針，獲取某個節點的前置節點和后置節點的復雜度都是O(1)。
  • 無環：表頭節點的prev指針和表尾節點的next指針都指向NULL，對鏈表的訪問以NULL為終點 。
  • 帶表頭指針和表尾指針：通過list結構的head指針和tail指針，程序獲取鏈表的表頭節點和表尾節點的復雜度為O(1)。
  • 帶鏈表長度計數器：程序使用list結構的len屬性來對list持有的鏈表節點進行計數，程序獲取鏈表中節點數量的復雜度為O(1) 。
3 Hash存儲一個對象，可以直接將該對象進行序列化后使用String類型存儲，再通過反序列化獲取對象 。對于只需要獲取對象的某個屬性的場景，可以將將每個屬性分別存儲；但這樣在Redis的dict中就會存在大量的key，對于鍵時效后的回收效率存在很大影響 。使用Map結構就可以再dict的存儲中只存在一個key并將屬性與值再做關聯 。
Redis的Hash數據結構也是使用的dict(具體實現可以查看上一篇，淺談Redis數據結構(上)-Redis數據存儲及String類型的實現)實現 。當數據量比較小，或者單個元素比較小時，底層使用ziplist存儲 ， 數據量大小和元素數量有如下配置：
二 京東云開發者| Redis數據結構-List、Hash、Set及Sorted Set的結構實現

文章插圖
ziplist元素個數超過512 ， 將改為hashtable編碼hash-max-ziplist-entries 512單個元素大小超過64byte時 ， 將改為hashtable編碼hash-max-ziplist-value 64
二 京東云開發者| Redis數據結構-List、Hash、Set及Sorted Set的結構實現

文章插圖
4 SetSet類型可以在對不重復集合操作時使用，可以判斷元素是否存在于集合中 。Set數據結構底層實現為value為null的dict，當數據可以使用整形表示時，Set集合將被編碼為intset結構 。
typedef struct intset {uint32_t encoding;uint32_t length;int8_t contents[];} intset;整數集合是一個有序的，存儲整型數據的結構 。整型集合在Redis中可以保存xxxx的整型數據，并且可以保證集合中不會出現重復數據 。
二 京東云開發者| Redis數據結構-List、Hash、Set及Sorted Set的結構實現

文章插圖
使用intset可以節省空間，會根據最大元素范圍確定所有元素類型；元素有序存儲在判斷某個元素是否存在時可以基于二分查找 。但在以下任意條件不滿足時將會使用hashtable存儲數據 。
  • 元素個數大于配置的set-max-inset-entries值
  • 元素無法用整型表示
【二 京東云開發者| Redis數據結構-List、Hash、Set及Sorted Set的結構實現】
二 京東云開發者| Redis數據結構-List、Hash、Set及Sorted Set的結構實現

文章插圖
5 Sorted Set連續空間存儲數據，每次增加數據都會對全量數據進行搬運 。對于有序鏈表查找指定元素，只能通過頭、尾節點遍歷方式進行查找，如果將每個數據增加不定層數的索引，索引之間相互關聯，尋找指定或范圍的元素時就可以通過遍歷層級的索引來確定元素所處范圍，減少空間復雜度 。跳躍表是一種可以對有序鏈表進行近似二分查找的數據結構，redis 在兩個地方用到了跳躍表，一個是實現有序集合，另一個是在集群節點中用作內部數據結構 。
跳躍表 ( skiplist ) 是一種有序數據結構，自動去重的集合數據類型，ZSet數據結構底層實現為字典(dict) + 跳表(skiplist) 。它通過在每個節點中維持多個指向其他節點的指針，從而達到快速訪問節點的目的 。支持平均O ( logN ) 、最壞 O(N) 復雜度的節點查找，還可以通過順序性操作來批量處理節點 。
數據比較少時，用ziplist編碼結構存儲，包含的元素數量比較多，又或者有序集合中元素的成員(member) 是比較長的字符串時，Redis 就會使用跳躍表來作為有序集合鍵的底層實現 。
元素個數超過128，將用skiplist編碼zset-max-ziplist-entries 128
單個元素大小超過64 byte，將用skiplist編碼zset-max-ziplist-value 64
5.1 跳躍表zset結構如下：
typedef struct zset {// 字典，存儲數據元素dict *dict;// 跳躍表，實現范圍查找zskiplist *zsl;} zset;robj *createZsetObject(void) {// 分配空間zset *zs = zmalloc(sizeof(*zs));robj *o;// dict用來查詢數據到分數的對應關系 ， zscore可以直接根據元素拿到分值zs->dict = dictCreate(&zsetDictType,NULL);// 創建skiplistzs->zsl = zslCreate();o = createObject(OBJ_ZSET,zs);o->encoding = OBJ_ENCODING_SKIPLIST;return o;}zskiplist
typedef struct zskiplist {// 頭、尾節點;頭節點不存儲元素，擁有最高層高struct zskiplistNode *header, *tail;unsigned long length;// 層級,所有節點中的最高層高int level;} zskiplist;typedef struct zskiplistNode {// 元素member值sds ele;// 分值double score;// 后退指針struct zskiplistNode *backward;// 節點中用 L1、L2、L3 等字樣標記節點的各個層 ，  L1代表第一層，L2代表第二層，以此類推 。struct zskiplistLevel {// 指向本層下一個節點，尾節點指向nullstruct zskiplistNode *forward;// *forward指向的節點與本節點之間的元素個數，span值越大，跳過的節點個數越多unsigned long span;} level[];} zskiplistNode;

推薦閱讀