《Redis 设计与实践》读书笔记系列三:链表

要注意,这里的链表介绍不等同于Redis基础类型的List。链表在Redis中应用非常广泛,而C语言没有内置的链表结构,所以Redis用C实现了链表结构。

List中的键的底层实现之一就是链表,当List元素较多,或List元素值为较长字符串时,就会使用链表来存储List中的键。

127.0.0.1:6379> lrange demo 0 -1#这里的1,2,3,4是上述中所指的List中的键
1) "java"
2) "php"
3) "python"
4) "ruby"
127.0.0.1:6379> 

Redis中还有很多地方使用到了链表结构,如发布与订阅,慢查询,监视器等。后续其他章节会介绍到。

Redis中的链表底层结构是双向链表,即每个节点拥有上一个节点和下一个节点的指针,每个节点的结构名为:listNode。在此链表结构基础之上,Redis封装了一层,结构名称为:list。如下:

该结构相当于上一章节的简单动态字符串SDS,是一种Redis的基础结构,拥有自己的API

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;

该结构有两个属性分别指向了真实链表的头和尾,双向链表的结构(查找从头开始找),使其list相当于持有了该链表。

原生双向链表结构 Redis的list链表结构
获取头尾复杂度 头O(1),尾O(n) 均O(1)
获取链表长度复杂度 O(n) O(1)
API 没有 拥有多个API进行操作

简而言之,双向链表的优秀特性,list均拥有,list拥有的特性双向链表没有,因为list直接有个属性指向双向链表的头指针。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 2
Jyunwaa

过时的资料,现在是quicklist了

1年前 评论
巴啦啦 (楼主) 1年前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!