首頁 > 資料庫 > Redis > 主體

深入聊聊Redis中的雙鍊錶

青灯夜游
發布: 2021-12-01 09:53:25
轉載
2166 人瀏覽過

這篇文章帶大家了解一下Redis 資料結構中的雙鍊錶,簡單介紹一下雙鍊錶的運用,希望對大家有幫助!

深入聊聊Redis中的雙鍊錶

在Redis 資料類型中的列表list,對資料的新增和刪除常用的指令有lpush,rpush,lpop,rpop,其中l表示在左側,r 表示在右側,可以在左右兩側做新增和刪除操作,說明這是一個雙向的資料結構,而list 資料結構正是雙向鍊錶,類似java 中的LinekdList 鍊錶列表。 【相關推薦:Redis影片教學

鍊錶提供了高效的節點重排能力,以及順序的節點存取方式,透過修改節點的pre 和next 指標來修改鍊錶的數據。

C 語言沒有內建鍊錶的資料結構,所以 Redis 建構了自己的鍊錶結構。

鍊錶的資料結構,鍊錶以及鍊錶節點

鍊錶是由鍊錶以及鍊錶節點組成,每個鍊錶節點使用一個adlist.h/listNode 結構來表示:

typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    // 节点值
    void *value;
} listNode;
登入後複製

多個listNode 可以透過prev 和next 指標組成雙鍊錶的,如題所示:

深入聊聊Redis中的雙鍊錶

多個listNode 可以組成鍊錶,但為了方便管理,使用adlist.h/list 管理鍊錶,list 結構如下:

typedef struct list {
    // 列表头结点
    listNode *head;
    // 列表尾结构
    listNode *tail;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数 
    int (*match)(void *ptr, void *key);
    // 列表节点数量
    unsigned long len;
} list;
登入後複製

list 結構為鍊錶提供了表頭指標head、表尾指標tail,以及節點數計算len 。下圖展示一個由list 結構和三個listNode 節點組成的鍊錶:

深入聊聊Redis中的雙鍊錶

#Redis 鍊錶實作的特徵有如下的總結:

  • 雙向:鍊錶節點帶有prev 和next 指針,可以透過指針取得每一個資料
  • 快速計算鍊錶長度:透過list 結構中的len 屬性計算list 的長度,而時間複雜度為O(1)
  • 多態: 鍊錶節點使用void* 指標保存節點,所以鍊錶支援保存各種不同類型的值

雙鍊錶的運用

列表鍵,發布訂閱、慢查詢以及監視器等。

總結

  • 本文透過介紹鍊錶的資料結構,鍊錶是由鍊錶和鍊錶節點組成的
  • 鍊錶節點都有一個前置和後置指針,所以Redis 的鍊錶是一個雙向鍊錶
  • 鍊錶可以儲存頭結點,尾節點,更好的管理自己的節點,len 屬性快速算出鍊錶的長度
  • 鍊錶通過void*以及不同的類型設定函數,所以鍊錶可以不同的類型的值

更多程式相關知識,請造訪:程式設計入門! !

以上是深入聊聊Redis中的雙鍊錶的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:juejin.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板