1. 概述

根据《Redis设计与实现》一书，总结下Redis底层数据结构和对象类型。日常工作中，我们直接使用的是对象，但每种对象至少对应一种底层数据结构，不同使用场景，可以为对象设置不同数据结构，从而优化使用效率。

2. 数据结构

2.1. 简单动态字符（简称SDS）

2.1.1. 结构与实现

由已使用长度、空闲长度、字节数组组成：

每个sds.h/sdshdr结构表示一个SDS值：

struct sdshdr{

//记录buf数组中已使用字节的数量

int len;

//记录buf数组中未使用字节的数量

int free;

//字节数组，用于保存字符串

char buf[];

}

2.1.2. 特性

1) 避免发送缓冲区溢出

当需要对SDS进行就修改时，API会先检查SDS的空间，如不满足，会自动将空间扩展至执行修改所需的大小；

2) 减少内存分配次数

空间预分配，当进行空间扩展时，不仅会为SDS分片修改所必须的空间，还会分配额外的未使用空间；预分配可以减少连续执行字符串增长操作所需的内存重分配次数；

3) 惰性释放空间

当字符串长度缩短时，并不是立即使用内存重分配来回收缩短后的字节空间，而是使用free属性，将这些字节的数量记录下来，将来要扩容的话，这些未使用的空间就可能派上用场，避免频繁扩缩容，当然底层也提供了真正释放SDS未使用空间的API，不用担心惰性空间释放策略造成内存浪费；

2.2. 链表

作为常用的数据结构，链表一般出现在高级语言中，Redis使用C语言编写，没有这种数据结构，所以Redis自己构建了这种数据结构；

2.2.1. 结构与实现

链表和链表节点，使用adlist.h/list来表示链表，使用adlist.h/listNode结构来标识链表节点，

下图是由一个list结构和三个listNode结构组成的链表：

2.2.2. 应用范围

链表在Redis中的应用广泛，列表键的底层实现之一就是链表。当一个列表键元素数量较多，又或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。

2.2.3. 特性

1) 链表被广泛用于实现Redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等；

2) 每个链表节点由一个listNode结构来表示，每个节点都有一个指向前置节点和后置节点的指针，所以Redis的链表实现是双端链表；

3) 每个链表使用一个list结构来表示，这个结构带有表头节点指针、表尾节点指针，以及链表长度等信息；

4) 因为链表表头节点的前置节点和表尾节点的后置节点都指向NULL，所以Redis的链表实现是无环链表；

5) 通过为链表设置不同的类型特定函数，Redis的链表可以用于保存各种不同类型的值。

2.3. 字典

字典可以理解为java中的map结构，一个键（key）可以和一个值（value）进行关联（或者说将键映射为值），这些关联的键和值就称为键值对。

2.3.1. 结构与实现

字典由dict.h/dict结构表示：

字典所使用的哈希表由dict.h/dictht结构定义：

一个完整的字典结构：

2.3.2. 应用范围

Redis的数据库就是使用字典来作为底层实现的，对数据库的增、删、查、改操作也是构建在对字典的操作之上的。

2.4. 跳跃表

2.4.1. 结构与实现

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的

跳跃表由zskiplist和zskiplistNode两个结构组成，其中在skiplist用于保持跳表信息，如表头节点、表尾节点、长度；zskiplistNode包括层、分值、值对象；

2.4.2. 应用范围

应用于有序集合建和集群节点中内部数据结构。

2.5. 整数集合

2.5.1. 结构与实现

整数集合由intset实现，包括编码方式、元素数量、保存的元素数组；

每个intset.h/intset结构表示一个整数集合：

整数集合数据样例：

2.5.2. 应用范围

当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现；

2.6. 压缩列表

2.6.1. 结构与实现

压缩列表，是由一系列特殊编码的连续内存块组成的顺序型数据结构。由压缩列表和压缩列表节点构成，包括压缩列表总长度、距离尾节点偏移量、列表节点；压缩列表节点由前一个节点的length、encoding、content三部分组成；

2.6.2. 应用范围

压缩列表用是列表建和哈希建的底层实现之一。

2.6.3. 特点

1) 压缩列表是一种为节约内存而开发的顺序型数据结构；

2) 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或一个整数值；

3) 添加或删除节点时，可能引起连锁更新，但出现几率并不高；

3. 对象类型

Redis并没有直接使用上面这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种数据结构。

Redis中每个对象都由一个redisObject结构标识，结构中和保存数据有关的三个属性为type属性、encoding属性、ptr属性；

type属性记录了对象的类型：

encoding属性记录了对象所使用的编码：

不同对象类型和底层数据结构的对应：

4. 总结

1) 当称呼一个键为“字符串键”时，是指这个数据库键对应的值为字符串对象，当称呼一个键为“列表键”时，是指这个数据库键对应的值为列表对象；因为Redis中所有的key都为字符串，不用强调key的类型；

2) 通过encoding属性来设定对象所使用的编码，而不是为特定类型的对象关联一种固定的编码，极大地提升了Redis的灵活性和效率，因为Redis可以根据不同的使用场景来为一个对象设置不同的编码，从而优化对象在某一场景下的效率。

举个例子：

在列表对象包含的元素比较少时，Redis使用压缩列表作为列表对象的底层实现：因为压缩列表比双端链表更节约内存，并且在元素数量较少时，在内存中以连续块方式保存的压缩列表比起双端链表可以更快被载入到缓存中；随着列表对象包含的元素越来越多，使用压缩列表来保存元素的优势逐渐消失时，对象就会将底层实现从压缩列表转向功能更强、也更适合保存大量元素的双端链表上面；