Redis数据结构

引用：小林coding、JavaGuide

1. Redis是如何实现键值对数据库的？

Redis是使用了一个哈希表保存所有键值对，哈希表其实就是一个数组，数组中的元素叫哈希桶。哈希桶存放的是指向键值对的指针（dictEntry*），键值对则保存了key和value的指针。

特别说明下，void * key 和 void * value指针指向的是Redis对象，Redis中的每个对象都由redisObject结构表示：

2. Redis的基本数据类型

Redis 共有 5 种基本数据类型：String（字符串）、List（列表）、Set（集合）、Hash（散列）、Zset（有序集合）。

这 5 种数据类型底层实现主要依赖这 8 种数据结构：简单动态字符串（SDS）、LinkedList（双向链表）、Dict（哈希表/字典）、SkipList（跳跃表）、Intset（整数集合）、ZipList（压缩列表）、QuickList（快速列表）。Redis 5 种基本数据类型对应的底层数据结构实现如下表所示：

String	List	Hash	Set	Zset
SDS	LinkedList/ZipList/QuickList	Dict、ZipList	Dict、Intset	ZipList、SkipList

Redis 3.2 之前，List 底层实现是 LinkedList 或者 ZipList。 Redis 3.2 之后，引入了 LinkedList 和 ZipList 的结合 QuickList，List 的底层实现变为 QuickList。从 Redis 7.0 开始， ZipList 被 ListPack 取代。

3. 简单动态字符串SDS

String数据类型是由SDS实现的，SDS包括字节数组buf[]，还包括了字符串长度len，以及给这个SDS分配的空间长度alloc，这样就能以O(1)的时间复杂度获取字符串的长度，同时还能方便计算剩余可用空间。

4. 压缩列表ZipList

ZipList是Redis为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构：

• zlbytes：记录整个ZipList占用的内存字节数
• zltail：记录ZipList尾部节点距离起始地址有多少字节，也就是列表尾部的偏移量
• zllen：记录ZipList包含的节点数
• zlend：标记ZipList的结束点，固定值0xFF

5. 跳表SkipList

Redis的有序集合zset是用ZipList或SkipList实现的，因为设计者考虑到 Redis 数据存放于内存，为了节约宝贵的内存空间，在有序集合元素小于 64 字节且个数小于 128 的时候，会使用 ziplist；一旦有序集合中的某个元素超出这两个其中的一个阈值它就会转为 skiplist。

也就是说，ZSet 有两种不同的实现，分别是 ziplist 和 skiplist，具体使用哪种结构进行存储的规则如下：

• 当有序集合对象同时满足以下两个条件时，使用 ziplist：
  1. ZSet 保存的键值对数量少于 128 个；
  2. 每个元素的长度小于 64 字节。
• 如果不满足上述两个条件，那么使用 skiplist 。

5.1 跳表是什么

我们都知道有序链表在添加、查询、删除的平均时间复杂都都是 O(n) 即线性增长，所以一旦节点数量达到一定体量后其性能表现就会非常差劲。而跳表我们完全可以理解为在原始链表基础上，建立多级索引，通过多级索引检索定位将增删改查的时间复杂度变为 O(log n) 。

假如我们需要查询元素 6，其工作流程如下：

1. 从 2 级索引开始，先来到节点 4。
2. 查看 4 的后继节点，是 8 的 2 级索引，这个值大于 6，说明 2 级索引后续的索引都是大于 6 的，没有再往后搜寻的必要，我们索引向下查找。
3. 来到 4 的 1 级索引，比对其后继节点为 6，查找结束。

相较于原始有序链表需要 6 次，我们的跳表通过建立多级索引（每级索引的数量一般是下一层的数量的一半），我们只需两次就直接定位到了目标元素，其查询的复杂度被直接优化为O(log n)。