《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 条评论
登录 后参与评论

相关文章

来自专栏前端小叙

JS中函数声明与函数表达式的异同

相同点 注:函数声明和函数表达式的相同点包括但不限于以下几点 函数是一个值,所以和其他值一样,函数也可以进行被输出、被赋值、作为参数传给其他函数等相关操作,不...

2635
来自专栏塔奇克马敲代码

第 16 章 模板与泛型编程

1152
来自专栏ASP.NETCore

动手实现扩展属性为对象动态添加获取数据(续)

在上一篇文章中我们了解了扩展属性的原理和结构,其实其内部结构与思想都与WPF中的依赖属性基本相同,大家也可以从中了解到关于依赖属性的原理,这对了解及使用依赖属性...

701
来自专栏CodingToDie

Python学习(六):函数的参数

第6 章 函数的参数 Table of Contents 位置参数 默认参数 可变参数 关键字参数 命名关键字参数 参数组合 每天步履匆匆,迎接新的战场,面对未...

4386
来自专栏程序员阿凯

java中“53”个关键字(含2个保留字)

1265
来自专栏Coding迪斯尼

自制Monkey语言编译器:解释执行return语句和错误处理控制

955
来自专栏林冠宏的技术文章

Deque的部分成员函数 解析,关于这个类,百度有很多解析,唯独没有其函数介绍

函数 描述 c.assign(beg,end) c.assign(n,elem) 将[beg; end)区间中的数据赋值给c。 ...

1728
来自专栏PHP技术

新手快速学习ES6语法,用最快的速度入门ES6就看这里

最近正在学习ES6,对于ES6的语法有一些自己的理解,想写这篇文章帮助跟我一样的新手快速入门ES6而不至于连代码都看不懂.至于开发环境的搭建什么的例如balel...

1073
来自专栏梦魇小栈

JQuery分析及实现part5之事件模块功能及实现

884
来自专栏大学生计算机视觉学习DeepLearning

python遍历文件 python创建XML对象 方法 python解析XML文件 提取ROI坐标计存入文件

1234

扫码关注云+社区