目錄
- 陣列和鏈表
- 鏈表
- 對比
- 總結
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鏈表，
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/265097.html
標籤：其他
上一篇：ClickHouse原始碼筆記4:FilterBlockInputStream, 探尋where，having的實作