天天看點

《Redis設計與實作》第6章 整數集合(intset)

       整數集合(intset)是集合鍵的底層實作之一,當一個集合隻包含整數值元素,并且這個集合的元素數量不多時,Redis就會使用整數集合作為集合鍵的底層實作。

6.1 整數集合的實作

       整數集合(intset)是Redis用于儲存整數值的集合抽象資料結構,它可以保證類型為int16_t、int32_t或者int64_t的整數值,并且保證集合中不會出現重複的元素。集合結構儲存在inset.h/inset:

《Redis設計與實作》第6章 整數集合(intset)

       contents數組是整數集合的底層實作:整數集合的每個元素都是contents數組的一個數組項(item),各個項在數組中按值從小到大有序地排列,并且數組中不包含重複項。

       雖然inset結構将contents屬性聲明為int8_t類型的數組,但實際上contents數組并不儲存任何int8_t類型的值,contents數組的真正類型取決于encoding屬性的值:INTSET_ENC_INT16(int16_t類型:最小值-32768,最大值為32767)、INTSET_ENC_INT32(int32_t類型:最小值為-2147483648,最大值為2147483647)、INTSET_ENC_INT64(int64_t類型:最小值為-9223372036854775808,最大值為9223372036854775807)。

《Redis設計與實作》第6章 整數集合(intset)

6.2 整數集合的更新規則

       每當我們将一個新元素添加到整數集合裡面,并且新元素的類型比整數集合現有所有元素的類型都要長時,整數集合需要先進行更新(upgrade),然後才能将新元素添加到整數集合裡面。

       更新整數集合并添加新元素分三步進行:

       1)根據新元素類型,擴充整數集合底層數組的空間大小,并為新元素配置設定空間;

       2)将底層數組現有的所有元素都轉換成與新元素相同的類型,并将類型轉換後的元素放置到正确的位上,而且在放置元素的過程中,需要繼續維持底層數組的有序性質不變;

       3)将新元素添加到底層數組裡面。

       因為每次向整數集合添加新元素都可能會引起更新,而每次更新都需要對底層數組中已有的所有元素進行類型轉換,是以向整數集合添加新元素的時間複雜度為O(N)。

       因為引發更新的新元素的長度總是比整數集合現有所有元素的長度都大,是以這個新元素的值要麼大于所有現有元素(正數),要麼就小于所有現有元素(負數)。

6.3 更新的好處

       更新的兩個好處:

       1、提升整數集合的靈活性;

       2、盡可能地節約記憶體;

6.3.1 提升靈活性

       C語言是靜态類型語言,為了避免類型錯誤,不會将兩種不同類型的值放在同一個資料結構裡面。

       整數集合可以通過自動更新底層數組來适應新元素,是以我們可以随意地将int16_t、int32_t或者int64_t類型的整數添加到集合中,而不必擔心出現類型錯誤,這種做法非常靈活。

6.3.2 節約記憶體

       可以直接使用int64_t類型的數組作為整數集合的底層實作,儲存所有int8_t、int16_t、int32_t、int64_t類型的整數。

       整數集合現在的做法既可以讓集合能同時儲存三種不同類型的值,又可以確定更新操作隻會在有需要的時候進行,這可以盡量節省記憶體。

6.4 降級(不支援)

       降級一般發生在删除元素時,不過整數集合不支援降級操作,更新後,整數集合的編碼會一直保持更新後的狀态。(如果要支援降級,每次删除元素都要周遊集合中的所有元素,檢視這些元素的類型,再決定是否能夠進行降級操作)

6.5 整數集合API

《Redis設計與實作》第6章 整數集合(intset)

繼續閱讀