每个程序员都应该知道的Redis知识 - List类型底层原理

本文将继续讲解Reids知识之List类型的实现原理。**我们知道Redis的list类型给我们提供了很多操作数据的命令(详细命令见文章末尾),比如 LPUSH 可以将一个或多个值插入到列表头部,LRANGE 可以获取指定范围内的元素。由此我们产生了一个疑问,这些在底层是如何实现的?

在这里插入图片描述


前面文章讲解了Redis知识框架和String原理,文章链接如下:
《每个程序员都应该知道的Redis知识》、《每个程序员都应该知道的Redis知识 - String底层原理》

**本文将继续讲解Reids知识之List类型的实现原理。**我们知道Redis的list类型给我们提供了很多操作数据的命令(详细命令见文章末尾),比如 LPUSH 可以将一个或多个值插入到列表头部,LRANGE 可以获取指定范围内的元素。由此我们产生了一个疑问,这些在底层是如何实现的?


我将从以下两个方面介绍List类型:

  • List类型的实现原理
  • List中各个命令的查询原理

在这里插入图片描述


一、List类型实现原理


List的底层是实现是链表,说到链表不得不提的就是数组。那么链表和数组两种数据结构有什么不同呢?

数组是顺序存储的,在内存中的存储方式是连续的;链表是链式存储,在内存中是非连续性存储

访问数组中的数据的时间复杂度是O(1),而链表必须从表头顺序去访问,时间复杂度是O(n)

链表上任意节点删除效率比数组高


Redis的List类型底层是通过list和listNode两个结构体实现,代码见下图:

在这里插入图片描述


从上图可以看出,listNode是一个双向链表的节点,多个listNode通过prev和next指针组成双端链表。

在这里插入图片描述

在这里插入图片描述


为了更加方便的操作,使用list结构体来持有链表。list结构为链表提供了表头指针head、表尾指针tail,以及链表节点数量len,dup、free、match成员则是为了实现链表功能而提供的接口。

dup函数用于复制链表节点所保存的值
free函数用于释放链表节点所保存的值
match函数用于对比链表节点所保存的值和另一个输入值是否相等由list结构和listNode组成的链表如下图所示,这就是Redis中list类型的实现。

在这里插入图片描述


通过上图我们可以发现:

链表是双端结构,listNode结构体中带有prev和next指针,因此获取某个节点的前置节点和后继节点的时间复杂度都是O(1)

这个链表无环:表头节点的prev和表尾节点的next指针都指向了NULL,对链表的访问以NULL为终点

带表头指针和表尾指针:通过list结构的head指针和tail指针,程序获取链接的表头节点和表尾节点的时间复杂度为O(1)

带有链表长度计数器:程序使用list结构体的len属性来对list持有的链表节点进行计数,程序获取链表中节点数量的复杂度为O(1)

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


二、List中各个命令是如何实现的?


以上就是list类型的实现,下面我们用具体的命令来验证一下,底层是如何实现数据增删改查的。

**BLPOP key1:**这个命令是从链表的头部移出并获取返回移出的值。从上图可以看出,list结构体持有整个链表,通过head指针用O(1)的时间复杂度就可以找到链表第一个节点,然后通过链表删除某个节点的操作就可以移除节点。BRPOP key 的操作也类似,通过list链表的tail指针就可以使用O(1)的时间复杂度找到节点,剩下的操作类似

**LLEN key:**这个命令是获取链表的长度,因为list结构体中已经存储了链表长度len,多以查询的时间复杂度是O(1)

**LPUSH key value:**这个命令是将一个或多个值插入到链表头部。同样也是通过list链表中的head指针来实现链表的插入

从上面的几个例子可以看出,Redis中对list类型的增删改成都是通过对双向链表的增删改查来实现的。关于链表的增删改查后面会专门写文章来介绍。

除此之外,我们看到list结构体中设置了len属性,查询链表长度就不需要遍历整个链表,这也是一种空间换时间的思想。

这篇文章就为大家介绍到这里,如有不足,还请见谅!


为方便大家查找命令,下面列出了Redis命令列表:

在这里插入图片描述

在这里插入图片描述


在这里插入图片描述

  • 发表于 2020-08-22 09:39
  • 阅读 ( 154 )
  • 分类:分布式

0 条评论

请先 登录 后评论
阿梓
阿梓

879 篇文章

作家榜 »

  1. 阿梓 879 文章
  2. p270228163 0 文章
  3. 陈洋 0 文章
  4. 维子老师 0 文章
  5. gyy 0 文章
  6. 花橙 0 文章
  7. 朱利海 0 文章
  8. 小熊 0 文章