亚洲激情专区-91九色丨porny丨老师-久久久久久久女国产乱让韩-国产精品午夜小视频观看

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

Redis中數據結構的底層實現分析

發布時間:2021-08-04 14:39:05 來源:億速云 閱讀:91 作者:Leah 欄目:數據庫

Redis中數據結構的底層實現分析,很多新手對此不是很清楚,為了幫助大家解決這個難題,下面小編將為大家詳細講解,有這方面需求的人可以來學習下,希望你能有所收獲。

1、概述

Redis是一個開源的使用ANSI C語言編寫的key-value 數據庫,我們可能會較為主觀的認為 Redis 中的字符串就是采用了C語言中的傳統字符串表示,但其實不然,Redis沒有直接使用C語言傳統的字符串表示,而是自己構建了一種名為簡單動態字符串(simple dynamic string SDS)的抽象類型,并將SDS用作Redis的默認字符串表示:redis>SET msg "hello world"

SDS 定義:

struct sdshdr{       //記錄buf數組中已使用字節的數量       //等于 SDS 保存字符串的長度       int len;       //記錄 buf 數組中未使用字節的數量       int free;       //字節數組,用于保存字符串       char buf[];  }

Redis中數據結構的底層實現分析

圖片來源:《Redis設計與實現》

我們看上面對于 SDS 數據類型的定義:

  •  len 保存了SDS保存字符串的長度

  •  buf[] 數組用來保存字符串的每個元素

