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

前面文章讲解了String原理,文章链接如下:《每个程序员都应该知道的Redis知识 - String底层原理》本文将继续讲解Reids知识之List类型的实现原理。
我们知道Redis的list类型给我们提供了很多操作数据的命令(详细命令见文章末尾),比如 LPUSH 可以将一个或多个值插入到列表头部,LRANGE 可以获取指定范围内的元素。
由此我们产生了一个疑问,这些在底层是如何实现的?我将从以下两个方面介绍List类型:List类型的实现原理List中各个命令的查询原理别人家的程序员01List类型实现原理List的底层是实现是链表,说到链表不得不提的就是数组。
那么链表和数组两种数据结构有什么不同呢?数组是顺序存储的,在内存中的存储方式是连续的;链表是链式存储,在内存中是非连续性存储访问数组中的数据的时间复杂度是O(1),而链表必须从表头顺序去访问,时间复杂度是O(n)链表上任意节点删除效率比数组高Redis的List类型底层是通过list和listNode两个结构体实现,代码见下图:链表节点listNode从上图可以看出,listNode是一个双向链表的节点,多个listNode通过prev和next指针组成双端链表。
双端链表list链表为了更加方便的操作,使用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三个属性为节点值设置类型特定函数,所以链表可以用于保存不同类型的值02List中各个命令是如何实现的以上就是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属性,查询链表长度就不需要遍历整个链表,这也是一种空间换时间的思想。

返回列表
上一篇:
下一篇: