Redis 中的数据结构

白杨的梦呓 2022-03-08

227

Redis 有个典型的特点就是访问速度很快。当它接收到一个键值对操作后，能以微秒级别的速度找到数据，并快速完成操作。

这是因为它是内存数据库，所有操作都在内存上完成，内存的访问速度本身就很快。

另一方面，还要归功于它的数据结构。因为键值对是按一定的数据结构来组织的，操作键值对最终就是对数据结构进行增删改查操作，所以高效的数据结构是 Redis 快速处理数据的基础。

Redis有五种数据类型：

字符串 String、列表 List、哈希 Hash、集合 Set 和有序集合 Sorted Set。这几种数据类型也是数据的保存形式。那么它们底层是怎么实现的呢？

简单说，底层的数据结构可以分为 6 种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。

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

键和值用什么结构存储？

为了实现键到值的快速访问，Redis 使用的是哈希表来保存键值对。

一个哈希表，就是一个数组，数组中的每个元素称为一个哈希桶。可以说一个哈希表由多个哈希桶组成，每个哈希桶保存了键值对的数据。

有时 Redis 写入大量数据时，保存速度也可能会变慢，这是因为哈希表可能发生冲突问题，rehash 可能会带来操作阻塞。

这里说到的哈希冲突，是指两个 key 的哈希值和哈希桶计算对应关系时，正好落在了同一个哈希桶中。

在 Redis 解决哈希冲突的方法之一是，链式哈希，就是指同一个哈希桶中的多个元素用一个链表来保存，它们之间用指针连接。

为什么 Redis 的访问速度也可能会很慢？如果哈希表里写入的数据越来越多，哈希冲突可能也会越来越多，这就会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时长，效率降低。

文章转载自白杨的梦呓，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。