今天要分享的就是Redis底层数据结构的知识概要。
首先我们知道Redis是一个K-V键值对型的数据库。那么Redis是如何通过KV键值对来访问数据的呢？

键值对数据结构的基石——Dict

Redis的 键与值的映射关系正是通过Dict来实现的。

Dict是什么

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

再来看看Dict 和其他底层数据结构的关系

Dict的扩容

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。
Dict在每次新增键值对时都会检查负载因子（LoadFactor = used/size） ，满足以下两种情况时会触发哈希表扩容：

• 哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程；
• 哈希表的LoadFactor > 5 ；
  
  

Dict的rehash

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。过程是这样的：

• 计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：

  • 如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n
  • 如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）

• 按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]

• 设置dict.rehashidx = 0，标示开始rehash

• 将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]

• 将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存

• 将rehashidx赋值为-1，代表rehash结束

• 在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空
  （省流理解：给dict[1] 分配一个能够满足要求的空间，将dict[0]所有的数据重新计算再传入后，再将值赋给dict[0]。）
  整个过程可以描述成：

小总结：

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]执行，其它操作在两个哈希表

SDS

Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称SDS。
下图就是 Redis 5.0 的 SDS 的数据结构：

结构中的每个成员变量分别介绍下：

len，记录了字符串长度。这样获取字符串长度的时候，只需要返回这个成员变量值就行，时间复杂度只需要 O（1）。
alloc，分配给字符数组的空间长度。这样在修改字符串的时候，可以通过 alloc - len 计算出剩余的空间大小，然后自行选择是否扩容。
flags，用来表示不同类型的 SDS。一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，这里的数字表示的是长度与分配内存的上限。
buf[]，字符数组，用来保存实际数据。不仅可以保存字符串，也可以保存二进制数据。
总的来说，Redis 的 SDS 结构在原本字符数组之上，增加了三个元数据：len、alloc、flags，用来解决 C 语言字符串的缺陷。

为什么不用String？

使用String的缺点：

• 获取字符串长度的时间复杂度为 O（N）；
• 字符串的结尾是以 “\0” 字符标识，字符串里面不能包含有 “\0”字符，因此不能保存二进制数据；
• 字符串操作函数不高效且不安全，比如有缓冲区溢出的风险，有可能会造成程序运行终止；

SDS的优势

SDS的优势就体现在它的结构上。
len：可以以O（1）的时间复杂度获取字符串长度，不需要扫描整个字符串。而且允许了字符串中的'\0'的存在，而且SDS的API是以处理二进制数据的方式处理buf[]中的数据。所以SDS可以保存任意格式的二进制的数据。

alloc：支持扩容，当判断出缓冲区大小不够用时，Redis 会自动将扩大 SDS 的空间大小，所以不会有缓存区溢出的情况。

flags：能灵活保存不同大小的字符串，从而有效节省内存空间。

链表

Redis 的 List 对象的底层实现之一就是链表。C 语言本身没有链表这个数据结构的，所以 Redis 自己设计了一个链表数据结构。

#链表节点结构设计
先来看看「链表节点」结构的样子：

typedef struct listNode {//前置节点struct listNode *prev;//后置节点struct listNode *next;//节点的值void *value;
} listNode;

有前置节点和后置节点，可以看的出，这个是一个双向链表。

链表结构设计

不过，Redis 在 listNode 结构体基础上又封装了 list 这个数据结构，这样操作起来会更方便，链表结构如下：

typedef struct list {//链表头节点listNode *head;//链表尾节点listNode *tail;//节点值复制函数void *(*dup)(void *ptr);//节点值释放函数void (*free)(void *ptr);//节点值比较函数int (*match)(void *ptr, void *key);//链表节点数量unsigned long len;
} list;

链表的优势与劣势

优点

获取某个节点的前置节点或后置节点的时间复杂度只需O(1)，而且这两个指针都可以指向 NULL，所以链表是无环链表；

• 获取链表的表头节点和表尾节点的时间复杂度只需O(1)；
• 获取链表中的节点数量的时间复杂度只需O(1)；
• listNode 链表节使用void* 指针保存节点值，并且可以通过 list 结构的 dup、free、match
  函数指针为节点设置该节点类型特定的函数，因此链表节点可以保存各种不同类型的值；

缺点

