Redis 五种数据类型的数据结构

Redis 五种数据类型的数据结构

Redis 数据类型

Redis支持五种数据类型:string(字符串),hash(哈希),list(列表),set(集合)及zset(sorted set:有序集合)。

对应的底层数据结构一共有 6 种,分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。

在这里插入图片描述

String 类型的底层实现只有一种数据结构,也就是简单动态字符串。而 List、Hash、Set 和 Sorted Set 这四种数据类型,都有两种底层实现结构。通常情况下,我们会把这四种类型称为集合类型,它们的特点是一个键对应了一个集合的数据

简单动态字符串(simple dynamic string,SDS)

Redis没有直接使用C语言传统的字符串表示(以空字符结尾的字符数组,简称C字符串),而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型,并将其用作默认字符串表示

在构造简单动态字符串的时候,声明了两个额外的属性;free和len

free是记录buf数组中未使用字节的数量 len记录所保存字符串的长度

在这里插入图片描述

特点

1、SDS在len属性中记录了SDS本身的长度,所以获取其长度的时间复杂度仅为O(1)

2.杜绝缓冲区溢出由于C字符串不记录自身长度,容易造成缓冲区溢出(buffer overflow),例如拼接字符串时,为给s1分配足够空间,可能会造成s1内容溢出到s2上;

而SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性:当SDS API需要对SDS进行修改时,API会检查SDS的空间是否满足修改所需的要求,如果不满足,API会自动将SDS的空间扩展至执行修改所需的大小,然后才执行实际的修改操作,所以SDS不需手动修改SDS的空间大小 简而言之,SDS会先检查,后自动扩展,再操作。

双向链表

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

通过链表的指针逐个访问元素,操作复杂度基本是 O(N),操作效率比较低;

在这里插入图片描述

压缩列表

压缩列表实际上类似于一个数组,数组中的每一个元素都对应保存一个数据。和数组不同的是,压缩列表在表头有三个字段。

**zlbytes;**列表长度

**zltail :**列表尾的偏移量

**zllen:**列表中的 entry 个数

压缩列表在表尾还有一个 zlend,表示列表结束。

如果我们要查找定位第一个元素和最后一个元素,可以通过表头三个字段的长度直接定位,复杂度是 O(1)。而查找其他元素时,就没有这么高效了,只能逐个查找,此时的复杂度就是 O(N) 了。

在这里插入图片描述

跳表

跳表是redis的一个核心组件,也同时被广泛地运用到了各种缓存地实现当中,它的主要优点,就是可以跟红黑树、AVL等平衡树一样,做到比较稳定地插入、查询与删除。理论插入查询删除的算法时间复杂度为O(logN)。

跳表在链表的基础上**,增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位**,如下图所示:
在这里插入图片描述

在这里插入图片描述


版权声明:本文为Qiuyuguohou原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。