认识达内从这里开始

我们在上文中给大家简单介绍了Redis性能问题的一些基础知识，而今天我们就再来了解一下，Redis的数据类型与数据结构都有哪些。

一、Redis的数据类型

一般的键值对数据库只支持String一种数据类型，例如Memcached，而Redis支持的数据类型非常丰富，一共有5种，分别是String(字符串)、List(列表)、Hash(字典)、Set(集合)、SortSet(有序集合)。除String外，其余四种数据类型是集合类型。

Redis数据类型和底层数据结构的对应关系

String

String是简单的数据类型了，它是由简单动态字符串实现的。

List

List支持存储一组数据，有两种实现方式：压缩列表(ziplist)和双向循环链表。

Hash

Hash用来存储一组数据对，每个数据对又包含键和值两部分。Hash也有两种实现方式：压缩列表和哈希表。

Set

Set这种数据类型用来存储一组不重复的数据。有两种实现方式：有序数组和哈希表。

SortedSet

SortedSet用来存储一组数据，并且每个数据会附带一个得分。通过得分的大小，我们将数据组织成跳表这种数据结构，以支持快速地按照得分值、得分区间获得数据。

SortedSet也有两种实现方式：跳表和压缩列表。

二、Redis的数据结构

Redis底层一共有六种数据结构，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表、整数数组。

简单动态字符串(SDS)

与字符串本身不同，简单动态字符串(SDS)保留字符串长度信息，只需要O(1)就能得到字符串长度。

len：记录buf数据中已使用字节的数量

free：记录buf数组中未使用字节的数量

buf：字节数组，用于保存字符串

双向链表

双向链表是节点保存前置和后置节点的指针的链表结构。

压缩列表

类似于数组，但与数组不同的是，压缩列表在表头有三个字段(zlbytes、zltail、zllen)和表名有一个字段(zlend)。

查找一个元素和后一个元素只需要O(1)，其他O(n)。

zlbytes：列表长度

zltail：列表层的偏移量

zllen：列表中的entry个数

entrylist：列表数组

zlend：表示列表结束

哈希表

一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。

哈希表大的好处是查找元素只需要O(1)时间复杂度，但随着哈希表写入大量数据后，就可能出现操作变慢的情况，这是因为哈希表的冲突问题和rehash可能带来的操作阻塞。

为什么哈希表操作变慢了?

当哈希表中写入大量数据时，哈希冲突是不可避免的。这里的哈希冲突指的是两个key的哈希值相同，落在同一个哈希桶中。

Redis解决哈希冲突的方式是：链式哈希，即同一个哈希桶中的多个元素用一个链表来保存。

但这里还存在一个问题，哈希冲突链上查找元素的时间复杂度是O(N)，当哈希冲突链过长，查找元素耗时长，效率降低。这对Redis来说是不能接受的。

所以Redis会对哈希表做rehash操作。rehash就是增加现有的哈希桶数量，即扩容。

Redis执行rehash有三步：

给哈希表2分配更大的空间，例如是当前哈希表1大小的两倍;

把哈希表1中的数据重新映射并拷贝到哈希表2中;

释放哈希表1的空间。

这个过程看似简单，但是步骤2涉及大量的数据拷贝，如果一次性把数据都迁移完，会造成Redis线程阻塞，无法处理其他请求。

为了避免这个问题，Redis采用了渐进式rehash。

简单来说，就是把步骤2拷贝数据这一次性开销分摊到多次请求里，例如请求key1，会把key1所在的哈希桶从哈希表1迁移到哈希表2里，直到所有哈希桶都迁移到哈希表2里。在这个过程里，哈希表1要一直保留，等到迁移完成后才释放。

除了键值对请求操作进行数据迁移，Redis本身还会有一个定时任务来执行rehash。

跳表

有序链表只能逐一查找元素，导致操作非常缓慢，于是出现了跳表。具体来说，跳表是在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位。如下图所示：

可以看到，这个查找过程就是在多级索引上跳来跳去，后定位到元素。跳表的查找时间复杂度是O(logN)。

整数数组

就是一个数组，元素类型是整数，并且是有序的。

【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!更多内容请在707945861群中学习了解。