节点之间的内存都是不连续的，意味着无法很好利用 CPU 缓存。能很好利用 CPU 缓存的数据结构就是数组，因为数组的内存是连续的，这样就可以充分利用 CPU 缓存来加速访问。（局部性原理）

保存一个链表节点的值都需要一个链表节点结构头的分配，内存开销较大。

压缩列表（ZipListEntry）

压缩列表的结构

压缩列表的最大特点，就是它被设计成一种内存紧凑型的数据结构，占用一块连续的内存空间，不仅可以利用 CPU 缓存，而且会针对不同长度的数据，进行相应编码，这种方法可以有效地节省内存开销。
压缩列表的结构决定了它可以很快获得头节点和尾结点，而其他的只能通过遍历获取，所以只适合数据量不多时候的存储。
ZipListEntry

ZipList 中的Entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存。而是采用了下面的结构：

• previous_entry_length：前一节点的长度，占1个或5个字节。

  • 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
  • 如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据

• encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节

ZipListEntry中的encoding编码分为字符串和整数两种：

• 字符串：如果encoding是以“00”、“01”或者“10”开头，则证明content是字符串
• 整数：如果encoding是以“11”开始，则证明content是整数，且encoding固定只占用1个字节

• contents：负责保存节点的数据，可以是字符串或整数

这种根据数据大小和类型进行不同的空间大小分配的设计思想，正是 Redis 为了节省内存而采用的。

连锁更新

前面提到了压缩链表会用一个previous_entry_length 存储前一个节点的大小，若此时连续插入多个长度在 250～253 之间的节点后，在连续结点的第一个结点前插入了一个长度大于等于254的节点，此时后面的连续结点因为修改previous_entry_length 的长度也大于等于254需要重新分配内存空间，这种多米罗骨牌似的情况就耗费时间。

小总结

压缩列表适合存储数据量不大的情况

哈希表

哈希表是一种保存键值对（key-value）的数据结构。（数组 + 链表）
通过哈希计算索引能够在数组中快速找到Key
通过链表解决哈希冲突

整数集合（intset）

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

对于超出范围的数，intset会自动升级编码
插入流程：

小总结：

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

• Redis会确保Intset中的元素唯一、有序
• 具备类型升级机制，可以节省内存空间
• 底层采用二分查找方式来查询

跳表

Redis 只有 Zset 对象的底层实现用到了跳表，跳表的优势是能支持平均 O(logN) 复杂度的节点查找。

zset 结构体里有两个数据结构：一个是跳表，一个是哈希表。这样的好处是既能进行高效的范围查询，也能进行高效单点查询。

typedef struct zset {dict *dict;zskiplist *zsl;
} zset;

zset在插入数据时，会同时更新哈希表和跳表中的值让他们保持一致。
为什么常说zset的底层结构是跳表，因为其中的绝大部分操作都是由跳表完成的。

跳表的结构

跳表是一个多层级的有序链表，在查询数据量多时，时间复杂度为O(logn)。

typedef struct zskiplist {struct zskiplistNode *header, *tail;unsigned long length;// 层数int level;
} zskiplist;

typedef struct zskiplistNode {//Zset 对象的元素值sds ele;//元素权重值double score;//后向指针struct zskiplistNode *backward;//节点的level数组，保存每层上的前向指针和跨度struct zskiplistLevel {struct zskiplistNode *forward;// 用于正确计算结点的位置。unsigned long span;} level[];
} zskiplistNode;

跳表怎样进行查询

要想明白跳表是什么东西，最好就是看跳表是如何应用的。
查找一个跳表节点的过程时，跳表会从头节点的最高层开始，逐一遍历每一层。
举个例子，下图有个 3 层级的跳表。在遍历某一层的跳表节点时，会用跳表节点中的 SDS 类型的元素和元素的权重来进行判断，共有两个判断条件：

• 如果当前节点的权重「小于」要查找的权重时，跳表就会访问该层上的下一个节点。 如果当前节点的权重「等于」要查找的权重时，并且当前节点的
• SDS 类型数据「小于」要查找的数据时，跳表就会访问该层上的下一个节点。

如果上面两个条件都不满足，或者下一个节点为空时，跳表就会使用目前遍历到的节点的 level 数组里的下一层指针，然后沿着下一层指针继续查找，这就相当于跳到了下一层接着查找。

