(编辑:jimmy 日期: 2024/12/23 浏览:2)
数组:
数组会在内存中开辟一块连续的空间存储数据,这种存储方式有利也有弊端。当获取数据的时候,直接通过下标值就可以获取到对应的元素,时间复杂度为O(1)。但是如果新增或者删除数据会移动大量的数据,时间复杂度为O(n)。数组的扩容机制是:如果数组空间不足,会先开辟一块新的空间地址,将原来的数组复制到新的数组中。
链表:
链表不需要开辟连续的内存空间,其通过指针将所有的数据连接起来。新增或者删除的时候只需要将指针指向的地址修改就行了,时间复杂度为O(1)。但是查询的时间复杂度为O(n)。
2.1、双向链表
双向链表是各个节点之间的逻辑关系是双向的。
双向链表中节点的组成是:prior:
指向当前节点的前置节点,data:
当前节点存储的数据。next:
指向当前节点的后置节点。
2.2、压缩链表
2.3、quicklist链表
A doubly linked list of ziplists A generic doubly linked quicklist implementation
quicklist是一个双向链表,并且是一个ziplist的双向链表,ziplist本身是一个维持数据项先后顺序的列表,而且数据项保存在一个连续的内存块种。
3.1、双向链表
3.2、压缩列表
3.3、quicklist链表
在redis 3.2版本之前使用的是 双向链表和压缩链表 两种,因为双向链表占用的内存要比压缩链表高,所以创建链表时首先会创建压缩链表,在合适的时机会转化成双向链表。redis 3.2之后使用的是quicklist链表。