Redis 升級

每當我們要將一個新元素添加到整數(shù)集合里面， 并且新元素的類型比整數(shù)集合現(xiàn)有所有元素的類型都要長時， 整數(shù)集合需要先進行升級（upgrade）， 然后才能將新元素添加到整數(shù)集合里面。

升級整數(shù)集合并添加新元素共分為三步進行：

1. 根據(jù)新元素的類型， 擴展整數(shù)集合底層數(shù)組的空間大小， 并為新元素分配空間。
2. 將底層數(shù)組現(xiàn)有的所有元素都轉(zhuǎn)換成與新元素相同的類型， 并將類型轉(zhuǎn)換后的元素放置到正確的位上， 而且在放置元素的過程中， 需要繼續(xù)維持底層數(shù)組的有序性質(zhì)不變。
3. 將新元素添加到底層數(shù)組里面。

舉個例子， 假設(shè)現(xiàn)在有一個 INTSET_ENC_INT16 編碼的整數(shù)集合， 集合中包含三個 int16_t 類型的元素， 如圖 6-3 所示。

因為每個元素都占用 16 位空間， 所以整數(shù)集合底層數(shù)組的大小為 3 * 16 = 48 位， 圖 6-4 展示了整數(shù)集合的三個元素在這 48 位里的位置。

現(xiàn)在， 假設(shè)我們要將類型為 int32_t 的整數(shù)值 65535 添加到整數(shù)集合里面， 因為 65535 的類型 int32_t 比整數(shù)集合當前所有元素的類型都要長， 所以在將 65535 添加到整數(shù)集合之前， 程序需要先對整數(shù)集合進行升級。

升級首先要做的是， 根據(jù)新類型的長度， 以及集合元素的數(shù)量（包括要添加的新元素在內(nèi)）， 對底層數(shù)組進行空間重分配。

整數(shù)集合目前有三個元素， 再加上新元素 65535 ， 整數(shù)集合需要分配四個元素的空間， 因為每個 int32_t 整數(shù)值需要占用 32 位空間， 所以在空間重分配之后， 底層數(shù)組的大小將是 32 * 4 = 128 位， 如圖 6-5 所示。

雖然程序?qū)Φ讓訑?shù)組進行了空間重分配， 但數(shù)組原有的三個元素 1 、 2 、 3 仍然是 int16_t 類型， 這些元素還保存在數(shù)組的前 48 位里面， 所以程序接下來要做的就是將這三個元素轉(zhuǎn)換成 int32_t 類型， 并將轉(zhuǎn)換后的元素放置到正確的位上面， 而且在放置元素的過程中， 需要維持底層數(shù)組的有序性質(zhì)不變。

首先， 因為元素 3 在 1 、 2 、 3 、 65535 四個元素中排名第三， 所以它將被移動到 contents 數(shù)組的索引 2 位置上， 也即是數(shù)組 64 位至 95 位的空間內(nèi)， 如圖 6-6 所示。

接著， 因為元素 2 在 1 、 2 、 3 、 65535 四個元素中排名第二， 所以它將被移動到 contents 數(shù)組的索引 1 位置上， 也即是數(shù)組的 32位至 63 位的空間內(nèi)， 如圖 6-7 所示。

之后， 因為元素 1 在 1 、 2 、 3 、 65535 四個元素中排名第一， 所以它將被移動到 contents 數(shù)組的索引 0 位置上， 也即是數(shù)組的 0 位至 31 位的空間內(nèi)， 如圖 6-8 所示。

然后， 因為元素 65535 在 1 、 2 、 3 、 65535 四個元素中排名第四， 所以它將被添加到 contents 數(shù)組的索引 3 位置上， 也即是數(shù)組的96 位至 127 位的空間內(nèi)， 如圖 6-9 所示。

最后， 程序?qū)⒄麛?shù)集合 encoding 屬性的值從 INTSET_ENC_INT16 改為 INTSET_ENC_INT32 ， 并將 length 屬性的值從 3 改為 4 ， 設(shè)置完成之后的整數(shù)集合如圖 6-10 所示。

因為每次向整數(shù)集合添加新元素都可能會引起升級， 而每次升級都需要對底層數(shù)組中已有的所有元素進行類型轉(zhuǎn)換， 所以向整數(shù)集合添加新元素的時間復(fù)雜度為  。

其他類型的升級操作， 比如從 INTSET_ENC_INT16 編碼升級為 INTSET_ENC_INT64 編碼， 或者從 INTSET_ENC_INT32 編碼升級為 INTSET_ENC_INT64 編碼， 升級的過程都和上面展示的升級過程類似。

升級之后新元素的擺放位置

因為引發(fā)升級的新元素的長度總是比整數(shù)集合現(xiàn)有所有元素的長度都大， 所以這個新元素的值要么就大于所有現(xiàn)有元素， 要么就小于所有現(xiàn)有元素：

• 在新元素小于所有現(xiàn)有元素的情況下， 新元素會被放置在底層數(shù)組的最開頭（索引 0 ）；
• 在新元素大于所有現(xiàn)有元素的情況下， 新元素會被放置在底層數(shù)組的最末尾（索引 length-1 ）。