redis存储类型

主要提供了5种数据结构：字符串（String）、哈希(hash)、列表(list)、集合(set)、有序集合(short set)；

redis底层实现的8种数据结构

SDS simple synamic string：支持自动动态扩容的字节数组list ：链表dict ：使用双哈希表实现的, 支持平滑扩容的字典zskiplist ：附加了后向指针的跳跃表intset ： 用于存储整数数值集合的自有结构ziplist ：一种实现上类似于TLV, 但比TLV复杂的, 用于存储任意数据的有序序列的数据结构quicklist：一种以ziplist作为结点的双链表结构, 实现的非常不错zipmap ： 一种用于在小规模场合使用的轻量级字典结构

字符串对象支持三种编码方式: INT, RAW, EMBSTR, 三种方式的内存布局分别如下

哈希对象

哈希对象的底层实现有两种, 一种是dict, 一种是ziplist. 分别对应编码HT与ZIPLIST. 而之前介绍的zipmap这种结构, 虽然也是一种轻量级的字典结构, 且纵使在源代码中有相应的编码宏值, 但遗憾的是, 至Redis 4.0.10, 目前哈希对象的底层编码仍然只有ziplist与dict两种

dict自不必说, 本身就是字典类型, 存储键值对的. 用ziplist作为底层数据结构时, 是将键值对以<key1><value1><key2><value2>...<keyn><valuen>这样的形式存储在ziplist中的. 两种编码内存布局分别如下:

列表对象

列表对象的底层实现, 历史上是有两种的, 分别是ziplist与list, 但截止Redis 4.0.10版本, 所有的列表对象API都不再支持除去quicklist之外的任何底层实现. 也就是说, 目前(Redis 4.0.10), 列表对象支持的底层实现实质上只有一种, 即是quicklist.

列表对象的创建API依然支持从ziplist的实例创建一个列表对象, 即你可以创建一个底层编码为ZIPLIST的列表对象, 但如果用该列表对象去调用任何其它列表对象的API, 都会导致panic. 在使用之前, 你只能再次调用相关的底层编码转换接口, 将这个列表对象的底层编码转换为QUICKLIST.

并且遗憾的是, LINKEDLIST这种编码, 即底层为list的列表, 被彻底淘汰了. 也就是说, 截止目前(Redis 4.0.10), Redis定义的10个对象编码方式宏名中, 有两个被完全闲置了, 分别是: OBJ_ENCODING_ZIPMAP与OBJ_ENCODING_LINKEDLIST. 从Redis的演进历史上来看, 前者是后续可能会得到支持的编码值, 后者则应该是被彻底淘汰了.

列表对象的内存布局如下图所示:

集合对象

集合对象的底层实现有两种, 分别是intset和dict. 分别对应编码宏中的INTSET和HT. 显然当使用intset作为底层实现的数据结构时, 集合中存储的只能是数值数据, 且必须是整数. 而当使用dict作为集合对象的底层实现时, 是将数据全部存储于dict的键中, 值字段闲置不用.

集合对象的内存布局如下图所示:

有序集合对象

有序集合的底层实现依然有两种, 一种是使用ziplist作为底层实现, 另外一种比较特殊, 底层使用了两种数据结构: dict与skiplist. 前者对应的编码值宏为ZIPLIST, 后者对应的编码值宏为SKIPLIST

使用ziplist来实现在序集合很容易理解, 只需要在ziplist这个数据结构的基础上做好排序与去重就可以了. 使用zskiplist来实现有序集合也很容易理解, Redis中实现的这个跳跃表似乎天然就是为了实现有序集合对象而实现的, 那么为什么还要辅助一个dict实例呢? 我们先看来有序集合对象在这两种编码方式下的内存布局, 然后再做解释:

首先是编码为ZIPLIST时, 有序集合的内存布局如下:

在使用dict与skiplist实现有序集合时, 跳跃表负责按分数索引, 字典负责按数据索引. 跳跃表按分数来索引, 查找时间复杂度为O(lgn). 字典按数据索引时, 查找时间复杂度为O(1). 设想如果没有字典, 如果想按数据查分数, 就必须进行遍历. 两套底层数据结构均只作为索引使用, 即不直接持有数据本身. 数据被封装在SDS中, 由跳跃表与字典共同持有. 而数据的分数则由跳跃表结点直接持有(double类型数据), 由字典间接持有.