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

相关文章

来自专栏云霄雨霁

字符串查找----R向单词查找树

850
来自专栏GreenLeaves

Oracle PL/SQL编程之变量

注: 以下测试案例所用的表均来自与scott方案,使用前,请确保该用户解锁. 1、简介 和大多数编程语言一样,在编写PL/SQL程序时,可以定义常量和变量,在p...

1817
来自专栏从流域到海域

《笨办法学Python》 第30课手记

《笨办法学Python》 第30课手记 本节课讲if语句的嵌套,和c的差别仅仅是将else if简写成elif,其余类似。 原代码如下: people = 30...

1697
来自专栏blackheart的专栏

[C#1] 2-类型基础

1.System.Object CLR要求每个类型都要继承自System.Object[直接或者间接方式],如果不显示继承,编译器会自动为我们添加对System...

1817
来自专栏JetpropelledSnake

Python入门之python可变对象与不可变对象

本文分为如下几个部分 概念 地址问题 作为函数参数 可变参数在类中使用 函数默认参数 类的实现上的差异 概念 可变对象与不可变对象的区别在于对象本身是否可变。 ...

2706
来自专栏Phoenix的Android之旅

你所不知道的 equals()

在基本运算符中, == 扮演一个重要的角色, 而跟它相似的还有个 equals()方法, 这两个的区别是什么你知道么。

582
来自专栏python全栈布道师

2017年8月28日技术日记

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

Java直接(堆外)内存使用详解

本篇主要讲解如何使用直接内存(堆外内存),并按照下面的步骤进行说明: 相关背景-->读写操作-->关键属性-->读写实践-->扩展-->参考说明 希望对想使用直...

1869
来自专栏大闲人柴毛毛

Java中被你忽视的四种引用

正文开始前,有必要先了解下Java内存分配与回收,请见我的相关博文。 —————————————————————————————————— Java的数据类型分...

3147
来自专栏微信公众号:Java团长

探究Java虚拟机栈

Java 虚拟机的内存模型分为两部分:一部分是线程共享的,包括 Java 堆和方法区;另一部分是线程私有的,包括虚拟机栈和本地方法栈,以及程序计数器这一小部分内...

532

扫描关注云+社区