原创代码,Java

Redis底层数据结构--链表

本文阅读 2 分钟
首页 代码,Java 正文

1.简介

当一个列表键包含了数量比较多的元素,又或者列表中包含的元素都是比较长的字符串时,Redis就会使用链表作为列表键的底层实现。

除了链表键之外,发布与订阅、慢查询、监视器等功能也用到了链表,Redis服务器本身还使用链表来保存多个客户端的状态信息,以及使用链表来构建客户端输出缓冲区。

2.链表和链表节点的定义和实现

链表节点的结构如下:

typedef struct listNode{
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
} listNode;

多个listNode可以通过prev和next指针组成双端链表,如下图:
01.png

list链表的结构如下:

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

在Redis中,我们使用list结构来持有链表,如下图是一个list和三个listNode节点组成的链表:
02.png

Redis链表特性:

  • 双端:链表节点有prev和next指针,获取前置节点和下一节点实践复杂度都是O(1);
  • 无环:表头节点的prev和表尾节点的next都指向NULL,对链表的访问以NULL终止;
  • 带表头指针和表尾指针;
  • 带节点计数器;
  • 多态:使用void*指针来保存节点的值。

参考书籍:Redis设计与实现

原创文章,作者:纸飞机-JAVA追梦,如若转载,请注明出处:https://www.zfjsec.com/1912.html
-- 展开阅读全文 --
Redis底层数据结构--简单动态字符串
« 上一篇 04-10
Redis底层数据结构--字典
下一篇 » 04-20

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复