redis数据结构都有哪些（带你领略Redis数据结构之美）

redis数据结构都有哪些（带你领略Redis数据结构之美）好了，介绍完以上这些您对redis的对象与数据结构的关系有了一个大致的了解。前戏足了，下面咋们可以进入正题了，嘿嘿。六种姿势将在下面注意解锁，注意感受哦。编码选择的策略如下：（2）encoding 属性和 *prt 指针对象的 prt 指针指向对象底层的数据结构，而数据结构由 encoding 属性来决定。而每种类型的对象都至少使用了两种不同的编码：

谈到Redis有哪些数据结构，很多同学都会脱口而出string、hash、list、set、zset。但是小编认为，这些严格来说只是数据类型，或者说只是redis对你开放的可以让数据按照相应的数据结构存储的接口而已。那么什么才是真正意义上的redis数据结构？他们的作用是什么？redis为什么要采用这些数据结构呢？在揭晓这些问题之前我们先为您简单讲解下redis的数据对象。

每次在Redis数据库中创建一个键值对时，至少会创建两个对象，一个是键对象，一个是值对象，而Redis中的每个对象都是由 redisObject 结构来表示。有以下四个属性：类型 type; 编码 encoding; 指向底层数据结构的指针 *ptr; 引用计数 refcount;记录最后一次被程序访问的时间 lru;下面对这些属性做一个简单的介绍：

（1）对象的type属性记录了对象的类型，这个类型就是前面讲的五大数据类型：

在Redis中，键总是一个字符串对象，而值可以是字符串、列表、集合等对象，所以我们通常说的键为字符串键，表示的是这个键对应的值为字符串对象，我们说一个键为集合键时，表示的是这个键对应的值为集合对象。

（2）encoding 属性和 *prt 指针

对象的 prt 指针指向对象底层的数据结构，而数据结构由 encoding 属性来决定。

而每种类型的对象都至少使用了两种不同的编码：

编码选择的策略如下：

• 列表类型 ：当列表对象所存储的字符串元素长度小于64字节并且元素数量小于512个时，使用ziplist编码，否则使用linkedlist编码
• 集合类型：当集合对象所保存的元素都是整数值且元素数量不超过512个时，使用intset编码，否则使用hashtable编码
• 有序集合类型：当元素数量小于128个并且所有元素成员的长度都小于64字节之时使用ziplist编码，否则使用skiplist编码
• 哈希类型：哈希对象的编码可以是压缩列表（ziplist）或者字典（hashtable），当哈希对象保存的所有键值对的键和值得长度都小于64字节并且元素数量小于512个时使用ziplist，否则使用hashtable。使用ziplist时，是依次将键和值压入链表之中，两者相邻。使用hashtable是是将键值对存于dictEntry之中
• 字符串：字符串对象的编码可以是int、raw或者embstr。其中int表示整型的值，embstr表示小于等于39字节的字符串值，剩余的均用raw表示，并且int和embstr都是只读的，一旦发生了append操作，即会转换为raw

好了，介绍完以上这些您对redis的对象与数据结构的关系有了一个大致的了解。前戏足了，下面咋们可以进入正题了，嘿嘿。六种姿势将在下面注意解锁，注意感受哦。

一、简单动态字符串

Redis自己构建了一种名为 简单动态字符串（simple dynamic string SDS）的抽象类型，并将 SDS 作为 Redis的默认字符串表示。而并没有用 C 语言中的字符串。那么redis为什么要坐这样的调整呢？我们先看看redis里的SDS是如何实现的。

由上图我们可以了解到：len保存了SDS保存字符串的长度；buf[] 数组用来保存字符串的每个元素；free j记录了 buf 数组中未使用的字节数量。这种方式带来的好处由以下几点：

（1）可以更快捷的获取字符串的长度。由于 len 属性的存在，我们获取 SDS 字符串的长度只需要读取 len 属性，时间复杂度为 O(1)。而对于 C 语言，获取字符串的长度通常是经过遍历计数来实现的，时间复杂度为 O(n)。通过 strlen key 命令可以获取 key 的字符串长度。

（2）可以有效杜绝缓冲区溢出。 redis这种强依赖内存操作的中间件，非常容易发生内存溢出而且一旦发生就极有可能造成数据丢失。 C 语言中使用 strcat 函数来进行两个字符串的拼接，一旦没有分配足够长度的内存空间，就会造成缓冲区溢出。而对于 SDS 数据类型，在进行字符修改的时候，会首先根据记录的 len 属性检查内存空间是否满足需求，如果不满足，会进行相应的空间扩展，然后在进行修改操作，所以不会出现缓冲区溢出。

（3）二进制安全。为C字符串以空字符作为字符串结束的标识，而对于一些二进制文件（如图片等），内容可能包括空字符串，因此C字符串无法正确存取；而所有 SDS 的API 都是以处理二进制的方式来处理 buf 里面的元素，并且 SDS 不是以空字符串来判断是否结束，而是以 len 属性表示的长度来判断字符串是否结束。

