Redis 資料結構-雙向鏈表
最是人間留不住，朱顏辭鏡花辭樹，
1、簡介
Redis 之所以快主要得益于它的資料結構、操作記憶體資料庫、單執行緒和多路 I/O 復用模型，進一步窺探下它常見的五種基本資料的底層資料結構，
Redis 常見資料型別對應的的底層資料結構，
- String：簡單動態字串，
- List：雙向鏈表、壓縮串列，
- Hash：壓縮串列、哈希表，
- Sorted Set：壓縮串列、跳表，
- Set：哈希表、整數陣列，
2、雙向鏈表
C 語言是沒有內置鏈表這種結構，而當一個串列鍵包含較多的元素，或者串列中包含的元素都是比較長的字串的時，Redis 就會使用鏈表作為 list 的底層實作，就自己實作了雙向鏈表，相當于Java 語言中的LinkedList，但又不完全是，
單純的鏈表優缺點：
- 雙向鏈表資料結構，支持前后順序遍歷，
- 不需要連續的的記憶體空間，插入和洗掉的時間復雜度是 O(1) 級別的，效率較高，
- 比起陣列它的缺點就是查詢較慢（時間復雜度O(n)），
常見使用場景
雙向鏈表的特性經常被用于異步佇列的使用，實際開發中將需要延后處理的任務結構體序列化成字串，放入Redis 的佇列中，另一個執行緒從這個串列中獲取資料進行后續的業務邏輯，
鏈表節點結構
從redis/src/adlist.h 原始碼檔案中查看鏈表節點結構設計，
1 typedef struct listNode { 2 struct listNode *prev; // 前置節點，如果是list的頭結點，則prev指向NULL 3 struct listNode *next;// 后置節點，如果是list尾部結點，則next指向NULL 4 void *value; // 記錄該節點的值，能夠存放任何資訊（也叫萬能節點） 5 } listNode;
從listNode 結構中看到一個節點由頭指標 prev 、尾指標 next 以及節點的值 value 組成，這種有前置節點和后置節點很明顯就是一個雙向鏈表，
鏈表結構
為了方便操作，Redis 在 listNode 鏈表節點結構體基礎上又封裝了 list 這個資料結構，而且封裝之后，還提供了頭節點、尾節點以及一些自定義的函式，鏈表結構如下：
1 typedef struct list { 2 listNode *head; // 鏈表 頭結點 指標 3 listNode *tail; // 鏈表 尾結點 指標 4 unsigned long len; // 鏈表長度計數器 即 節點的個數 5 6 // 三個函式指標 7 void *(*dup)(void *ptr); // 復制函式 復制鏈表節點保存的值 8 void (*free)(void *ptr); // 釋放函式 釋放鏈表節點保存的值 9 int (*match)(void *ptr, void *key); // 匹配函式 查找節點時使用 比較鏈表節點所保存的節點值和另一個輸入的值是否相等 10 } list;
list 結構為鏈表提供了鏈表頭指標 head、鏈表尾節點 tail、鏈表節點數量 len、以及可以自定義實作的 dup、free、match 函式，
- head：鏈表 頭結點 指標，指向了雙向鏈表的最開始的一個節點；
- tail：鏈表 尾結點 指標，指向了雙向鏈表的最后一個節點；
- len：代表了雙向鏈表節點的數量；
- dup：復制函式，用于復制雙向鏈表節點所保存的值；
- free：釋放函式，用于釋放雙向鏈表節點所保存的值；
- match：匹配函式，用于對比雙向鏈表節點所保存的值和另外一個的輸入值是否相等，
相關命令
右進左出（佇列）
佇列在結構上是先進先出（FIFO）的資料結構（比如排隊購票的順序），常見場景如訊息排隊、異步處理等，用于確保元素的訪問順序，
lpush -> 從左邊邊添加元素
127.0.0.1:6379> lpush tjt_list 1 2 3
rpush -> 從右邊添加元素
127.0.0.1:6379> rpush tjt_list 1 2 3
llen -> 獲取串列的長度
127.0.0.1:6379> llen tjt_list
lpop -> 從左邊彈出元素
127.0.0.1:6379> lpop tjt_list
右進右出（堆疊）
堆疊在結構上是先進后出（FILO）的資料結構（比如彈夾壓入子彈，子彈被射擊出去的順序就是堆疊），這種資料結構一般用來處理一些逆序輸出的業務場景，
lpush -> 從左邊邊添加元素
127.0.0.1:6379> lpush tjt_list 1 2 3
rpush -> 從右邊添加元素
127.0.0.1:6379> rpush tjt_list 1 2 3
rpop -> 從右邊彈出元素
127.0.0.1:6379> rpop tjt_list
慢操作
由于串列(list)的鏈表資料結構，它的遍歷是慢操作，所以涉及到遍歷的性能將會隨著遍歷區間range 的增大而增大，在Redis 鏈表中，list 的索引運行為負數，-1代表倒數第一個，-2代表倒數第二個，其它同理，
lindex -> 遍歷獲取串列指定索引處的值(下方所有為 0)
127.0.0.1:6379> lindex tjt_list 0 "you"
lrange -> 獲取從索引start 到stop 處的全部值
127.0.0.1:6379> lrange tjt_list 0 -1 1) "you" 2) "will" 3) "never" 4) "know"
ltrim -> 截取并保存索引start 到stop 處的全部值，其它將會被洗掉
127.0.0.1:6379> ltrim tjt_list 1 -1 OK 127.0.0.1:6379> lrange tjt_list 0 -1 1) "will" 2) "never" 3) "know"
非普通LinkedList
前面提到了Redis 資料型別List 對應的的底層資料結構有 雙向鏈表 和 壓縮串列，因為 Redis底層存盤list(串列)不是一個簡單的LinkedList，而是quicklist 快速串列，
為什么用quicklist 替代LinkedList
普通的LinkedList node節點元素，都會持有一個prev-> 執行前一個node 節點和next-> 指向后一個node 節點的指標（參考），這種結構雖然支持前后順序遍歷，但是也帶來了不小的記憶體開銷，如果node 節點僅僅是一個int 型別的值，那么參考的記憶體比例將會更大，所以Redis 底層對于list(串列)的存盤，當元素個數少的時候，它會使用一塊連續的記憶體空間來存盤，這樣可以減少每個元素增加prev 和next 指標帶來的記憶體消耗，減少記憶體碎片化問題，
quicklist
quicklist 是多個ziplist (壓縮串列)組成的雙向串列，
ziplist
ziplist是一塊連續的記憶體地址，他們之間無需持有prev和next指標，能通過地址順序尋址訪問，
3、鏈表小結
鏈表優勢
- listNode 鏈表節點的結構里帶有 prev 和 next 指標，獲取某個節點的前置節點或后置節點的時間復雜度只需O(1)，而且這兩個指標都可以指向 NULL，所以鏈表是無環鏈表，對雙向鏈表的訪問以 NULL 結束；
- list 結構因為提供了表頭指標 head 和表尾節點 tail，所以獲取鏈表的表頭、表尾節點的時間復雜度都是 O(1)；
- list 結構因為提供了鏈表節點數量 len，通過 len 屬性直接獲取節點的數量，時間復雜度為 O(1) , 效率高；
- listNode 鏈表節使用 void* 指標保存節點值，并且可以通過 list 結構的 dup、free、match 函式指標為節點設定該節點型別特定的函式，因此鏈表節點可以保存各種不同型別的值，
?鏈表缺陷
- 鏈表每個節點之間的記憶體都是不連續的，無法很好利用 CPU 快取，陣列資料結構就能很好利用 CPU 快取，因為陣列的記憶體是連續的，可以充分利用 CPU 快取來加速訪問，
- 保存一個鏈表節點的值每次都需要為一個鏈表節點結構頭分配空間，記憶體開銷較大，Redis 3.0 的 List 物件在資料量比較少的情況下，會采用 壓縮串列 作為底層資料結構的實作，節省記憶體空間，降低保存鏈表節點的記憶體開銷，
最是人間留不住 朱顏辭鏡花辭樹
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/541647.html
標籤：其他