redis本身是开源的C语言编写的k-v存储系统,他支持String、List、Set、ZSet、hash五种数据结构,每种数据结构底层是如何实现的?其数据结构为什么?
底层结构:指针+字符数组 时间复杂度:O(1)
Redis是C语言开发的,但在C语言中并没有字符串
类型,只能使用指针
和字符数组
的形式来保存一个字符串。所以Redis设计了一个简单的动态字符串(SDS [Simple Dynamic String])
来作为底层实现。
struct sdshdr{
//记录buf数组中已使用的字节的长度
int len;
//记录buf数组中剩余空间的长度
int free;
//字节数组,用于存储字符串
char buf[];
}
底层结构:双向链表 时间复杂度:查询效率为O(n)。但是访问两端元素的时间复杂度O(1)
lRange
时间复杂度O(n);lpop
时间复杂度O(1);lpush key value1 value2 value3... valueN
从list的左边添加一个或者多个元素 时间复杂度O(1~n)
;底层结构:quicklist
一个链表结构可以有序的存储多个字符串,拥有例如:lpush、lpop、rush、rpop等操作。在3.2版本之前,列表使用ziplist和linkedlist来实现。而在3.2版本之后,重新引入了一个quicklist的数据结构,列表的底层是由quicklist实现的,它结合了ziplist和linkedlist的优点。按照原文的解释是:【A doubly linked list of ziplist】
。存。
在老版本中,当列表对象同时满足一下两个条件时,列表将使用ziplist编码:
当有一个条件不满足时将进行一次转码,使用linkedlist。
ziplist
ziplist是一个经过特殊编码的双向链表,它设计的目的是为了提高存储的效率。一个普通的双向链表,链表中每一项都占用独立的一块内存,各项之间用地址指针(或引用)连接起来,但是这种方式会造成大量的内存碎片,而且地址指针也会占用额外的内存。
ziplist却是将表中每一项存放在前后连续的地址空间内
,一个ziplist整体占用一大块内存。它是一个表(list),但其实不是一个链表(linked list)
linkedlist
双向列表,插入和删除的效率高,但是查询的效率确实O(n)
quicklist
【A doubly linked list of ziplist】
ziplist组成的双向链表。它宏观上就是一个链表结构,只不过每一个节点都是以ziplist来存储数据,而ziplist中又包含多个entry。也可以说quicklist节点保存的是一片数据
在redis.conf
配置文件中,有两个参数可以优化:
3.1 结论
底层结构:ziplist或者hashtable 时间复杂度:O(1)
redis的散列可以存储多个键值对之间的映射。hash底层的数据结构实现其实有两种:
底层结构:整数集合(intset)或者字典(hashtable) 时间复杂度:O(1)
typedef struct intset{
//编码方式
uint32_t encoding;
//元素数量
uint32_t length;
//存储元素的数组
int8_t contents[];
}
整数集合中的每个元素都是contents数组
的一个数组项,各个项在数组中按值的大小进行有序排列,并且不包含重复的项。contents数组中的元素类型由encoding决定,没当加入新元素时,如果元素的编码大于contents数组元素的编码,则数组元素会整体升级,注意不会发生降级。
底层结构:ziplist或者skiplist(跳表) 时间复杂度:O(log(n))
力扣——1206. 设计跳表
跳表设计思路和链表相似,跳表中有很多层,每一层是一个短的链表。在第一层的作用下,增删查的时间复杂度不超过O(n)。跳表的每一个操作平均时间复杂度为 O(log(n)),空间复杂度是 O(n)。
跳跃表是一种有序的数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。跳表的期望空间复杂度为O(n)O(n),跳表的查询,插入和删除操作的期望时间复杂度都为O(logn)O(logn)。
Redis内部数据结构详解之跳跃表(skiplist)
跳表是一种随机化数据结构,基于并联的链表。