  •  free j記錄了 buf 數組中未使用的字節數量

2、與C語言相比較 

Redis中數據結構的底層實現分析

一般來說,SDS 除了保存數據庫中的字符串值以外,SDS 還可以作為緩沖區(buffer):包括 AOF 模塊中的AOF緩沖區以及客戶端狀態中的輸入緩沖區。后面在介紹Redis的持久化時會進行介紹。

三、鏈表

1、概述

鏈表提供了高效的節點重排能力,以及順序性的節點訪問方式,并且可以通過增刪節點來靈活地調整鏈表的長度。

鏈表在Redis 中的應用非常廣泛,比如列表鍵的底層實現之一就是鏈表。當一個列表鍵包含了數量較多的元素,又或者列表中包含的元素都是比較長的字符串時,Redis 就會使用鏈表作為列表鍵的底層實現。

每個鏈表節點使用一個listNode結構表示(adlist.h/listNode):

typedef  struct listNode{         //前置節點         struct listNode *prev;         //后置節點         struct listNode *next;         //節點的值         void *value;    }listNode

鏈表的數據結構:

typedef struct list{        //表頭節點       listNode *head;       //表尾節點       listNode *tail;       //鏈表所包含的節點數量       unsigned long len;       //節點值復制函數       void (*free) (void *ptr);       //節點值釋放函數       void (*free) (void *ptr);       //節點值對比函數       int (*match) (void *ptr,void *key);  }list;

組成結構圖

Redis中數據結構的底層實現分析

2、Redis鏈表特性

  •  雙端:鏈表具有前置節點和后置節點的引用,獲取這兩個節點時間復雜度都為O(1)。

  •  無環:表頭節點的 prev 指針和表尾節點的 next 指針都指向 NULL,對鏈表的訪問都是以 NULL 結束。 

  •  帶鏈表長度計數器:通過 len 屬性獲取鏈表長度的時間復雜度為 O(1)。

  •  多態:鏈表節點使用 void* 指針來保存節點值,可以保存各種不同類型的值。

四、字典

1、概述

字典又稱為符號表或者關聯數組、或映射(map),是一種用于保存鍵值對的抽象數據結構。字典中的每一個鍵 key 都是唯一的,通過 key 可以對值來進行查找或修改。C 語言中沒有內置這種數據結構的實現,所以字典依然是 Redis自己構建的。

哈希表結構定義:

typedef struct dictht{       //哈希表數組       dictEntry **table;       //哈希表大小       unsigned long size;       //哈希表大小掩碼,用于計算索引值       //總是等于 size-1       unsigned long sizemask;       //該哈希表已有節點的數量       unsigned long used;  }dictht

哈希表是由數組 table 組成,table 中每個元素都是指向 dict.h/dictEntry 結構,dictEntry 結構定義如下:

typedef struct dictEntry{       //鍵       void *key;       //值       union{            void *val;            uint64_tu64;            int64_ts64;       }v;       //指向下一個哈希表節點,形成鏈表       struct dictEntry *next; }dictEntry

key 用來保存鍵,val 屬性用來保存值,值可以是一個指針,也可以是uint64_t整數,也可以是int64_t整數。

注意這里還有一個指向下一個哈希表節點的指針,我們知道哈希表最大的問題是存在哈希沖突,如何解決哈希沖突,有開放地址法和鏈地址法。這里采用的便是鏈地址法,通過next這個指針可以將多個哈希值相同的鍵值對連接在一起,用來解決哈希沖突。

Redis中數據結構的底層實現分析

五、跳躍表

1、概述

跳躍表(skiplist)是一種有序數據結構,它通過在每個節點中維持多個指向其他節點的指針,從而達到快速訪問節點的目的。跳躍表是一種隨機化的數據,跳躍表以有序的方式在層次化的鏈表中保存元素,效率和平衡樹媲美 ——查找、刪除、添加等操作都可以在對數期望時間下完成,并且比起平衡樹來說,跳躍表的實現要簡單直觀得多。

Redis 只在兩個地方用到了跳躍表,一個是實現有序集合鍵,另外一個是在集群節點中用作內部數據結構。

Redis中跳躍表節點定義如下:

typedef struct zskiplistNode {       //層       struct zskiplistLevel{             //前進指針             struct zskiplistNode *forward;             //跨度             unsigned int span;       }level[];       //后退指針       struct zskiplistNode *backward;       //分值       double score;       //成員對象       robj *obj;  } zskiplistNode

多個跳躍表節點構成一個跳躍表:

typedef struct zskiplist{       //表頭節點和表尾節點       structz skiplistNode *header, *tail;       //表中節點的數量       unsigned long length;       //表中層數最大的節點的層數       int level;  }zskiplist;
  •  header和tail指針分別指向跳躍表的表頭和表尾節點;

  •  length屬性記錄節點的數量;

  •  level屬性記錄層數最高的幾點的層數量;

  •  下圖分別展示了完整的跳躍表和單個節點的詳細結構圖:

Redis中數據結構的底層實現分析

2、特性

跳表具有如下性質:

  •  由很多層結構組成

  •  每一層都是一個有序的鏈表

  •  最底層(Level 1)的鏈表包含所有元素

  •  如果一個元素出現在 Level i 的鏈表中,則它在 Level i 之下的鏈表也都會出現。

  •  每個節點包含兩個指針,一個指向同一鏈表中的下一個元素,一個指向下面一層的元素。

六、整數集合

1、概述

《Redis 設計與實現》 中這樣定義整數集合:“整數集合是集合建的底層實現之一,當一個集合中只包含整數,且這個集合中的元素數量不多時,redis就會使用整數集合intset作為集合的底層實現。”

我們可以這樣理解整數集合,他其實就是一個特殊的集合,里面存儲的數據只能夠是整數,并且數據量不能過大。

typedef struct intset{       //編碼方式       uint32_t encoding;       //集合包含的元素數量       uint32_t length;       //保存元素的數組       int8_t contents[];  }intset;

我們觀察一下一個完成的整數集合結構圖: 

Redis中數據結構的底層實現分析

  • encoding:用于定義整數集合的編碼方式

  • length:用于記錄整數集合中變量的數量

  • contents:用于保存元素的數組,雖然我們在數據結構圖中看到,intset將數組定義為int8_t,但實際上數組保存的元素類型取決于encoding

2、特性

  •  整數集合是集合建的底層實現之一

  •  整數集合的底層實現為數組,這個數組以有序,無重復的范式保存集合元素,在有需要時,程序會根據新添加的元素類型改變這個數組的類型

  •  升級操作為整數集合帶來了操作上的靈活性,并且盡可能地節約了內存2

  整數集合只支持升級操作,不支持降級操作

七、壓縮列表

1、概述

壓縮列表是列表鍵和哈希鍵的底層實現之一。當一個列表鍵只包含少量列表項,并且每個列表項要么就是小整數,要么就是長度比較短的字符串,那么Redis 就會使用壓縮列表來做列表鍵的底層實現。

一個壓縮列表的組成如下:

Redis中數據結構的底層實現分析

  •  zlbytes:用于記錄整個壓縮列表占用的內存字節數

  •  zltail:記錄要列表尾節點距離壓縮列表的起始地址有多少字節

  •  zllen:記錄了壓縮列表包含的節點數量

  •  entryX:要說列表包含的各個節點

  •  zlend:用于標記壓縮列表的末端

2、特性

  •  壓縮列表是一種為了節約內存而開發的順序型數據結構

  •  壓縮列表被用作列表鍵和哈希鍵的底層實現之一

  •  壓縮列表可以包含多個節點,每個節點可以保存一個字節數組或者整數值

  •  添加新節點到壓縮列表,可能會引發連鎖更新操作。 

看完上述內容是否對您有幫助呢?如果還想對相關知識有進一步的了解或閱讀更多相關文章,請關注億速云行業資訊頻道,感謝您對億速云的支持。

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

合作市| 砚山县| 隆化县| 鄂伦春自治旗| 桐乡市| 怀柔区| 洪湖市| 红原县| 宾阳县| 舒兰市| 文水县| 壤塘县| 吉安市| 屏东县| 稻城县| 福鼎市| 宁南县| 左权县| 治县。| 宁陕县| 鸡东县| 巴东县| 楚雄市| 农安县| 临沂市| 德庆县| 丘北县| 石渠县| 辰溪县| 宾川县| 玉溪市| 弥勒县| 攀枝花市| 北碚区| 腾冲县| 越西县| 井研县| 金溪县| 浙江省| 阳原县| 西和县|