Redis底层数据结构

Redis数据结构-动态字符串

我们都知道Redis中保存的Key是字符串，value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。

不过Redis没有直接使用C语言中的字符串，因为C语言字符串存在很多问题：

获取字符串长度的需要通过运算

非二进制安全

不可修改

Redis是C语言实现的，其中SDS是一个结构体，源码如下：

例如，一个包含字符串“name”的sds结构如下：

SDS之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为“hi”的SDS：

假如我们要给SDS追加一段字符串“,Amy”，这里首先会申请新内存空间：

如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1；

如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。

Redis数据结构-intset

IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。结构如下：

其中的encoding包含三种模式，表示存储的整数大小不同：

为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中，结构如图：

现在，数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16，每部分占用的字节大小为： encoding：4字节 length：4字节 contents：2字节 * 3 = 6字节

我们向该其中添加一个数字：50000，这个数字超出了int16_t的范围，intset会自动升级编码方式到合适的大小。

升级编码为INTSET_ENC_INT32, 每个整数占4字节，并按照新的编码方式及元素个数扩容数组

倒序依次将数组中的元素拷贝到扩容后的正确位置

将待添加的元素放入数组末尾

最后，将inset的encoding属性改为INTSET_ENC_INT32，将length属性改为4

小总结：

Intset可以看做是特殊的整数数组，具备一些特点：

Redis会确保Intset中的元素唯一、有序

具备类型升级机制，可以节省内存空间

底层采用二分查找方式来查询

Redis数据结构-Dict

我们知道Redis是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。 Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

当我们向Dict添加键值对时，Redis首先根据key计算出hash值（h），然后利用 h & sizemask来计算元素应该存储到数组中的哪个索引位置。我们存储k1=v1，假设k1的哈希值h =1，则1&3 =1，因此k1=v1要存储到数组角标1位置。

Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

小总结：

Dict的结构：

类似java的HashTable，底层是数组加链表来解决哈希冲突

Dict包含两个哈希表，ht[0]平常用，ht[1]用来rehash

Dict的伸缩：

当LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时，Dict扩容

当LoadFactor小于0.1时，Dict收缩

扩容大小为第一个大于等于used + 1的2^n

收缩大小为第一个大于等于used 的2^n

Dict采用渐进式rehash，每次访问Dict时执行一次rehash

rehash时ht[0]只减不增，新增操作只在ht[1]执行，其它操作在两个哈希表

Redis数据结构-ZipList

ZipList 是一种特殊的“双端链表” ，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。

ZipList特性：

压缩列表的可以看做一种连续内存空间的"双向链表"

列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低

如果列表数据过多，导致链表过长，可能影响查询性能

增或删较大数据时有可能发生连续更新问题

Redis数据结构-QuickList

问题1：ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。怎么办？

答：为了缓解这个问题，我们必须限制ZipList的长度和entry大小。

问题2：但是我们要存储大量数据，超出了ZipList最佳的上限该怎么办？

答：我们可以创建多个ZipList来分片存储数据。

问题3：数据拆分后比较分散，不方便管理和查找，这多个ZipList如何建立联系？

答：Redis在3.2版本引入了新的数据结构QuickList，它是一个双端链表，只不过链表中的每个节点都是一个ZipList。

为了避免QuickList中的每个ZipList中entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制。如果值为正，则代表ZipList的允许的entry个数的最大值如果值为负，则代表ZipList的最大内存大小，分5种情况：

-1：每个ZipList的内存占用不能超过4kb

-2：每个ZipList的内存占用不能超过8kb

-3：每个ZipList的内存占用不能超过16kb

-4：每个ZipList的内存占用不能超过32kb

-5：每个ZipList的内存占用不能超过64kb

其默认值为 -2：

以下是QuickList的和QuickListNode的结构源码：

我们接下来用一段流程图来描述当前的这个结构

总结：

QuickList的特点：

是一个节点为ZipList的双端链表

节点采用ZipList，解决了传统链表的内存占用问题

控制了ZipList大小，解决连续内存空间申请效率问题

中间节点可以压缩，进一步节省了内存

Redis数据结构-SkipList

SkipList（跳表）首先是链表，但与传统链表相比有几点差异：元素按照升序排列存储节点可能包含多个指针，指针跨度不同。

小总结：

SkipList的特点：

跳跃表是一个双向链表，每个节点都包含score和ele值

节点按照score值排序，score值一样则按照ele字典排序

每个节点都可以包含多层指针，层数是1到32之间的随机数

不同层指针到下一个节点的跨度不同，层级越高，跨度越大

增删改查效率与红黑树基本一致，实现却更简单