Redis五种数据结构详解
Redis是基于c語(yǔ)言編寫(xiě)的開(kāi)源非關(guān)系型內(nèi)存數(shù)據(jù)庫(kù),可以用作數(shù)據(jù)庫(kù)、緩存、消息中間件,這么優(yōu)秀的東西一定要一點(diǎn)一點(diǎn)的吃透它。
Redis的五種數(shù)據(jù)結(jié)構(gòu)包括以下五種:
String:字符串類(lèi)型
List:列表類(lèi)型
Set:無(wú)序集合類(lèi)型
ZSet:有序集合類(lèi)型
Hash:哈希表類(lèi)型但是作為一名優(yōu)秀的程序在Redis中有一個(gè)「核心的對(duì)象」叫做redisObject ,是用來(lái)表示所有的key和value的,用redisObject結(jié)構(gòu)體來(lái)表示String、Hash、List、Set、ZSet五種數(shù)據(jù)類(lèi)型。
redisObject的源代碼在redis.h中,使用c語(yǔ)言寫(xiě)的,感興趣的可以自行查看,關(guān)于redisObject我這里畫(huà)了一張圖,表示redisObject的結(jié)構(gòu)如下所示:
在redisObject中「type表示屬于哪種數(shù)據(jù)類(lèi)型,encoding表示該數(shù)據(jù)的存儲(chǔ)方式」,也就是底層的實(shí)現(xiàn)的該數(shù)據(jù)類(lèi)型的數(shù)據(jù)結(jié)構(gòu)。因此這篇文章具體介紹的也是encoding對(duì)應(yīng)的部分。
那么encoding中的存儲(chǔ)類(lèi)型又分別表示什么意思呢?具體數(shù)據(jù)類(lèi)型所表示的含義,如下圖所示:
你在Redis中設(shè)置一個(gè)字符串key 234,然后查看這個(gè)字符串的存儲(chǔ)類(lèi)型就會(huì)看到為int類(lèi)型,非整數(shù)型的使用的是embstr儲(chǔ)存類(lèi)型,具體操作如下圖所示:員可能不能只停留在只會(huì)用這五種類(lèi)型進(jìn)行crud工作,還是得深入了解這五種數(shù)據(jù)結(jié)構(gòu)的底層原理。
二、Redis核心對(duì)象
三、String類(lèi)型String是Redis最基本的數(shù)據(jù)類(lèi)型,上面的簡(jiǎn)介中也說(shuō)到Redis是用c語(yǔ)言開(kāi)發(fā)的。但是Redis中的字符串和c語(yǔ)言中的字符串類(lèi)型卻是有明顯的區(qū)別。
String類(lèi)型的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)方式有三種int、raw、embstr。那么這三種存儲(chǔ)方式有什么區(qū)別呢?
int
Redis中規(guī)定假如存儲(chǔ)的是「整數(shù)型值」,比如set num 123這樣的類(lèi)型,就會(huì)使用 int的存儲(chǔ)方式進(jìn)行存儲(chǔ),在redisObject的「ptr屬性」中就會(huì)保存該值。
SDS
假如存儲(chǔ)的「字符串是一個(gè)字符串值并且長(zhǎng)度大于32個(gè)字節(jié)」就會(huì)使用SDS(simple dynamic string)方式進(jìn)行存儲(chǔ),并且encoding設(shè)置為raw;
若是「字符串長(zhǎng)度小于等于32個(gè)字節(jié)」就會(huì)將encoding改為embstr來(lái)保存字符串。
SDS稱(chēng)為「簡(jiǎn)單動(dòng)態(tài)字符串」,對(duì)于SDS中的定義在Redis的源碼中有的三個(gè)屬性int len、int free、char buf[]。
len保存了字符串的長(zhǎng)度,
free表示buf數(shù)組中未使用的字節(jié)數(shù)量
buf數(shù)組則是保存字符串的每一個(gè)字符元素。
因此當(dāng)你在Redsi中存儲(chǔ)一個(gè)字符串Hello時(shí),根據(jù)Redis的源代碼的描述可以畫(huà)出SDS的形式的redisObject結(jié)構(gòu)圖如下圖所示:
SDS與c語(yǔ)言字符串對(duì)比
Redis使用SDS作為存儲(chǔ)字符串的類(lèi)型肯定是有自己的優(yōu)勢(shì),SDS與c語(yǔ)言的字符串相比,SDS對(duì)c語(yǔ)言的字符串做了自己的設(shè)計(jì)和優(yōu)化,具體優(yōu)勢(shì)有以下幾點(diǎn):
(1)c語(yǔ)言中的字符串并不會(huì)記錄自己的長(zhǎng)度,因此「每次獲取字符串的長(zhǎng)度都會(huì)遍歷得到,時(shí)間的復(fù)雜度是O(n)」,而Redis中獲取字符串只要讀取len的值就可,時(shí)間復(fù)雜度變?yōu)镺(1)。
(2)「c語(yǔ)言」中兩個(gè)字符串拼接,若是沒(méi)有分配足夠長(zhǎng)度的內(nèi)存空間就「會(huì)出現(xiàn)緩沖區(qū)溢出的情況」;而「SDS」會(huì)先根據(jù)len屬性判斷空間是否滿(mǎn)足要求,若是空間不夠,就會(huì)進(jìn)行相應(yīng)的空間擴(kuò)展,所以「不會(huì)出現(xiàn)緩沖區(qū)溢出的情況」。
(3)SDS還提供「空間預(yù)分配」和「惰性空間釋放」兩種策略。在為字符串分配空間時(shí),分配的空間比實(shí)際要多,這樣就能「減少連續(xù)的執(zhí)行字符串增長(zhǎng)帶來(lái)內(nèi)存重新分配的次數(shù)」。
當(dāng)字符串被縮短的時(shí)候,SDS也不會(huì)立即回收不適用的空間,而是通過(guò)free屬性將不使用的空間記錄下來(lái),等后面使用的時(shí)候再釋放。
具體的空間預(yù)分配原則是:「當(dāng)修改字符串后的長(zhǎng)度len小于1MB,就會(huì)預(yù)分配和len一樣長(zhǎng)度的空間,即len=free;若是len大于1MB,free分配的空間大小就為1MB」。
(4)SDS是二進(jìn)制安全的,除了可以?xún)?chǔ)存字符串以外還可以?xún)?chǔ)存二進(jìn)制文件(如圖片、音頻,視頻等文件的二進(jìn)制數(shù)據(jù));而c語(yǔ)言中的字符串是以空字符串作為結(jié)束符,一些圖片中含有結(jié)束符,因此不是二進(jìn)制安全的。
為了方便易懂,做了一個(gè)c語(yǔ)言的字符串和SDS進(jìn)行對(duì)比的表格,如下所示:
String類(lèi)型
(1)首先要把上傳得圖片進(jìn)行編碼,這里寫(xiě)了一個(gè)工具類(lèi)把圖片處理成了Base64得編碼形式,具體得實(shí)現(xiàn)代碼如下:
(2)第二步就是把處理后的圖片字符串格式存儲(chǔ)進(jìn)Redis中,實(shí)現(xiàn)的代碼如下所示:
這樣就是實(shí)現(xiàn)了圖片得二進(jìn)制存儲(chǔ),當(dāng)然String類(lèi)型得數(shù)據(jù)結(jié)構(gòu)得應(yīng)用也還有常規(guī)計(jì)數(shù):「統(tǒng)計(jì)微博數(shù)、統(tǒng)計(jì)粉絲數(shù)」等。
四、Hash類(lèi)型ash對(duì)象的實(shí)現(xiàn)方式有兩種分別是ziplist、hashtable,其中hashtable的存儲(chǔ)方式key是String類(lèi)型的,value也是以key value的形式進(jìn)行存儲(chǔ)。
字典類(lèi)型的底層就是hashtable實(shí)現(xiàn)的,明白了字典的底層實(shí)現(xiàn)原理也就是明白了hashtable的實(shí)現(xiàn)原理,hashtable的實(shí)現(xiàn)原理可以與HashMap的是底層原理相類(lèi)比。
字典
兩者在新增時(shí)都會(huì)通過(guò)key計(jì)算出數(shù)組下標(biāo),不同的是計(jì)算法方式不同:
HashMap中是以hash函數(shù)的方式,
hashtable中計(jì)算出hash值后,還要通過(guò)sizemask 屬性和哈希值再次得到數(shù)組下標(biāo)。
我們知道hash表最大的問(wèn)題就是hash沖突,為了解決hash沖突,假如hashtable中不同的key通過(guò)計(jì)算得到同一個(gè)index,就會(huì)形成單向鏈表(「鏈地址法」),如下圖所示:
rehash
在字典的底層實(shí)現(xiàn)中,value對(duì)象以每一個(gè)dictEntry的對(duì)象進(jìn)行存儲(chǔ),當(dāng)hash表中的存放的鍵值對(duì)不斷的增加或者減少時(shí),需要對(duì)hash表進(jìn)行一個(gè)擴(kuò)展或者收縮。
這里就會(huì)和HashMap一樣也會(huì)就進(jìn)行rehash操作,進(jìn)行重新散列排布。從上圖中可以看到有ht[0]和ht[1]兩個(gè)對(duì)象,先來(lái)看看對(duì)象中的屬性是干嘛用的。
在hash表結(jié)構(gòu)定義中有四個(gè)屬性分別是:
dictEntry **table、
unsigned long size、
unsigned long sizemask、
unsigned long used
分別表示的含義就是「哈希表數(shù)組、hash表大小、用于計(jì)算索引值,總是等于size-1、hash表中已有的節(jié)點(diǎn)數(shù)」。
ht[0]是用來(lái)最開(kāi)始存儲(chǔ)數(shù)據(jù)的,當(dāng)要進(jìn)行擴(kuò)展或者收縮時(shí),ht[0]的大小就決定了ht[1]的大小,ht[0]中的所有的鍵值對(duì)就會(huì)重新散列到ht[1]中。
擴(kuò)展操作:ht[1]擴(kuò)展的大小是比當(dāng)前 ht[0].used 值的二倍大的第一個(gè) 2 的整數(shù)冪;收縮操作:ht[0].used 的第一個(gè)大于等于的 2 的整數(shù)冪。
當(dāng)ht[0]上的所有的鍵值對(duì)都rehash到ht[1]中,會(huì)重新計(jì)算所有的數(shù)組下標(biāo)值,當(dāng)數(shù)據(jù)遷移完后ht[0]就會(huì)被釋放,然后將ht[1]改為ht[0],并新創(chuàng)建ht[1],為下一次的擴(kuò)展和收縮做準(zhǔn)備。
漸進(jìn)式rehash
假如在rehash的過(guò)程中數(shù)據(jù)量非常大,Redis不是一次性把全部數(shù)據(jù)rehash成功,這樣會(huì)導(dǎo)致Redis對(duì)外服務(wù)停止,Redis內(nèi)部為了處理這種情況采用「漸進(jìn)式的rehash」。
Redis將所有的rehash的操作分成多步進(jìn)行,直到都rehash完成,具體的實(shí)現(xiàn)與對(duì)象中的rehashindex屬性相關(guān),「若是rehashindex 表示為-1表示沒(méi)有rehash操作」。
當(dāng)rehash操作開(kāi)始時(shí)會(huì)將該值改成0,在漸進(jìn)式rehash的過(guò)程「更新、刪除、查詢(xún)會(huì)在ht[0]和ht[1]中都進(jìn)行」,比如更新一個(gè)值先更新ht[0],然后再更新ht[1]。
而新增操作直接就新增到ht[1]表中,ht[0]不會(huì)新增任何的數(shù)據(jù),這樣保證「ht[0]只減不增,直到最后的某一個(gè)時(shí)刻變成空表」,這樣rehash操作完成。
上面就是字典的底層hashtable的實(shí)現(xiàn)原理,說(shuō)完了hashtable的實(shí)現(xiàn)原理,我們?cè)賮?lái)看看Hash數(shù)據(jù)結(jié)構(gòu)的兩一種存儲(chǔ)方式「ziplist(壓縮列表)」
ziplist
壓縮列表(ziplist)是一組連續(xù)內(nèi)存塊組成的順序的數(shù)據(jù)結(jié)構(gòu),壓縮列表能夠節(jié)省空間,壓縮列表中使用多個(gè)節(jié)點(diǎn)來(lái)存儲(chǔ)數(shù)據(jù)。
壓縮列表是列表鍵和哈希鍵底層實(shí)現(xiàn)的原理之一,「壓縮列表并不是以某種壓縮算法進(jìn)行壓縮存儲(chǔ)數(shù)據(jù),而是它表示一組連續(xù)的內(nèi)存空間的使用,節(jié)省空間」,壓縮列表的內(nèi)存結(jié)構(gòu)圖如下:
壓縮列表中每一個(gè)節(jié)點(diǎn)表示的含義如下所示:
zlbytes:4個(gè)字節(jié)的大小,記錄壓縮列表占用內(nèi)存的字節(jié)數(shù)。
zltail:4個(gè)字節(jié)大小,記錄表尾節(jié)點(diǎn)距離起始地址的偏移量,用于快速定位到尾節(jié)點(diǎn)的地址。
zllen:2個(gè)字節(jié)的大小,記錄壓縮列表中的節(jié)點(diǎn)數(shù)。
entry:表示列表中的每一個(gè)節(jié)點(diǎn)。
zlend:表示壓縮列表的特殊結(jié)束符號(hào)’0xFF’。
再壓縮列表中每一個(gè)entry節(jié)點(diǎn)又有三部分組成,包括previous_entry_ength、encoding、content。
previous_entry_ength表示前一個(gè)節(jié)點(diǎn)entry的長(zhǎng)度,可用于計(jì)算前一個(gè)節(jié)點(diǎn)的其實(shí)地址,因?yàn)樗麄兊牡刂肥沁B續(xù)的。
encoding:這里保存的是content的內(nèi)容類(lèi)型和長(zhǎng)度。
content:content保存的是每一個(gè)節(jié)點(diǎn)的內(nèi)容。
說(shuō)到這里相信大家已經(jīng)都hash這種數(shù)據(jù)結(jié)構(gòu)已經(jīng)非常了解,若是第一次接觸Redis五種基本數(shù)據(jù)結(jié)構(gòu)的底層實(shí)現(xiàn)的話(huà),建議多看幾遍,下面來(lái)說(shuō)一說(shuō)hash的應(yīng)用場(chǎng)景。
應(yīng)用場(chǎng)景
哈希表相對(duì)于String類(lèi)型存儲(chǔ)信息更加直觀(guān),存儲(chǔ)更加方便,經(jīng)常會(huì)用來(lái)做用戶(hù)數(shù)據(jù)的管理,存儲(chǔ)用戶(hù)的信息。
hash也可以用作高并發(fā)場(chǎng)景下使用Redis生成唯一的id。下面我們就以這兩種場(chǎng)景用作案例編碼實(shí)現(xiàn)。
存儲(chǔ)用戶(hù)數(shù)據(jù)
第一個(gè)場(chǎng)景比如我們要儲(chǔ)存用戶(hù)信息,一般使用用戶(hù)的ID作為key值,保持唯一性,用戶(hù)的其他信息(地址、年齡、生日、電話(huà)號(hào)碼等)作為value值存儲(chǔ)。
若是傳統(tǒng)的實(shí)現(xiàn)就是將用戶(hù)的信息封裝成為一個(gè)對(duì)象,通過(guò)序列化存儲(chǔ)數(shù)據(jù),當(dāng)需要獲取用戶(hù)信息的時(shí)候,就會(huì)通過(guò)反序列化得到用戶(hù)信息。
但是這樣必然會(huì)造成序列化和反序列化的性能的開(kāi)銷(xiāo),并且若是只修改其中的一個(gè)屬性值,就需要把整個(gè)對(duì)象序列化出來(lái),操作的動(dòng)作太大,造成不必要的性能開(kāi)銷(xiāo)。
若是使用Redis的hash來(lái)存儲(chǔ)用戶(hù)數(shù)據(jù),就會(huì)將原來(lái)的value值又看成了一個(gè)k v形式的存儲(chǔ)容器,這樣就不會(huì)帶來(lái)序列化的性能開(kāi)銷(xiāo)的問(wèn)題。
分布式生成唯一ID
第二個(gè)場(chǎng)景就是生成分布式的唯一ID,這個(gè)場(chǎng)景下就是把redis封裝成了一個(gè)工具類(lèi)進(jìn)行實(shí)現(xiàn),實(shí)現(xiàn)的代碼如下:
五、List
Redis中的列表在3.2之前的版本是使用ziplist和linkedlist進(jìn)行實(shí)現(xiàn)的。在3.2之后的版本就是引入了quicklist。
ziplist壓縮列表上面已經(jīng)講過(guò)了,我們來(lái)看看linkedlist和quicklist的結(jié)構(gòu)是怎么樣的。
linkedlist是一個(gè)雙向鏈表,他和普通的鏈表一樣都是由指向前后節(jié)點(diǎn)的指針。插入、修改、更新的時(shí)間復(fù)雜度尾O(1),但是查詢(xún)的時(shí)間復(fù)雜度確實(shí)O(n)。
linkedlist和quicklist的底層實(shí)現(xiàn)是采用鏈表進(jìn)行實(shí)現(xiàn),在c語(yǔ)言中并沒(méi)有內(nèi)置的鏈表這種數(shù)據(jù)結(jié)構(gòu),Redis實(shí)現(xiàn)了自己的鏈表結(jié)構(gòu)。
Redis中鏈表的特性:
每一個(gè)節(jié)點(diǎn)都有指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)的指針。
頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的prev和next指針指向?yàn)閚ull,所以鏈表是無(wú)環(huán)的。
鏈表有自己長(zhǎng)度的信息,獲取長(zhǎng)度的時(shí)間復(fù)雜度為O(1)。
Redis中List的實(shí)現(xiàn)比較簡(jiǎn)單,下面我們就來(lái)看看它的應(yīng)用場(chǎng)景。
應(yīng)用場(chǎng)景
Redis中的列表可以實(shí)現(xiàn)「阻塞隊(duì)列」,結(jié)合lpush和brpop命令就可以實(shí)現(xiàn)。生產(chǎn)者使用lupsh從列表的左側(cè)插入元素,消費(fèi)者使用brpop命令從隊(duì)列的右側(cè)獲取元素進(jìn)行消費(fèi)。
(1)首先配置redis的配置,為了方便我就直接放在application.yml配置文件中,實(shí)際中可以把redis的配置文件放在一個(gè)redis.properties文件單獨(dú)放置,具體配置如下:
(2)第二步創(chuàng)建redis的配置類(lèi),叫做RedisConfig,并標(biāo)注上@Configuration注解,表明他是一個(gè)配置類(lèi)。
@Configuration public class RedisConfiguration {@Value("${spring.redis.host}") private String host; @Value("${spring.redis.port}") private int port; @Value("${spring.redis.password}") private String password; @Value("${spring.redis.pool.max-active}") private int maxActive; @Value("${spring.redis.pool.max-idle}") private int maxIdle; @Value("${spring.redis.pool.min-idle}") private int minIdle; @Value("${spring.redis.pool.max-wait}") private int maxWait; @Value("${spring.redis.database}") private int database; @Value("${spring.redis.timeout}") private int timeout;@Bean public JedisPoolConfig getRedisConfiguration(){ JedisPoolConfig jedisPoolConfig= new JedisPoolConfig(); jedisPoolConfig.setMaxTotal(maxActive); jedisPoolConfig.setMaxIdle(maxIdle); jedisPoolConfig.setMinIdle(minIdle); jedisPoolConfig.setMaxWaitMillis(maxWait); return jedisPoolConfig; }@Bean public JedisConnectionFactory getConnectionFactory() { JedisConnectionFactory factory = new JedisConnectionFactory(); factory.setHostName(host); factory.setPort(port); factory.setPassword(password); factory.setDatabase(database); JedisPoolConfig jedisPoolConfig= getRedisConfiguration(); factory.setPoolConfig(jedisPoolConfig); return factory; }@Bean public RedisTemplate<?, ?> getRedisTemplate() { JedisConnectionFactory factory = getConnectionFactory(); RedisTemplate<?, ?> redisTemplate = new StringRedisTemplate(factory); return redisTemplate; } }(3)第三步就是創(chuàng)建Redis的工具類(lèi)RedisUtil,自從學(xué)了面向?qū)ο蠛?#xff0c;就喜歡把一些通用的東西拆成工具類(lèi),好像一個(gè)一個(gè)零件,需要的時(shí)候,就把它組裝起來(lái)。
@Component public class RedisUtil {@Autowired private RedisTemplate<String, Object> redisTemplate; /** * 存消息到消息隊(duì)列中 * @param key 鍵 * @param value 值 * @return */ public boolean lPushMessage(String key, Object value) { try { redisTemplate.opsForList().leftPush(key, value); return true; } catch (Exception e) { e.printStackTrace(); return false; } }/** * 從消息隊(duì)列中彈出消息 * @param key 鍵 * @return */ public Object rPopMessage(String key) { try { return redisTemplate.opsForList().rightPop(key); } catch (Exception e) { e.printStackTrace(); return null; } }/** * 查看消息 * @param key 鍵 * @param start 開(kāi)始 * @param end 結(jié)束 0 到 -1代表所有值 * @return */ public List<Object> getMessage(String key, long start, long end) { try { return redisTemplate.opsForList().range(key, start, end); } catch (Exception e) { e.printStackTrace(); return null; } }這樣就完成了Redis消息隊(duì)列工具類(lèi)的創(chuàng)建,在后面的代碼中就可以直接使用。
六、set集合
Redis中列表和集合都可以用來(lái)存儲(chǔ)字符串,但是「Set是不可重復(fù)的集合,而List列表可以存儲(chǔ)相同的字符串」,Set集合是無(wú)序的這個(gè)和后面講的ZSet有序集合相對(duì)。
Set的底層實(shí)現(xiàn)是「ht和intset」,ht(哈希表)前面已經(jīng)詳細(xì)了解過(guò),下面我們來(lái)看看inset類(lèi)型的存儲(chǔ)結(jié)構(gòu)。
inset也叫做整數(shù)集合,用于保存整數(shù)值的數(shù)據(jù)結(jié)構(gòu)類(lèi)型,它可以保存int16_t、int32_t 或者int64_t 的整數(shù)值。
在整數(shù)集合中,有三個(gè)屬性值encoding、length、contents[],分別表示編碼方式、整數(shù)集合的長(zhǎng)度、以及元素內(nèi)容,length就是記錄contents里面的大小。
在整數(shù)集合新增元素的時(shí)候,若是超出了原集合的長(zhǎng)度大小,就會(huì)對(duì)集合進(jìn)行升級(jí),具體的升級(jí)過(guò)程如下:
首先擴(kuò)展底層數(shù)組的大小,并且數(shù)組的類(lèi)型為新元素的類(lèi)型。
然后將原來(lái)的數(shù)組中的元素轉(zhuǎn)為新元素的類(lèi)型,并放到擴(kuò)展后數(shù)組對(duì)應(yīng)的位置。
整數(shù)集合升級(jí)后就不會(huì)再降級(jí),編碼會(huì)一直保持升級(jí)后的狀態(tài)。
應(yīng)用場(chǎng)景
Set集合的應(yīng)用場(chǎng)景可以用來(lái)「去重、抽獎(jiǎng)、共同好友、二度好友」等業(yè)務(wù)類(lèi)型。接下來(lái)模擬一個(gè)添加好友的案例實(shí)現(xiàn):
假如兩個(gè)用戶(hù)A和B都是用上上面的這個(gè)接口添加了很多的自己的好友,那么有一個(gè)需求就是要實(shí)現(xiàn)獲取A和B的共同好友,那么可以進(jìn)行如下操作:
public Set intersectFriend(User userA, User userB) {return setOperations.intersect(userA.getId.toString(), userB.getId.toString()); } ```七、ZSet集合 ZSet是有序集合,從上面的圖中可以看到ZSet的底層實(shí)現(xiàn)是ziplist和skiplist實(shí)現(xiàn)的,ziplist上面已經(jīng)詳細(xì)講過(guò),這里來(lái)講解skiplist的結(jié)構(gòu)實(shí)現(xiàn)。skiplist也叫做「跳躍表」,跳躍表是一種有序的數(shù)據(jù)結(jié)構(gòu),它通過(guò)每一個(gè)節(jié)點(diǎn)維持多個(gè)指向其它節(jié)點(diǎn)的指針,從而達(dá)到快速訪(fǎng)問(wèn)的目的。skiplist有如下幾個(gè)特點(diǎn):有很多層組成,由上到下節(jié)點(diǎn)數(shù)逐漸密集,最上層的節(jié)點(diǎn)最稀疏,跨度也最大。 每一層都是一個(gè)有序鏈表,至少包含兩個(gè)節(jié)點(diǎn),頭節(jié)點(diǎn)和尾節(jié)點(diǎn)。 每一層的每一個(gè)每一個(gè)節(jié)點(diǎn)都含有指向同一層下一個(gè)節(jié)點(diǎn)和下一層同一個(gè)位置節(jié)點(diǎn)的指針。 如果一個(gè)節(jié)點(diǎn)在某一層出現(xiàn),那么該以下的所有鏈表同一個(gè)位置都會(huì)出現(xiàn)該節(jié)點(diǎn)。 具體實(shí)現(xiàn)的結(jié)構(gòu)圖如下所示:在跳躍表的結(jié)構(gòu)中有head和tail表示指向頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的指針,能快速的實(shí)現(xiàn)定位。level表示層數(shù),len表示跳躍表的長(zhǎng)度,BW表示后退指針,在從尾向前遍歷的時(shí)候使用。BW下面還有兩個(gè)值分別表示分值(score)和成員對(duì)象(各個(gè)節(jié)點(diǎn)保存的成員對(duì)象)。跳躍表的實(shí)現(xiàn)中,除了最底層的一層保存的是原始鏈表的完整數(shù)據(jù),上層的節(jié)點(diǎn)數(shù)會(huì)越來(lái)越少,并且跨度會(huì)越來(lái)越大。跳躍表的上面層就相當(dāng)于索引層,都是為了找到最后的數(shù)據(jù)而服務(wù)的,數(shù)據(jù)量越大,條表所體現(xiàn)的查詢(xún)的效率就越高,和平衡樹(shù)的查詢(xún)效率相差無(wú)幾。應(yīng)用場(chǎng)景因?yàn)閆Set是有序的集合,因此ZSet在實(shí)現(xiàn)排序類(lèi)型的業(yè)務(wù)是比較常見(jiàn)的,比如在首頁(yè)推薦10個(gè)最熱門(mén)的帖子,也就是閱讀量由高到低,排行榜的實(shí)現(xiàn)等業(yè)務(wù)。下面就選用獲取排行榜前前10名的選手作為案例實(shí)現(xiàn),實(shí)現(xiàn)的代碼如下所示:```javascript @Autowired private RedisTemplate redisTemplate; /*** 獲取前10排名* @return*/public static List<levelVO > getZset(String key, long baseNum, LevelService levelService){ZSetOperations<Serializable, Object> operations = redisTemplate.opsForZSet();// 根據(jù)score分?jǐn)?shù)值獲取前10名的數(shù)據(jù)Set<ZSetOperations.TypedTuple<Object>> set = operations.reverseRangeWithScores(key,0,9);List<LevelVO> list= new ArrayList<LevelVO>();int i=1;for (ZSetOperations.TypedTuple<Object> o:set){int uid = (int) o.getValue();LevelCache levelCache = levelService.getLevelCache(uid);LevelVO levelVO = levelCache.getLevelVO();long score = (o.getScore().longValue() - baseNum + levelVO .getCtime())/CommonUtil.multiplier;levelVO .setScore(score);levelVO .setRank(i);list.add( levelVO );i++;}return list;}原文地址:https://mp.weixin.qq.com/s/F5Uq0V9jWHpvfb94bTmaow
總結(jié)
以上是生活随笔為你收集整理的Redis五种数据结构详解的全部?jī)?nèi)容,希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇: 分布式消息技术 Kafka
- 下一篇: HashMap、Hashtable、Co