如果要查找「元素：abcd，权重：4」的节点，查找的过程是这样的：

1. 先从头节点的最高层开始，L2 指向了「元素：abc，权重：3」节点，这个节点的权重比要查找节点的小，所以要访问该层上的下一个节点；
2. 但是该层的下一个节点是空节点（ leve[2]指向的是空节点），于是就会跳到「元素：abc，权重：3」节点的下一层去找，也就是leve[1];
3. 「元素：abc，权重：3」节点的 leve[1]的下一个指针指向了「元素：abcde，权重：4」的节点，然后将其和要查找的节点比较。虽然「元素：abcde，权重：4」的节点的权重和要查找的权重相同，但是当前节点的SDS 类型数据「大于」要查找的数据，所以会继续跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[0]；
4. 「元素：abc，权重：3」节点的 leve[0] 的下一个指针指向了「元素：abcd，权重：4」的节点，该节点正是要查找的节点，查询结束。

跳表的层数

跳表的设计不合理，会变成近似链表的结构。那么跳表该设置多少层？怎么样合理的将数据合理的分配到每一层？

跳表的相邻两层的节点数量最理想的比例是 2:1，查找复杂度可以降低到 O(logN)。
如果采用新增节点或者删除节点时，来调整跳表节点以维持比例的方法的话，会带来额外的开销。

Redis 则采用一种巧妙的方法是，跳表在创建节点的时候，随机生成每个节点的层数，并没有严格维持相邻两层的节点数量比例为 2 : 1 的情况。

具体的做法是，跳表在创建节点时候，会生成范围为[0-1]的一个随机数，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。

为什么用跳表不用平衡树（AVL|红黑）

redis的作者原话
There are a few reasons:
1、They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
它们不是非常内存密集型的。基本上由你决定。改变关于节点具有给定级别数的概率的参数将使其比 btree 占用更少的内存。
2、A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
Zset 经常需要执行 ZRANGE 或 ZREVRANGE 的命令，即作为链表遍历跳表。通过此操作，跳表的缓存局部性至少与其他类型的平衡树一样好。
3、They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
它们更易于实现、调试等。例如，由于跳表的简单性，我收到了一个补丁（已经在Redis master中），其中扩展了跳表，在 O(log(N) 中实现了 ZRANK。它只需要对代码进行少量修改。

• 从内存占用上来比较，跳表比平衡树更灵活一些。平衡树每个节点包含 2 个指针（分别指向左右子树），而跳表每个节点包含的指针数目平均为1/(1-p)，具体取决于参数 p 的大小。如果像 Redis里的实现一样，取 p=1/4，那么平均每个节点包含 1.33个指针，比平衡树更有优势。
• 在做范围查找的时候，跳表比平衡树操作要简单。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第1 层链表进行若干步的遍历就可以实现。
• 从算法实现难度上来比较，跳表比平衡树要简单得多。平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速。

quicklist

在 Redis 3.0 之前，List 对象的底层数据结构是双向链表或者压缩列表。在 Redis 3.2 的时候，List 对象的底层改由 quicklist 数据结构实现。
其实 quicklist 就是「双向链表 + 压缩列表」组合，因为一个 quicklist 就是一个链表，而链表中的每个元素又是一个压缩列表。

让我们回顾一下之前的数据结构有什么问题。

压缩列表：不适合太大的数据量，需要避免连锁更新问题。
连锁更新发生的场景：连续插入多个大小为250~253的数据，当连续数据前插入一个大于等于254的数据时，会导致后面的连续数据全部需要重新分配内存。
quicklist 解决办法，通过控制每个链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题。因为压缩列表元素越少或越小，连锁更新带来的影响就越小，从而提供了更好的访问性能。

listpack

虽然quicklist对原来的压缩列表进行了优化，但只要底层还是使用了压缩列表就会不可避免的有连锁更新的问题。

所以listpack 抛弃压缩列表中记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当我们向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。

总结

String——SDS
List——listpack+链表
Hash表——Dict（键值对查询的基础）
Set——整数列表（intset）
Zset——跳表（skiplist）

Redis针对底层的数据结构做了很多的优化，但是不管怎么优化，所有的数据结构底层都是由链表或数组优化来的。对Redis底层数据结构的理解一定要结合具体的实践场景和问题去思考。

参考文献

Redis数据结构
黑马程序员课程资料。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！