《Redis设计与实现》读书笔记(三) ——Redis中的链表

《Redis设计与实现》读书笔记(三) ——Redis中的链表

(原创内容,转载请注明来源,谢谢)

一、概述

链表在redis底层实现广泛,例如redis的list(列表)数据结构在底层就是用链表来实现的。链表提供了节点重排和顺序节点访问。

除了list,redis的发布订阅、慢查询、监视器等,也使用到了链表。redis还用链表保存多个客户端的状态信息,以及用链表来构建客户端的输出缓冲区。

二、链表和表节点的实现

1、节点结构

链表的节点结构,采用结构体,如下:

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

其中prev指向前一个节点,next指向后一个节点,value存储着节点本身的值。多个listNode组成双向链表,如下图所示:

2、链表结构

链表的结构也是采用结构体定义,如下:

typedef structlist{
listNode *head;
listNode *tail;
unsigned long len;
void *(*dup) (void *ptr);
void *(*free) (void *ptr);
int (*match) (void *ptr, void *key);
}

其中head和tail表示链表节点的开始节点和结束节点,len表示链表的长度,dup是节点的值复制函数,free是节点的值释放存储空间函数,match是节点的值比较函数(比较两个值是否相等)。

链表如下图所示:

三、redis链表结构综述

redis的链表特性如下:

1)双向,每个listNode节点带有prev和next指针,可以找到前一个节点和后一个节点,具有双向性。

2)无环,list链表的head节点的prev和tail节点的next指针都是指向null。

3)带表头指针和尾指针,即上述的head和tail,获取头指针和尾指针的时间复杂度O(1)。

4)带链表长度计数器,即list的len属性,记录节点个数,因此获取节点个数的时间复杂度O(1)。

5)多态,链表使用void*指针来保存节点的值,可以通过list的dup、free、match三个属性为节点值设置类型特定函数,所以链表可以用于保存不同类型的值。

四、总结

链表广泛用于redis的list、发布订阅、慢查询、监视器等地方;链表的每个节点由listNode结构实现,包含前置节点、后置节点指针以及节点值;链表本身由list结构实现,包含头尾指针、链表长度、链表的比较、复制、释放空间函数;另外redis的链表是双向、无环,通过为链表设定不同类型的特定函数,可以保存不同的值。

——written by linhxx 2017.08.29

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-08-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏LuckQI

Redis初识~List命令

962
来自专栏hrscy

Swift2.1-下标脚本下标脚本

类,结构体和枚举可以定义下标脚本,下标脚本可以认为是访问集合(collection),列表或序列的成员元素。你可是使用下标脚本来设置或通过索引检索值,而不需要调...

733
来自专栏企鹅号快讯

如何写好python代码

写代码好比画画,好的代码就像一件艺术品,美观、可读性高,让人看着舒服。代码是写给人看的,不是写给机器看的,遵守一定的代码规范很重要,就像写作文需要总分总结构,这...

3867
来自专栏前端那些事

复杂值vs原始值&&内存空间

写在前面      最近在读《JavaScript启示录》,这本书不是JavaScript的详尽的参考指南,但是把对象作为了解JavaScript的透镜,受益匪...

1857
来自专栏ccylovehs

再也不用被this苦恼了

前端编程对于this再熟悉不过了,今日来个老调重弹温故知新,肯定有很多大佬已经完全吃透了this原理,敬请出门左拐。对于理解this似懂非懂的同学可以借鉴一波

1052
来自专栏技术博客

C#项目代码规范

   小菜就是小菜,几个人搞出来的项目,让公司大牛稍微看了下,最后送出了惨不忍睹四个字。命名各种各样,五花八门,大写英文、小写英文、大写拼音、小写拼音、英文和拼...

1164
来自专栏前端小栈

转 javascript基础详解-执行环境与作用域链

函数调用都有与之相关的作用域和上下文。从根本上说,范围是基于函数(function-based)而上下文是基于对象(object-based)。换句话说,作用域...

531
来自专栏从零开始学 Web 前端

04 - JavaSE之异常处理

2.throw new someExpresion("错误原因"); 表示的是手动抛出异常。 **

1304
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之二进制中1的个数(九度OJ1513)

题目描述: 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 输入: 输入可能包含多个测试样例。 对于每个输入文件,第一行输入一个整数T,代表测...

1909
来自专栏云霄雨霁

Java--运行期类型鉴定(RTTI)

1585

扫码关注云+社区