Redis之链表

• • 链表在Redis中的作用
  • • 链表节点
    • 链表结构
    • 链表示意图
    • 总结 : 链表的特点

• 在Redis3.0之前中list底层可以用linkedlist来实现(数据少和小), 也可以用ziplist(数据大或者多)实现
• 在Redis3.0之后, list多用linkedlist和ziplist一起来实现, 叫quicklist(之后的章节会讲)

既然讲到了链表, 那么其中的节点是如何实现的那么必须要知道, 其实和java中linkedlistNode差不多

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

• 一个指向前面节点的prev指针
• 一个指向后面节点的next指针
• void* 代表可用存储任何数据, value域存储数据

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;

• 一个指向头结点的指针 head(方便插入和删除)
• 一个指向尾节点的指针 tail(方便插入和删除)
• 复制节点的函数 dup
• 释放节点的函数 free
• 节点对比函数 match
• 节点数量 len(就不需要去遍历链表来获取长度以便达到O(1))

下图就是大概的示意图, 帮助理解

1. 双端 : 获取某一个节点的前驱和后驱节点的复制度都为O(1)

2. 无环 : head节点的prev和tail节点的next都为NULL, 不会产生环状

3. 有链表长度计数器 : 拥有len字段,可以直接获取链表长度

4. 有表头节点和表尾节点, 获取节点复杂度为O(1)