Redis数组和链表深入详解

1.数组和链表基础知识

数组：
数组会在内存中开辟一块连续的空间存储数据，这类存储方式有益也有弊端。当获得数据的时候，直接通过下标值就能够获得到对应的元素，时间复杂度为O(1)。但是如果新增或删除数据会移动大量的数据，时间复杂度为O(n)。数组的扩容机制是：如果数组空间不足，会先开辟一块新的空间地址，将原来的数组复制到新的数组中。

链表：
链表不需要开辟连续的内存空间，其通过指针将所有的数据连接起来。新增或删除的时候只需要将指针指向的地址修改就好了，时间复杂度为O(1)。但是查询的时间复杂度为O(n)。

2、链表

2.1、双向链表

双向链表是各个节点之间的逻辑关系是双向的。
双向链表中节点的组成是：prior： 指向当前节点的前置节点，data：当前节点存储的数据。next：指向当前节点的后置节点。

2.2、紧缩链表

• 紧缩链表是为了节俭内存开发的。
• ziplist是一个特别的双向链表，没有保护双向指针prev next;反而是存储上一个entry的长度和当前entry长度，通太长度推算出下一个元素在甚么地方。
• 牺牲读取的性能，取得高效的存储空间，由于存储指针比存储entry长度更费内存，这就是典型的时间换空间。

2.3、quicklist链表

• 官网介绍：

• 介绍:

quicklist是一个双向链表，并且是一个ziplist的双向链表，ziplist本身是一个保持数据项前后顺序的列表，而且数据项保存在一个连续的内存块种。

3、对照

3.1、双向链表

• 双端链表便于在表的两端进行push和pop操作，但是它的内存开消比较大。
• 双端链表每一个节点上除要保存的数据以外，还要额外保存两个指针。
• 双端链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。

3.2、紧缩列表

• ziplist由因而一块连续的内存，所以存储效力很高。
• ziplist不利于修改操作，每次数据变动都会引发一次内存的realloc。
• 当ziplist长度很长的时候，一次realloc可能会致使大批量的数据拷贝，进一步下降性能。

3.3、quicklist链表

• 空间效力和时间效力的折衷。
• 结合了双端链表和紧缩列表的优点。

4、总结

在redis 3.2版本之前使用的是 双向链表和紧缩链表 两种，由于双向链表占用的内存要比紧缩链表高，所以创建链表时首先会创建紧缩链表，在适合的时机会转化成双向链表。redis 3.2以后使用的是quicklist链表。

到此这篇关于Redis数组和链表深入详解的文章就介绍到这了,更多相关Redis数组和链表内容请搜索之前的文章或继续浏览下面的相关文章希望大家以后多多支持！