Redis系列(九)底层数据结构之五种基础数据类型的实现

前言

Redis 已经是大家耳熟能详的东西了，日常工作也都在使用，面试中也是高频的会涉及到，那么我们对它究竟了解有多深刻呢？

我读了几本 Redis 相关的书籍，尝试去了解它的具体实现，将一些底层的数据结构及实现原理记录下来。

本文将介绍 Redis 中 五种基础数据类型 的实现方法。 这五种基本类型基本覆盖了我们业务中使用的 80%的场景，对面试也覆盖至少 90%.（其中重点当然是有序集合以及散列结构咯）.

定义

在前面的八篇文章中，我们详细的介绍了 Redis 中的 8 种基本数据结构，但是众所周知，Redis 常用的数据类型有五种。包括，字符串，列表，集合，有序集合，哈希。

而这五种数据类型，底层就是用前面介绍的数据结构实现的，当然，并不是直接一对一的绑定关系，而是采用了精妙的设计，构建了一个对象系统。

熟悉 OOP 编程的读者，可能很快就能想到为什么要这么设计了，对象系统带来的好处是非常多的，但是并不在这一篇文章中讲。这里只是提到对象系统，让大家对于五种数据类型为什么可以用一些花里胡哨的方法来实现，有一个初步的了解。

接下来将逐一分析五种数据类型的底层实现数据结构，及实现方式（编码）之间的切换条件。

注：后续提到五种数据类型，用 xx 对象来指代。比如 字符串对象，列表对象。提到的底层数据结构，用全称来讲。

字符串对象

涉及到的数据结构， SDS , 强烈建议阅读本系列第一篇文章。

字符串对象的底层实现有三种可能：int, raw, embstr.

int

如果一个字符串对象，保存的值是一个整数值，并且这个整数值在 long 的范围内，那么 redis 用整数值来保存这个信息，并且将字符串编码设置为 int .

比如：

raw

如果字符串对象保存的是一个 字符串 , 并且长度大于 32 个字节，它就会使用前面讲过的 SDS（简单动态字符串） 数据结构来保存这个字符串值，并且将字符串对象的编码设置为 raw .

embstr

如果字符串对象保存的是一个 字符串 , 但是长度小于 32 个字节，它就会使用 embstr 来保存了， embstr 编码不是一个数据结构，而是对 SDS 的一个小优化，当使用 SDS 的时候，程序需要调用两次内存分配，来给 字符串对象 和 SDS 各自分配一块空间，而 embstr 只需要一次内存分配，因为他需要的空间很少，所以采用 连续的空间保存，即将 SDS 的值和 字符串对象的值放在一块连续的内存空间上。这样能在短字符串的时候提高一些效率。

比如：

浮点数如何保存？

redis 的字符串数据类型是支持保存浮点数，并且支持对浮点数进行加减操作，但是 redis 在底层是把浮点数转换成字符串值，之后走上面三种编码的规则的。对浮点数进行操作时，也是从字符串转换成浮点数进行计算，然后再转换成字符串进行保存的。

编码转换条件

这块的知识其实是很符合我们的认知的，比如 int 编码只可以保存整数，那么当我们对一个 int 编码的字符串对象，修改它的值，它自然就会使用 raw 编码了。

但是有一个特性，Redis 没有为 embstr 编码提供任何的修改操作，这也就是为什么它只是个编码而不是一个数据结构的原因。

所以在 Redis 中， embstr 编码的值其实是 只读 的，只要发生修改，立刻将编码转换成 raw .

总结

字符串对象底层的数据结构或者说编码有三种，分别是 int , raw , embstr . 他们之间的使用条件如下：

编码 使用条件 int 可以用 long 保存的整数 embstr 字符串长度小于 32 字节（或者浮点数转换后满足） raw 长度大于 32 的字符串

列表对象

涉及到的数据结构， 压缩列表 , 双向链表 , 快速列表 , 强烈建议阅读本系列的第 二，三，四 篇文章。

在 Redis 3.2 版本之前，列表对象底层由 压缩列表和双向链表配合实现，当元素数量较少的时候，使用压缩列表，当元素数量增多，就开始使用普通的双向链表保存数据。

但是这种实现方式不够好，双向链表中的每个节点，都需要保存前后指针，这个内存的使用量 对于 Redis 这个内存数据库来说极其不友好。

因此在 3.2 之后的版本，作者新实现了一个数据结构，叫做 quicklist . 所有列表的底层实现都是这个数据结构了。它的底层实现基本上就是将 双向链表和压缩列表进行了结合，用双向的指针将压缩列表进行连接，这样不仅避免了压缩列表存储大量元素的性能压力，同时避免了双向链表连接指针占用空间过多的问题。

具体的原理讲解请 阅读对应的文章，这里不再赘述。

总结

编码 使用条件 quicklist 所有数据

集合对象

涉及到的数据结构： intset , dict(hashtable) , 强烈建议阅读本系列第五，第六篇文章。

集合对象的编码可以是 intset 或者 hashtable（字典） .

