（一）跳躍表
跳躍表是一種有序的資料結構，它通過每個節點中維持多個指向其他節點的指標，從而達到快速訪問節點的目的，
Redis使用跳躍表作為有序集合鍵的底層實作之一，如果一個有序集合包含的元素數量比較多，或者有序集合中元素的成員是比較長的字串時，Redis就會使用跳躍表作為有序集合鍵的底層實作，
Redis中的兩個地方用到了跳躍表，一個是實作有序集合鍵，另一個是在集群節點中用作內部資料結構，
Redis的跳躍表由zskiplistNode 與 zskiplist 兩個結構定義，其中zskiplistNode 結構用于標識跳躍表節點，zskiplist結構用于保存跳躍表節點的相關資訊（表頭、表尾節點、節點數量等），
zskiplistNode
typedef struct zskiplistNode{ //層 struct zskiplistLevel{ struct zskiplistNode *forward;//前進指標 unsigned int span;//跨度 } level[]; //后退指標 struct zskiplistNode *backward; //分值 double score; //成員物件 robj *obj; }
層中包含多個元素，每個元素是指向其他節點的指標，通過這些層可以加快訪問其他節點的速度，層越多，訪問其他節點的速度越快，沒增加一個跳躍節點，程式根據冪次定律（越大的數出現概率越小）生成1-32之間的值作為層高，
1、每層都有一個指向表尾方向的前進指標，作為表頭向表尾方向訪問節點，
2、層中的跨度用于記錄兩個節點之間的距離，
3、后退指標則只能一次跨1個節點進行訪問，
4、跳躍表的排序是按照所有節點的分值來排序的，
5、節點中的物件則是保存了一個SDS的字串，
6、同一個跳躍表的物件必須唯一，但分值可以重復，（相同分數，成員小的靠前排），
跳躍表zskiplist
typedef struct zskiplist{ struct skiplistNode *header,*tail;//表頭節點與表尾節點 unsigned long length;//表中節點的數量 int level;//表中層數最大的節點的層數(表頭不計算在內) } zskiplist;
（二）整數集合
整數集合是集合鍵的底層實作之一，當一個集合只包含整數值元素，并且集合的元素數量不多時，Redis就會使用整數集合作為集合鍵的底層實作，并且保證集合中不會出現重復元素，
intset
typedef struct intset{ uint32_t encoding;//編碼方式 uint32_t length;//集合包含的元素數量， int8_t contents[];//保存元素的陣列 } intset;
contents陣列是這個數集合的底層實作：整數集合的每個元素都是contents陣列的一個陣列項，各個項的陣列中按值的大小從小到大有序地排列，并且陣列中不包含任何重復項，
升級
當我們要將一個新元素添加到整數集合里面時，并且新元素型別比整數集合現有的所有元素型別都長時，整數集合需要先進性升級，然后才能將新的元素添加到整數集合中，
1、根據新元素的型別，擴展整數集合底層陣列的空間大小，并為新元素分配空間，
2、將底層陣列現有的所有元素都轉換為與新元素相同的型別，并將型別轉換后的元素放置到正確位置上，而且在放置元素程序中，需要繼續維持底層陣列的有序性質不變，
3、將新元素添加到底層陣列里面，
4、修改整數集合encoding屬性，
因為每次向整數集合添加新元素都有可能引起升級，而每次升級都需要將底層陣列中已有的所有元素進行型別轉換，所以向整數集合中添加新元素的時間復雜度為O(N);
---- end ----
每天學一點，總會有識訓，
說明：尊重作者知識產權，文中內容參考《Redis設計與實作》，僅在此做學習與大家分享，
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/3163.html
標籤：NoSQL
上一篇：Redis常用命令
下一篇：Cassandra資料建模