（4）减少修改字符串的内存重新分配次数。C语言由于不记录字符串的长度，所以如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，字符串长度减小时会造成内存泄露。而对于SDS，由于len属性和free属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略：空间预分配：对字符串进行空间扩展的时候，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重分配次数；惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用free属性将这些字节的数量记录下来，等待后续使用。（当然SDS也提供了相应的API，当我们有需要时，也可以手动释放这些未使用的空间。）这个特性对于redis这种追求高吞吐量的缓存中间件来说无疑是非常重要的。

二、链表

链表是一种常用的数据结构，C语言内部是没有内置这种数据结构的实现，所以Redis自己构建了链表的实现。Redis链表具有以下特性：

（1）双端：链表具有前置节点和后置节点的引用，获取这两个节点时间复杂度都为O(1)。

（2）无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL 对链表的访问都是以 NULL 结束。

（3）带链表长度计数器：通过 len 属性获取链表长度的时间复杂度为 O(1)。

（4）多态：链表节点使用 void* 指针来保存节点值，可以保存各种不同类型的值。

三、字典

字典又称为符号表或者关联数组、或映射（map），是一种用于保存键值对的抽象数据结构。字典中的每一个键 key 都是唯一的，通过 key 可以对值来进行查找或修改。C 语言中没有内置这种数据结构的实现，所以字典依然是 Redis自己构建的。Redis 的字典使用哈希表作为底层实现。为了追求极致的性能redis在hash表的扩缩容、hash冲突的解决方式上都做了一些值得借鉴的特殊处理。

（1）采用链地址法解决哈希冲突，提升效率。通过字典里面的 *next 指针指向下一个具有相同索引值的哈希表节点。

（2）采用渐近式rehash提升性能。 也就是rehash扩容和收缩操作不是一次性、集中式完成的，而是分多次、渐进式完成的。如果保存在Redis中的键值对只有几个几十个，那么rehash操作可以瞬间完成，但是如果键值对有几百万，几千万甚至几亿，那么要一次性的进行 rehash，势必会造成Redis一段时间内不能进行别的操作。所以Redis采用渐进式 rehash 这样在进行渐进式rehash期间，字典的删除查找更新等操作可能会在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是进行 增加操作，一定是在新的哈希表上进行的。

Redis的字典底层使用哈希表实现，每个字典通常有两个哈希表，一个平时使用，另一个用于rehash时使用，使用链地址法解决哈希冲突。

四、跳跃表

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的，跳跃表通常是有序集合的底层实现之一，表中的节点按照分值大小进行排序。具有如下性质：

(1)由很多层结构组成；

(2)每一层都是一个有序的链表，排列顺序为由高层到底层，都至少包含两个链表节点，分别是前面的head节点和后面的nil节点；

(3)最底层的链表包含了所有的元素；

(4)如果一个元素出现在某一层的链表中，那么在该层之下的链表也全都会出现（上一层的元素是当前层的元素的子集）；

(5)链表中的每个节点都包含两个指针，一个指向同一层的下一个链表节点，另一个指向下一层的同一个链表节点；

redis中zset便是主要用这种数据结果，skiplist的主要操作过程如下：

（1）搜索：从最高层的链表节点开始，如果比当前节点要大和比当前层的下一个节点要小，那么则往下找，也就是和当前层的下一层的节点的下一个节点进行比较，以此类推，一直找到最底层的最后一个节点，如果找到则返回，反之则返回空。

（2）插入：首先确定插入的层数，有一种方法是假设抛一枚硬币，如果是正面就累加，直到遇见反面为止，最后记录正面的次数作为插入的层数。当确定插入的层数k后，则需要将新元素插入到从底层到k层。

（3）删除：在各个层中找到包含指定值的节点，然后将节点从链表中删除即可，如果删除以后只剩下头尾两个节点，则删除这一层。

我们经常会被问到，为什么redis的ZSET要用跳跃表而没有采用红黑树呢？redis官方给出的答复是ZSET常用的场景是根据SCORE做范围查询，这样利用跳表里面的双向链表，可以方便地操作。跳表虽然在数据存储上更耗内存，但可以调参数来降低内存消耗，和那些平衡树结构达到差不多。除此之外小编觉得链表的插入和删除效率比红黑树还是要高效一些。而redis作为以追求高吞吐为终极目标的缓存数据库，这点无疑尤为重要。

五、整数集合

整数集合（intset）是Redis用于保存整数值的集合抽象数据类型，它可以保存类型为int16_t、int32_t 或者int64_t 的整数值，并且保证集合中不会出现重复元素。整数集合是集合键的底层实现之一，底层由数组构成，升级特性能尽可能的节省内存。

六、压缩列表

压缩列表（ziplist）是Redis为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。压缩列表并不是对数据利用某种算法进行压缩，而是将数据按照一定规则编码在一块连续的内存区域，以达到节省内存的原理。压缩列表是Redis为节省内存而开发的顺序型数据结构，通常作为列表键和哈希键的底层实现之一。

redis中的链表所存储的字符串元素长度小于64字节并且元素数量小于512个时，使用ziplist编码，否则使用linkedlist编码

听完三观的讲解有不明白的地方欢迎留言哦。三观一定拍马过来解答。如有不对的地方也请多多指教，相互学习。