intset

当集合中的所有元素都是整数，且元素的数量不大于 512 个的时候，使用 intset 编码。

intset 编码时，底层使用 intset 数据结构。

hashtable

当元素不符合 全部为整数值且元素个数小于 512 时，集合对象使用的编码方式为 hashtable .

字典的每一个键都是一个字符串对象，其中保存了集合里的一个元素，字典的值全部被设置为 NULL.

总结

编码 使用条件 intset 所有元素都是整数且元素个数小于 512 hashtable 其他数据

有序集合对象

涉及到的数据结构， 压缩列表 , 跳跃表 , 字典 , 强烈建议阅读本系列 第三篇，第六篇，第七篇文章。

有序集合对象的编码可以是 ziplist 以及 skiplist .

ziplist 编码

当使用 ziplist 编码时，有序集合对象的实现数据结构为 ziplist （听起来像句废话）, 每个集合的元素 (key-value), 使用两个紧挨着的压缩列表的节点来表示，第一个节点保存集合元素的成员 (member), 第二个节点保存集合元素的分支 (score).

在压缩列表的内部，集合元素按照分值从小到大进行排序。

skiplist 编码

当使用 skiplist 编码的时候，内部使用 zset 来实现数据的保存， zset 的定义如下：

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

为什么需要同时使用跳跃表以及字典呢？

其实如果我们细想，单独使用字典或者跳跃表，都是可以实现有序集合的所有功能的，但是性能太差劲了。

• 当我们只使用字典来实现，我们可以以 O(1) 的时间复杂度获取成员的分值，但是由于字典是无序的，当我们需要进行范围性操作的时候，需要对字典中的所有元素进行排序，这个时间复杂度至少需要 O(nlogn).
• 当我们只使用跳跃表来实现，我们可以在 O(logn) 的时间进行范围排序操作，但是如果要获取到某个元素的分值，时间复杂度也是 O(logn).

因此，将字典和跳跃表结合进行使用，可以在 O(1) 的时间复杂度下完成查询分值操作，而对一些范围操作，使用跳跃表可以达到 O(logn) 的是缠绵复杂度。

可以看到，我在上一次的例子中，添加了一个很长的 key 之后，有序集合的编码方式就成为了 skiplist .

总结

编码 使用条件 ziplist 元素数量少于 128 且 所有元素成员的长度小于 64 字节 skiplist 不满足上述条件的其他情况

散列对象

涉及到的数据结构， 压缩列表 , 字典 , 强烈建议阅读本系列 第三篇，第六篇文章。

哈希对象的编码可以是 ziplist 或者 hashtable .

ziplist 编码

ziplist 编码下的哈希对象，使用了压缩列表作为底层实现数据结构，用两个连续的压缩列表节点来表示哈希对象中的一个键值对。实现方式类似于上面的有序集合的场景。

如图中所示，当我放入了两个简单的键值对，此时哈希对象的编码为 ziplist.

hashtable 编码

这是对 hashtable 最直观的应用了~

哈希结构本身在结构上和字典 (hashtable) 就颇为相似，因此哈希对象中的每一个键值对都是字典中的一个键值对。

• 字典的每一个键都是一个字符串对象，对象中保存了键值对的键。
• 字典的每一个值都是一个字符串对象，对象中保存了键值对的值。

如图中所示，当我在上一个示例中额外加入一个很长的值，那么编码方式就来到了 hashtable .

总结

编码 使用条件 ziplist 键值对的键和值的长度都小于 64 字节，且 键值对个数小于 512. hastable 不满足上述条件的其他条件

全文总结

其实在前面的几篇文章写完之后，也就是在所有的底层数据结构介绍完之后，所谓的 Redis 的五种基础数据类型的底层实现原理 就已经没有了难度。

所有用到的底层数据结构都知道了，剩下的无非是个排列组合问题以及各种实现方式之间的切换条件，然后这个条件也仅仅是了解性知识，强行记住也没有必要。

这里把五种基础数据类型的可能的编码列出来方便理解及记忆。

基础数据类型 可能的编码方式 字符串 int, raw, embstr 列表 之前是 ziplist 和 linkedlist, 现在全是 quicklist 了。 集合 intset 或者 hashtable 有序集合 ziplist 或者 skiplist , skiplist 编码中使用了跳跃表+字典 散列 ziplist 或者 hashtable

至于他们的转换条件，由于我不会用 markdown 画多维表格，但是又不想写 html, 就不做总结了，需要的读者可以点击目录跳转至每一个小结的总结~.

参考文章

《Redis 的设计与实现（第二版）》

《Redis 深度历险：核心原理和应用实践》

完。

联系我

最后，欢迎关注我的个人公众号【 呼延十 】，会不定期更新很多后端工程师的学习笔记。

也欢迎直接公众号私信或者邮箱联系我，一定知无不言，言无不尽。

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：[email protected]

更多学习笔记见个人博客或关注微信公众号 < 呼延十 >------> 呼延十