Redis中數(shù)組和鏈表的關(guān)系是什么

Redis中數(shù)組和鏈表的關(guān)系是什么？針對這個問題，這篇文章詳細(xì)介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

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

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

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

2、鏈表

2.1、雙向鏈表

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

2.2、壓縮鏈表

• 壓縮鏈表是為了節(jié)約內(nèi)存開發(fā)的。

• ziplist是一個特別的雙向鏈表，沒有維護雙向指針prev next;反而是存儲上一個entry的長度和當(dāng)前entry長度，通過長度推算出下一個元素在什么地方。

• 犧牲讀取的性能，獲得高效的存儲空間，因為存儲指針比存儲entry長度更費內(nèi)存，這就是典型的時間換空間。

2.3、quicklist鏈表

• 官網(wǎng)介紹：

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

• 介紹:

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

3、對比

3.1、雙向鏈表

• 雙端鏈表便于在表的兩端進行push和pop操作，但是它的內(nèi)存開銷比較大。

• 雙端鏈表每個節(jié)點上除了要保存的數(shù)據(jù)之外，還要額外保存兩個指針。

• 雙端鏈表的各個節(jié)點是單獨的內(nèi)存塊，地址不連續(xù)，節(jié)點多了容易產(chǎn)生內(nèi)存碎片。

3.2、壓縮列表

• ziplist由于是一塊連續(xù)的內(nèi)存，所以存儲效率很高。

• ziplist不利于修改操作，每次數(shù)據(jù)變動都會引發(fā)一次內(nèi)存的realloc。

• 當(dāng)ziplist長度很長的時候，一次realloc可能會導(dǎo)致大批量的數(shù)據(jù)拷貝，進一步降低性能。

3.3、quicklist鏈表

• 空間效率和時間效率的折中。

• 結(jié)合了雙端鏈表和壓縮列表的優(yōu)點。

關(guān)于Redis中數(shù)組和鏈表的關(guān)系是什么問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。