面試官：Redis中基本的數(shù)據(jù)類(lèi)型有哪些？

我：Redis的基本數(shù)據(jù)類(lèi)型有：字符串（string）、哈希（hash）、列表（list）、集合（set）、有序集合（zset）。

面試官：有序集合的內(nèi)部實(shí)現(xiàn)方式是什么？

我還沉浸在上一個(gè)問(wèn)題的沾沾自喜中，頓時(shí)表情凝固了，手心開(kāi)始冒出冷汗。“這個(gè)。。沒(méi)有太深入了解”，我支支吾吾的說(shuō)到。

面試官：回去等消息吧。

這句話說(shuō)的干凈利落，然后就沒(méi)有然后了。失敗是成功的媽媽?zhuān)也粴怵H，決定馬上惡補(bǔ)一下。

有序集合的內(nèi)部實(shí)現(xiàn)

有序集合的內(nèi)部實(shí)現(xiàn)有兩種，分別是：壓縮列表（ziplist）和跳躍表（skiplist）。接下來(lái)，我們分別進(jìn)行詳細(xì)的了解。

以壓縮列表作為內(nèi)部實(shí)現(xiàn)

當(dāng)有序集合的元素個(gè)數(shù)小于zset-max-ziplist-entries（默認(rèn)為128個(gè)），并且每個(gè)元素成員的長(zhǎng)度小于zset-max-ziplist-value（默認(rèn)為64字節(jié)）的時(shí)候，使用壓縮列表作為有序集合的內(nèi)部實(shí)現(xiàn)。

每個(gè)集合元素由兩個(gè)緊挨在一起的兩個(gè)壓縮列表結(jié)點(diǎn)組成，其中第一個(gè)結(jié)點(diǎn)保存元素的成員，第二個(gè)結(jié)點(diǎn)保存元素的分支。壓縮列表中的元素按照分?jǐn)?shù)從小到大依次緊挨著排列，有效減少了內(nèi)存空間的使用。

舉個(gè)例子，我們使用zadd命令創(chuàng)建一個(gè)以壓縮列表為實(shí)現(xiàn)的有序集合：

127.0.0.1:6379> zadd one-more-zset 1 one 2 two 3 three
(integer) 3
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "one"
2) "two"
3) "three"
127.0.0.1:6379> object encoding one-more-zset
"ziplist"

以跳躍表作為內(nèi)部實(shí)現(xiàn)

當(dāng)有序集合的元素個(gè)數(shù)大于等于zset-max-ziplist-entries（默認(rèn)為128個(gè)），或者每個(gè)元素成員的長(zhǎng)度大于等于zset-max-ziplist-value（默認(rèn)為64字節(jié)）的時(shí)候，使用跳躍表作為有序集合的內(nèi)部實(shí)現(xiàn)。

此時(shí)，在有序集合中其實(shí)包含了兩個(gè)結(jié)構(gòu)，一個(gè)是跳躍表，另一個(gè)是哈希表。

在跳躍表中，所有元素按照從小到大的順序排列。跳躍表的結(jié)點(diǎn)中的object指針指向元素成員的字符串對(duì)象，score保存了元素的分?jǐn)?shù)。通過(guò)跳躍表，Redis可以快速地對(duì)有序集合進(jìn)行分?jǐn)?shù)范圍、排名等操作。

在哈希表中，為有序集合創(chuàng)建了一個(gè)從元素成員到元素分?jǐn)?shù)的映射。鍵值對(duì)中的鍵指向元素成員的字符串對(duì)象，鍵值對(duì)中的值保存了元素的分?jǐn)?shù)。通過(guò)哈希表，Redis可以快速查找指定元素的分?jǐn)?shù)。

雖然有序集合同時(shí)使用跳躍表和哈希表，但是這兩種數(shù)據(jù)結(jié)構(gòu)都使用指針共享元素中的成員和分?jǐn)?shù)，不會(huì)額外的內(nèi)存浪費(fèi)。

舉個(gè)例子，我們使用zadd命令創(chuàng)建一個(gè)以跳躍表為實(shí)現(xiàn)的有序集合：

127.0.0.1:6379> zadd one-more-zset 1 long-long-long-long-long-long-long-long-long-long-long-long-long-long
(integer) 1
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "long-long-long-long-long-long-long-long-long-long-long-long-long-long"
127.0.0.1:6379> object encoding one-more-zset
"skiplist"

內(nèi)部實(shí)現(xiàn)的轉(zhuǎn)換

當(dāng)一個(gè)有序集合是以壓縮列表作為內(nèi)部實(shí)現(xiàn)時(shí)，再向這個(gè)有序集合添加較長(zhǎng)的元素成員，或向這個(gè)有序集合的元素個(gè)數(shù)過(guò)多時(shí)，那么這個(gè)有序集合就會(huì)轉(zhuǎn)換為以跳躍表作為內(nèi)部實(shí)現(xiàn)。但是，以跳躍表作為內(nèi)部實(shí)現(xiàn)的有序集合不會(huì)轉(zhuǎn)換為以壓縮列表作為內(nèi)部實(shí)現(xiàn)。

舉個(gè)例子，我們先創(chuàng)建一個(gè)以壓縮列表作為內(nèi)部實(shí)現(xiàn)的有序集合：

127.0.0.1:6379> zadd one-more-zset 1 one 2 two 3 three
(integer) 3
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "one"
2) "two"
3) "three"
127.0.0.1:6379> object encoding one-more-zset
"ziplist"

然后，再向它添加一個(gè)較長(zhǎng)成員的元素，它就是轉(zhuǎn)換為以跳躍表作為內(nèi)部實(shí)現(xiàn)：

127.0.0.1:6379> zadd one-more-zset 4 long-long-long-long-long-long-long-long-long-long-long-long-long-long
(integer) 1
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "one"
2) "two"
3) "three"
4) "long-long-long-long-long-long-long-long-long-long-long-long-long-long"
127.0.0.1:6379> object encoding one-more-zset
"skiplist"

然后，再把那一個(gè)較長(zhǎng)成員的元素從有序集合中移除，有序集合依然是以跳躍表作為內(nèi)部實(shí)現(xiàn)：

127.0.0.1:6379> zrem one-more-zset long-long-long-long-long-long-long-long-long-long-long-long-long-long
(integer) 1
127.0.0.1:6379> zrange one-more-zset 0 -1
1) "one"
2) "two"
3) "three"
127.0.0.1:6379> object encoding one-more-zset
"skiplist"

總結(jié)

在Redis中，有序集合的內(nèi)部實(shí)現(xiàn)有壓縮列表（ziplist）和跳躍表（skiplist）兩種，當(dāng)集合中的所有元素的成員長(zhǎng)度較短并元素個(gè)數(shù)較少時(shí)，使用壓縮列表作為內(nèi)部實(shí)現(xiàn)，否則使用跳躍表和哈希表作為內(nèi)部實(shí)現(xiàn)。當(dāng)條件不滿足時(shí)，壓縮列表可以轉(zhuǎn)換為跳躍表，但跳躍表不能轉(zhuǎn)換為壓縮列表。

到此這篇關(guān)于Redis中有序集合的內(nèi)部實(shí)現(xiàn)方式的詳細(xì)介紹的文章就介紹到這了,更多相關(guān)Redis有序集合的內(nèi)部實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論