redis底层数据结构

Redis的底层数据结构是其高效读写性能和灵活数据操作能力的基础。

简单动态字符串（SDS，Simple Dynamic String）

• 定义：SDS是Redis用于存储字符串的自定义数据结构，它克服了C语言标准字符串（以空字符结尾的字符数组）的许多缺点。
• 结构：SDS通常包含三个主要字段——已用长度（len）、未使用长度（free）和实际的字节数组（buf）。这种设计使得获取字符串长度的时间复杂度为O(1)，同时也避免了缓冲区溢出，并减少了内存重分配的次数。
• 应用场景：SDS被广泛应用于Redis的各种字符串操作中，如键值对的键和值。

双向链表（Linked List）

• 定义：Redis中的双向链表是一种双端链表，具有前置节点和后置节点的引用。
• 结构：每个链表节点包含前驱节点指针、后置节点指针和节点值指针。这种设计使得链表可以在两端进行快速的添加和删除操作。
• 应用场景：双向链表是Redis列表（List）数据类型的底层实现之一，也用于其他需要链表结构的数据结构中，如发布与订阅（pub/sub）中的频道和消息列表。

压缩列表（Ziplist）

• 定义：压缩列表是Redis为了节省内存而开发的一种顺序型数据结构，它通过一系列特殊编码的连续内存块来存储数据。
• 特点：压缩列表中的每个元素都可以是字节数组或整数，且可以根据实际内容选择不同的编码方式以节省空间。此外，压缩列表还支持快速的随机访问。
• 应用场景：压缩列表是Redis列表（List）、哈希（Hash）、集合（Set）和有序集合（Sorted Set）等数据类型的底层实现之一，特别是在这些数据结构中的元素数量较少且每个元素较小时。

字典（Hashtable）

• 定义：字典是Redis用于实现哈希表（Hash）和集合（Set）等数据结构的核心数据结构。
• 结构：字典由哈希表数组和一系列链表（或跳表，在有序集合中）组成。哈希表数组的每个槽位指向一个链表的头节点，链表中的每个节点保存一个键值对。
• 特点：字典支持快速的查找、插入和删除操作，并通过渐进式rehash策略实现哈希表的动态扩容和缩容。
• 应用场景：字典是Redis哈希表（Hash）和集合（Set）等数据类型的底层实现。

跳跃表（Skiplist）

• 定义：跳跃表是一种有序的数据结构，它通过在链表的基础上增加多级索引来提高查找效率。
• 结构：跳跃表由多层链表组成，每层链表都包含了一系列节点，且每层链表的节点数量逐级减少。每个节点都包含多个指针，分别指向同一层链表中的下一个节点和下一层链表中的相应节点。
• 特点：跳跃表支持快速的查找、插入和删除操作，时间复杂度均为O(logN)。
• 应用场景：跳跃表是Redis有序集合（Sorted Set）的底层实现之一，特别是在有序集合中的元素数量较多时。

整数集合（Intset）

• 定义：整数集合是Redis用于存储整数集合的抽象数据类型。
• 结构：整数集合由一个编码方式字段、一个元素数量字段和一个元素数组组成。元素数组中的元素按照从小到大的顺序排列，并且不包含重复项。
• 特点：整数集合在存储小整数集合时比哈希表更加节省内存。
• 应用场景：整数集合是Redis集合（Set）数据类型的底层实现之一，特别是在集合中的元素全部为整数且数量较少时。

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

Redis数据类型	底层数据结构
String	SDS
Hash	Ziplist/Listpack（Redis 7.0后）/Hashtable
List	Ziplist/QuickList（Redis 3.2后）
Set	Intset/Hashtable
ZSet	Ziplist/Skiplist（Redis 7.0后）/Hashtable