Redis數組和鏈表深入詳解
1.數組和鏈表基礎知識
數組：
數組會在內存中開辟一塊連續的空間存儲數據，這種存儲方式有利也有弊端。當獲取數據的時候，直接通過下標值就可以獲取到對應的元素，時間復雜度為O(1)。但是如果新增或者刪除數據會移動大量的數據，時間復雜度為O(n)。數組的擴容機制是：如果數組空間不足，會先開辟一塊新的空間地址，將原來的數組復制到新的數組中。
鏈表：
鏈表不需要開辟連續的內存空間，其通過指針將所有的數據連接起來。新增或者刪除的時候隻需要將指針指向的地址修改就行瞭，時間復雜度為O(1)。但是查詢的時間復雜度為O(n)。
2、鏈表
2.1、雙向鏈表
雙向鏈表是各個節點之間的邏輯關系是雙向的。
雙向鏈表中節點的組成是：prior： 指向當前節點的前置節點，data：當前節點存儲的數據。next：指向當前節點的後置節點。
2.2、壓縮鏈表
- 壓縮鏈表是為瞭節約內存開發的。
- ziplist是一個特別的雙向鏈表，沒有維護雙向指針prev next;反而是存儲上一個entry的長度和當前entry長度，通過長度推算出下一個元素在什麼地方。
- 犧牲讀取的性能，獲得高效的存儲空間，因為存儲指針比存儲entry長度更費內存，這就是典型的時間換空間。
2.3、quicklist鏈表
- 官網介紹：
A doubly linked list of ziplists A generic doubly linked quicklist implementation
- 介紹:
quicklist是一個雙向鏈表，並且是一個ziplist的雙向鏈表，ziplist本身是一個維持數據項先後順序的列表，而且數據項保存在一個連續的內存塊種。
3、對比
3.1、雙向鏈表
- 雙端鏈表便於在表的兩端進行push和pop操作，但是它的內存開銷比較大。
- 雙端鏈表每個節點上除瞭要保存的數據之外，還要額外保存兩個指針。
- 雙端鏈表的各個節點是單獨的內存塊，地址不連續，節點多瞭容易產生內存碎片。
3.2、壓縮列表
- ziplist由於是一塊連續的內存，所以存儲效率很高。
- ziplist不利於修改操作，每次數據變動都會引發一次內存的realloc。
- 當ziplist長度很長的時候，一次realloc可能會導致大批量的數據拷貝，進一步降低性能。
3.3、quicklist鏈表
- 空間效率和時間效率的折中。
- 結合瞭雙端鏈表和壓縮列表的優點。
4、總結
在redis 3.2版本之前使用的是 雙向鏈表和壓縮鏈表 兩種，因為雙向鏈表占用的內存要比壓縮鏈表高，所以創建鏈表時首先會創建壓縮鏈表，在合適的時機會轉化成雙向鏈表。redis 3.2之後使用的是quicklist鏈表。
到此這篇關於Redis數組和鏈表深入詳解的文章就介紹到這瞭,更多相關Redis數組和鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！