關鍵字：層高隨機
跳躍表支持平均O（logN）、最壞O(N)復雜度的結點查找，還可以通過順序性操作來批量處理結點。
在大部份情況下，跳躍表的效力可以和平衡樹相媲美，由于跳躍表的實現比平衡樹來得更加簡單，所以很多程序都使用跳躍表代替平衡樹。
Redis使用跳躍表作為有序集合鍵的底層實現之1，如果有1個有序集合包括的元素數量比較多，或有序集合中元素的成員是比較長的字符串時，Redis就會使用跳躍表作為有序集合鍵的底層實現。
Redis只在兩個地方用到了跳躍表，1個是實現有序集合鍵，另外一個是在集群結點中用作內部數據結構
Redis的跳躍表由redis.h/zskiplistNode和redis.h/zskiplist兩個結構定義：
/*
* 跳躍表節點
*/
typedef struct zskiplistNode {
// 成員對象
robj *obj;
// 分值
double score;
// 后退指針
struct zskiplistNode *backward;
// 層
struct zskiplistLevel {
// 前進指針
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;zskiplistNode結構包括以下屬性：
層（level）數組可以包括多個元素：每一個層帶有兩個屬性：前進指針和跨度。前進指針用于訪問位于表尾方向的其他結點，而跨度則記錄了前進指針所指向結點和當前節點的距離。當程序從表頭向表尾進行遍用時，訪問會沿著層的前進指針進行。層的數量越多，訪問其他結點的速度就越快。
后退（backward）指針：結點中用BW字樣標記結點的后退指針，它指向位于當前節點的前1個結點。后退指針在程序從表尾向表頭遍用時使用。與可以1次跳過量個結點的前進指針不同，每一個結點只有1個后退指針，所以每次只能后退至前1個結點
分值（score）：1個double類型的浮點數，跳躍表中，結點按各自所保存的分值從小到大排列
/*
* 跳躍表
*/
typedef struct zskiplist {
// 表頭節點和表尾節點
struct zskiplistNode *header, *tail;
// 表中節點的數量
unsigned long length;
// 表中層數最大的節點的層數
int level;
} zskiplist;zskiplist結構用于保存跳躍表結點的相干信息，如結點數量，指向表頭結點和表尾結點的指針等：
表頭結點和其他結點的構造是1樣的：表頭結點也有后退指針、分值和成員對象，不過表頭結點的這些屬性都不會被用到。
關鍵字：升級規則
整數集合（intset）是集合鍵的底層實現之1，當1個集合只包括整數值元素，并且這個集合的元素數量不多時，Redis就使用整數集合作為集合鍵的底層實現。
typedef struct intset {
// 編碼方式
uint32_t encoding;
// 集合包括的元素數量
uint32_t length;
// 保存元素的數組
int8_t contents[];
} intset;整數集合（intset）是Redis用于保存整數值的集合抽象數據結構，可以保存類型為int16_t、int32_t或int64_t的整數值，并且保證集合中不會出現重復元素。
contents數組是 整數集合的底層實現：整數集合的每一個元素都是contents數組的1個數組項，各個項在數組中按值的大小從小到大有序排列，并且數組中不包括任何重復項
length屬性記錄了整數集合包括的元素數量，即contents數組的長度
encoding屬性：雖然intset結構將contents屬性聲明為int8_t類型的數組，但實際上contents數組其實不保存任何int8_t類型的值，contents數組的真正類型取決于encoding屬性的值
當將1個新元素添加到整數集合里面，并且新元素的類型比整數集合現有所有元素的類型都要長時，整數集合需要先進行升級（upgrade），然后才能將新元素添加到整數集合里面。
升級整數集合并添加新元素共分為3步進行：
由于每次向整數集合添加新元素都可能會引發升級，而每次升級都需要對底層數組中已有的所有元素進行類型轉換，所以向整數集合添加新元素的時間復雜度為O(N)
引發升級的新元素長度總是比整數集合現有所有元素的長度都大，所以這個新元素的值要末大于所有現有元素，要末小于所有現有元素：
整數集合的升級策略有兩個好處：
提升整數集合的靈活性，可以隨便將int16_t、int32_t或int64_t類型的整數添加到集合中，沒必要擔心出現類型毛病
節儉內存，這樣做可讓集合能同時保存3種不同類型的值，又可以確保升級操作只會在有需要的時候進行
整數集合不支持降級操作，1旦對數組升級，編碼就會1直保持升級后的狀態。
關鍵字：連鎖更新
緊縮列表（ziplist）是列表鍵和哈希鍵的底層實現之1。當1個列表鍵只包括少許列表項，且每一個列表項要末是小整數值，要末是長度比較短的字符串，那末Redis就會是1緊縮列表來做列表鍵的底層實現
緊縮列表是Redis為了節儉內存開發的，是由1系列特殊編碼的連續內存塊組成的順序型（sequential）數據結構。1個緊縮列表可以包括任意多個結點（Entry），每一個結點保存1個字節數組或1個整數值。
/*
空白 ziplist 示例圖
area |<---- ziplist header ---->|<-- end -->|
size 4 bytes 4 bytes 2 bytes 1 byte
+---------+--------+-------+-----------+
component | zlbytes | zltail | zllen | zlend |
| | | | |
value | 1011 | 1010 | 0 | 1111 1111 |
+---------+--------+-------+-----------+
^
|
ZIPLIST_ENTRY_HEAD
&
address ZIPLIST_ENTRY_TAIL
&
ZIPLIST_ENTRY_END
非空 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
*//*
* 保存 ziplist 節點信息的結構
*/
typedef struct zlentry {
// prevrawlen ：前置節點的長度
// prevrawlensize ：編碼 prevrawlen 所需的字節大小
unsigned int prevrawlensize, prevrawlen;
// len ：當前節點值的長度
// lensize ：編碼 len 所需的字節大小
unsigned int lensize, len;
// 當前節點 header 的大小
// 等于 prevrawlensize + lensize
unsigned int headersize;
// 當前節點值所使用的編碼類型
unsigned char encoding;
// 指向當前節點的指針
unsigned char *p;
} zlentry;每一個緊縮列表結點可以保存1個字節數組或1個整數值，其中，字節數組可以是以下3種長度的其中1種：
整數值則可以是以下中的1種：
每一個緊縮列表結點都由previous_entry_length、encoding、content3個部份：
結點的previous_entry_length屬性以字節為單位，記錄了緊縮列表中前1個結點的長度。previous_entry_length屬性的長度可以是1字節或5字節
若前1結點的長度小于254字節，那末previous_entry_length的長度為1字節：前1結點的長度就保存在這1個字節里面
如果前1結點長度大于等于254字節，那末previous_entry_length屬性的長度為5字節：其中屬性的第1字節會被設置為0xFE（10進制254），而以后的4個字節則用于保存前1結點的長度
由于結點的previous_entry_length屬性記錄了前1個結點的長度，所以程序可以通過指針運算，根據當前節點的起始地址計算出前1個結點的起始地址
緊縮列表的從表尾向表頭遍歷操作就是使用這1原理實現的，只要具有1個指向某個結點起始地址的指針，那末通過這個指針和這個結點的previous_entry_length屬性，就能夠1直向前1個結點回溯，終究到達緊縮列表的表頭結點。
encoding屬性記錄了結點的content屬性所保存數據的類型和長度：
content屬性保存結點的值，結點值可以是1個字節數組或整數，值的類型和長度由節點的encoding屬性決定
緊縮列表的添加新節點操作和刪除結點操作都可能會引發連鎖更新：
連鎖更新在最壞情況下需要對緊縮列表履行N次空間重分配操作，而每次空間重分配的最壞復雜度為O（N），所以連鎖更新的最壞復雜度為O(N^2)
雖然連鎖更新的復雜度較高，但它真正造成性能問題的可能性不大：
關鍵字：編碼轉換，多態命令，內存回收與同享，LRU
Redis基于以上數據結構創建了1個對象系統，這個系統包括字符串對象、列表對象、哈希對象、集合對象和有序集合對象這5種類型的對象，每種對象都用到了最少1種以上數據結構。
使用對象的好處：
Redis使用對象來表示數據庫中的鍵和值，數據庫中新創建1個鍵值對時，最少會創建兩個對象：鍵對象，用作鍵值對的鍵，值對象，用作鍵值對的值
typedef struct redisObject {
// 類型
unsigned type:4;
// 編碼
unsigned encoding:4;
// 對象最后1次被訪問的時間，用于計算對象的空轉時長
// 當服務器占用的內存數超過了maxmemory選項設置的上限時，空轉時長高的那部份鍵會優先被服務器釋放，從而回收內存
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
// 援用計數
int refcount;
// 指向實際值的指針
void *ptr;
} robj;Redis中的每一個對象都由1個redisObject結構表示，該結構中的type屬性、encoding屬性和ptr屬性與保存數據相關：
對Redis數據庫保存的鍵值對來講，鍵總是1個字符串對象，而值則可以是字符串對象、列表對象、哈希對象、集合對象或有序集合對象的1種
encoding屬性記錄了對象所使用的編碼，即對象使用了甚么數據結構作為對象的底層實現
通過encoding設定對象所使用的編碼，使得Redis可以根據不同的使用處景為1個對象設置不同的編碼，從而優化對象在某1場景下的效力
字符串對象的編碼可以是int、raw或embstr。
如果1個字符串對象保存的是long類型的整數值，那末字符串對象會將整數值保存在字符串對象結構的ptr屬性里（將void*轉換成long），并將字符串對象的編碼設置為int。
如果字符串對象保存的是1個字符串值，并且這個字符串值的長度小于等于32字節，那末字符串對象將使用embstr編碼的方式來保存這個字符串值。
可以用long double類型表示的浮點數在Redis中也是作為字符串值保存的。
對int編碼的字符串對象，如果我們向對象履行了1些命令，使對象保存的不再是整數，而是1個字符串值，那末字符串對象的編碼將從int變成raw。
embstr編碼的字符串對象實際上是只讀的。對embstr編碼的字符串對象履行任何修改命令時，程序會先將對象的編碼從embstr轉換成raw，然后再履行修改命令。所以，embstr編碼的字符串對象在履行修改命令后，總會變成1個raw編碼的字符串對象
列表對象的編碼可以是ziplist或Linkedlist。
ziplist編碼的列表對象使用緊縮列表作為底層實現，每一個緊縮列表結點（Entry）保存了1個列表元素。
Linkedlist編碼的列表對象使用雙端鏈表作為底層實現，每一個雙端鏈表結點（Node）保存1個字符串對象，而每一個字符串對象保存1個列表元素。
當列表對象同時滿足以下兩個條件時，列表對象使用ziplist編碼：
否則使用linkedlist編碼。
哈希對象的編碼可以是ziplist或hashtable。
ziplist編碼的哈希對象使用緊縮列表作為底層實現，每當有新的鍵值對要加入到哈希對象時，程序會先將保存鍵的緊縮列表結點推入到緊縮列表表尾，然后再將保存值的緊縮列表結點推入到緊縮列表表尾：
hashtable編碼的哈希對象使用字典作為底層實現，哈希對象中的每一個鍵值對都使用1個字典鍵值對來保存：
當哈希對象同時滿足以下兩個條件時，哈希對象使用ziplist編碼：
否則需要使用hashtable編碼。
集合對象的編碼可以是intset或hashtable。
intset編碼的集合對象使用整數集合作為底層實現，集合對象包括的所有元素都被保存在整數集合里。
hashtable編碼的集合對象使用字典作為底層實現，字典的每一個鍵都是1個字符串對象，每一個字符串對象包括1個集合元素，而字典的值則全部被設置為null.
當滿足以下兩個條件時，使用intset編碼：
否則使用hashtable編碼。
有序集合的編碼可以是ziplist或skiplist。
ziplist編碼的有序集合對象使用緊縮列表作為底層實現，每一個集合元素使用兩個緊挨在1起的緊縮列表結點保存，第1個結點保存元素的成員（member），第2個元素則保存元素的分值（score）。
緊縮列表內的集合元素按分值從小到大進行排序，分值較小的元素靠近表頭的方向，分值較大靠近表尾。
skiplist編碼的有序集合對象使用zset結構作為底層實現，1個zset結構同時包括1個字典和1個跳躍表：
/*
* 有序集合
*/
typedef struct zset {
// 字典，鍵為成員，值為分值
// 用于支持 O(1) 復雜度的按成員取分值操作
dict *dict;
// 跳躍表，按分值排序成員
// 用于支持平均復雜度為 O(log N) 的按分值定位成員操作
// 和范圍操作
zskiplist *zsl;
} zset;有序集合每一個元素的成員都是1個字符串對象，而每一個元素的分值都是1個double類型的浮點數。
雖然zset結構同時使用跳躍表和字典來保存有序集合元素，但這兩種數據結構都會通過指針來同享相同元素的成員和分值，所以同時使用跳躍表和字典保存集合元素，不會產生重復成員和分值，不會因此浪費額外內存。
滿足以下兩個條件時，對象使用ziplist編碼：
否則有序集合對象使用skiplist編碼。
Redis中用于操作鍵的命令可分為兩種類型：
在履行1個類型特定的命令之前，Redis會先檢查輸入鍵的類型是不是正確，然后再決定是不是履行給定的命令。
類型特定命令的類型檢查是通過redisObject結構的type屬性來實現的：
Redis還會根據對象的編碼方式，選擇正確的命令實現代碼來履行命令。
Redis通過援用計數技術實現內存回收機制。
對象的援用計數信息會隨著對象的使用狀態而不斷變化：
基于援用計數的對象同享機制使Redis更節儉內存。
Redis的同享對象包括字符串鍵，和那些在數據結構中嵌套了字符串對象的對象（linkedlist編碼的列表對象、hashtable編碼的哈希對象、hashtable編碼的集合對象，zset編碼的有序集合對象）也能夠使用這些同享對象。
Redis只對包括整數值的字符串對象進行同享。
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
