Redis數(shù)組和鏈表深入詳解

1.數(shù)組和鏈表基礎(chǔ)知識(shí)

數(shù)組：
數(shù)組會(huì)在內(nèi)存中開(kāi)辟一塊連續(xù)的空間存儲(chǔ)數(shù)據(jù)，這種存儲(chǔ)方式有利也有弊端。當(dāng)獲取數(shù)據(jù)的時(shí)候，直接通過(guò)下標(biāo)值就可以獲取到對(duì)應(yīng)的元素，時(shí)間復(fù)雜度為O(1)。但是如果新增或者刪除數(shù)據(jù)會(huì)移動(dòng)大量的數(shù)據(jù)，時(shí)間復(fù)雜度為O(n)。數(shù)組的擴(kuò)容機(jī)制是：如果數(shù)組空間不足，會(huì)先開(kāi)辟一塊新的空間地址，將原來(lái)的數(shù)組復(fù)制到新的數(shù)組中。

鏈表：
鏈表不需要開(kāi)辟連續(xù)的內(nèi)存空間，其通過(guò)指針將所有的數(shù)據(jù)連接起來(lái)。新增或者刪除的時(shí)候只需要將指針指向的地址修改就行了，時(shí)間復(fù)雜度為O(1)。但是查詢的時(shí)間復(fù)雜度為O(n)。

2、鏈表

2.1、雙向鏈表

雙向鏈表是各個(gè)節(jié)點(diǎn)之間的邏輯關(guān)系是雙向的。
雙向鏈表中節(jié)點(diǎn)的組成是：prior： 指向當(dāng)前節(jié)點(diǎn)的前置節(jié)點(diǎn)，data：當(dāng)前節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)。next：指向當(dāng)前節(jié)點(diǎn)的后置節(jié)點(diǎn)。

2.2、壓縮鏈表

• 壓縮鏈表是為了節(jié)約內(nèi)存開(kāi)發(fā)的。
• ziplist是一個(gè)特別的雙向鏈表，沒(méi)有維護(hù)雙向指針prev next;反而是存儲(chǔ)上一個(gè)entry的長(zhǎng)度和當(dāng)前entry長(zhǎng)度，通過(guò)長(zhǎng)度推算出下一個(gè)元素在什么地方。
• 犧牲讀取的性能，獲得高效的存儲(chǔ)空間，因?yàn)榇鎯?chǔ)指針比存儲(chǔ)entry長(zhǎng)度更費(fèi)內(nèi)存，這就是典型的時(shí)間換空間。

2.3、quicklist鏈表

• 官網(wǎng)介紹：

A doubly linked list of ziplists
A generic doubly linked quicklist implementation

• 介紹:

quicklist是一個(gè)雙向鏈表，并且是一個(gè)ziplist的雙向鏈表，ziplist本身是一個(gè)維持?jǐn)?shù)據(jù)項(xiàng)先后順序的列表，而且數(shù)據(jù)項(xiàng)保存在一個(gè)連續(xù)的內(nèi)存塊種。

3、對(duì)比

3.1、雙向鏈表

• 雙端鏈表便于在表的兩端進(jìn)行push和pop操作，但是它的內(nèi)存開(kāi)銷(xiāo)比較大。
• 雙端鏈表每個(gè)節(jié)點(diǎn)上除了要保存的數(shù)據(jù)之外，還要額外保存兩個(gè)指針。
• 雙端鏈表的各個(gè)節(jié)點(diǎn)是單獨(dú)的內(nèi)存塊，地址不連續(xù)，節(jié)點(diǎn)多了容易產(chǎn)生內(nèi)存碎片。

3.2、壓縮列表

• ziplist由于是一塊連續(xù)的內(nèi)存，所以存儲(chǔ)效率很高。
• ziplist不利于修改操作，每次數(shù)據(jù)變動(dòng)都會(huì)引發(fā)一次內(nèi)存的realloc。
• 當(dāng)ziplist長(zhǎng)度很長(zhǎng)的時(shí)候，一次realloc可能會(huì)導(dǎo)致大批量的數(shù)據(jù)拷貝，進(jìn)一步降低性能。

3.3、quicklist鏈表

• 空間效率和時(shí)間效率的折中。
• 結(jié)合了雙端鏈表和壓縮列表的優(yōu)點(diǎn)。

4、總結(jié)

在redis 3.2版本之前使用的是 雙向鏈表和壓縮鏈表 兩種，因?yàn)殡p向鏈表占用的內(nèi)存要比壓縮鏈表高，所以創(chuàng)建鏈表時(shí)首先會(huì)創(chuàng)建壓縮鏈表，在合適的時(shí)機(jī)會(huì)轉(zhuǎn)化成雙向鏈表。redis 3.2之后使用的是quicklist鏈表。

到此這篇關(guān)于Redis數(shù)組和鏈表深入詳解的文章就介紹到這了,更多相關(guān)Redis數(shù)組和鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！