redis有String、List、Hash、Set、Sorted Set这五大基本数据类型，不同的数据类型适用不同的场景。

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

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

Redis全局哈希表（Global Hash Table）是指在Redis数据库内部用于存储所有键值对的主要数据结构。

  • String: 简单动态字符串
  • List: 双向链表，压缩列表
  • Hash: 哈希表，压缩列表
  • Sorted Set: 跳表，压缩列表
  • Set: 整数数组，哈希表

简单动态字符串

Redis中存储字符串时，Redis使用了一种称为简单动态字符串（Simple Dynamic String，SDS）的数据结构来表示字符串。

它有int、embstr和raw这三种编码模式:

  1. int编码：当保存的是 Long 类型整数时，RedisObject 中的指针就直接赋值为整数数据了，这样就不用额外的指针再指向整数了，节省了指针的空间开销。
  2. embstr编码：当保存的是字符串数据，并且字符串小于等于 44 字节时，RedisObject 中的元数据、指针和 SDS 是一块连续的内存区域，这样就可以避免内存碎片。
  3. raw编码：当字符串大于 44 字节时，SDS 的数据量就开始变多了，Redis 就不再把 SDS 和 RedisObject 布局在一起了，而是会给 SDS 分配独立的空间，并用指针指向 SDS 结构。

优势和特点:

  1. 动态调整大小：SDS可以根据字符串的长度动态调整内存大小。这意味着当我们向SDS中添加更多的字符时，SDS会自动分配更多的内存空间来容纳新的字符，而不需要手动管理内存分配和释放。这样可以避免频繁的内存重新分配操作，提高了性能。
  2. O(1)时间复杂度的长度获取：SDS在内部维护了字符串的长度信息。因此，无论字符串的长度是多少，我们都可以在常数时间内获取字符串的长度，而不需要遍历整个字符串。这使得获取字符串长度的操作非常高效。
  3. 二进制安全：SDS可以存储任意二进制数据，而不仅仅局限于文本字符串。这意味着我们可以在SDS中存储包含空字符（'\0’）在内的任意二进制数据，而不会导致字符串的截断或错误解析。
  4. 缓冲区溢出保护：SDS在内部维护了字符串的长度信息，这使得Redis能够有效地防止缓冲区溢出的问题。当我们向SDS中添加新的字符时，Redis会检查是否有足够的空间来容纳新的字符，如果没有足够的空间，Redis会自动分配更多的内存空间，以避免溢出。
  5. 兼容C字符串：SDS可以通过转换函数与C字符串进行互相转换。这意味着我们可以在Redis中使用SDS来存储字符串，然后将其转换为C字符串，以便与现有的C代码进行交互。反之，我们也可以将C字符串转换为SDS，以便在Redis中使用更多的字符串操作功能。

双向链表（Doubly Linked List）

在 Redis 中，链表节点的结构拥有指向前置节点和后置节点的属性。

链表结构则包含链表表头节点、表尾节点、节点长度等属性，便于快速获取链表相关信息。

双向链表的优势在于它可以高效地进行插入、删除和遍历操作。通过指针，可以快速地在链表中移动，并且在任意位置插入或删除节点的开销较小。

压缩列表（Ziplist）

当列表、哈希、有序集合存储的数据量较少时，redis就会考虑用ziplist来存储。

压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，ziplist每个元素长度可以不同，并且在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。

在压缩列表中，如果我们要查找第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，只能逐个查找，此时的复杂度就是 O(N) 。

跳跃表（Skip List）

跳表（skiplist）是在有序链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位。建立索引可以每隔2个数据建立索引，也可以隔3个或5个。

整数数组和压缩列表在查找时间复杂度方面并没有很大的优势，那为什么Redis还会把它们作为底层数据结构呢？主要出于以下两点考虑：

  • 内存利用率，数组和压缩列表都是非常紧凑的数据结构，它比链表占用的内存要更少。Redis是内存数据库，大量数据存到内存中，此时需要做尽可能的优化，提高内存的利用率。
  • 数组对CPU高速缓存支持更友好，所以Redis在设计时，集合数据元素较少情况下，默认采用内存紧凑排列的方式存储，同时利用CPU高速缓存不会降低访问速度。当数据元素超过设定阈值后，避免查询时间复杂度太高，转为哈希和跳表数据结构存储，保证查询效率。

参考