Redis中有序集合與列表占用內存分析

    在說正題之前需要先了解幾種定義：字典、壓縮列表與跳躍表。

    字典：非常常見的數據結構，key-value結構。

    常見的實現有紅黑樹（stl中的map），哈希表（stl中的unordered_map）。紅黑樹的查找操作具有O（logN）的時間復雜度。哈希表的查找操作具有O(1)的時間復雜度。 redis中的字典使用哈希表作為底層實現。

    壓縮列表：由一些列特殊編碼的連續內存塊組成的順序型數據結構。

    壓縮列表可以包含多種節點（只能保存一種的那叫數組）。 壓縮列表的優點是節省內存。順序結構擁有的缺點壓縮列表全都有。

    跳躍表：一種有序數據結構，它通過在每個節點中維護多個指向其他節點的指針，從而達到快速訪問節點的目的。

    跳躍表支持平均O（logN）、最壞O（N）時間復雜度的節點查找。

    redis中的跳躍表由zskiplist和zskiplistNode兩個結構組成，其中zskiplist用于保存跳躍表的信息（比如表頭節點、表尾節點、長度），而zskiplistNode用于表示跳躍表節點。跳躍表中的節點按照分支大小進行排序，當分值相同時，節點按照成員對象的大小進行排序。在同一跳躍表中，多個節點可以包含相同的分值，但每節點的成員對象必須是唯一的。

    進入正題，為什么redis中的有序集合占用內存比列表大？

    先說redis中的列表的實現，redis中的列表底層使用壓縮列表或鏈表來實現。redis列表有兩種不同的編碼（實現方式）：ziplist和linkedlist。在特定的條件下，編碼格式可以進行相互轉換。當列表對象保存的所有字符串元素的長度都小于64字節，并且列表對象的元素數量小于512時，列表對象使用ziplist。反之，使用linkedlist編碼。

    重點說一下有序集合的實現，redis中有序集合的實現要更加復雜，包含ziplist和skiplist兩種不同編碼。

    ziplist編碼的有序集合對象使用壓縮列表作為底層實現。每個集合元素使用兩個緊挨在一起的壓縮列表節點來保存，第一個節點保存元素的成員（member），而第二個元素則保存元素的分值（score）。

    skiplist 編碼的有序集合對象使用zset結果作為底層實現，一個zset結構同時包含一個字典和一個跳躍表。zset結構中的跳躍表按照分值從小到大保存了所有的集合元素，通過這個跳躍表，可以有序結合進行范圍型操作，例如zrank、zrange。 zset結構中的字典保存了有序集合中成員到分值的映射，通過這個字典，可以用O(1)的時間復雜度查找成員的分值。雖然zset使用兩種數據結構來保存數據，但這兩種數據結構使用指針來共享相同元素的成員和分值，所以并不會產生任何重復的成員或者分值。

    當有序集合保存的元素數量小于128個，并且所有元素成員的長度小于64字節時，使用ziplist編碼。反之，使用skiplist編碼。

    為什么有序集合要同時使用跳躍表和字典來實現呢？

    單獨使用字典時，查找快，只需要O(1)的時間復雜度，但是范圍操作就需要對字典元素進行排序，完成這種排序至少需要O(NlogN)的時間復雜度，以及額外的O(N)的內存空間。

    單獨使用跳躍表時，跳躍表執行范圍操作的優點會被保留，但是查找的效率會下降，查找的時間復雜度會從O(1)上升到O(logN)。