共计 7776 个字符，预计需要花费 20 分钟才能阅读完成。
1.Redis 的根底类型 dictEntry 和 redisObject
2. 程序员应用 redis 时的底层思维
3.String 底层数据结构
4.Hash 数据结构介绍
5.List 数据结构介绍
6.Set 数据结构介绍
7.ZSet 数据结构介绍
8. 总结
1.Redis 的根底类型 dictEntry 和 redisObject
咱们能够先去 redis 的 github 上下载源码：https://github.com/redis/redis
就像咱们的 JAVA 对象，顶层全是 Object一样，咱们的redis 的顶层都是 dictEntry，让咱们来看这样一段源码（dict.h 中）：
typedef struct dictEntry {
void *key; // 示意字符串 就是 redis KV 构造中的 KEY
union {
void *val; //val 指向的是 redisObject 中
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; /* Next entry in the same hash bucket. */
void *metadata[]; /* An arbitrary number of bytes (starting at a
* pointer-aligned address) of size as returned
* by dictType's dictEntryMetadataBytes(). */} dictEntry;咱们以最简略的 set k1 v1 为例，因为 Redis 是以 KV 为构造的数据库，每个键值对都会有一个 dictEntry, 这外面指向了 key 和 value 的指针 ，next 指向下一个 dictEntry。
key 是字符串，然而 Redis 没有间接应用 C 的 char 数组，而是存在了 redis 的自定义字符串中（等等上面会解释），value 因为会有不同的类型，redis 将这几种根本的类型形象成了 redisObject 中，实际上五种罕用的数据类型，都是通过 redisObject 来存储的。
咱们看看 redisObject 的源码（server.h）：
typedef struct redisObject {
unsigned type:4; // 以后对象的类型
unsigned encoding:4; // 以后对象的底层编码类型
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or LRU 或者 LFU 的拜访工夫数据
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
int refcount; // 对象援用计数的次数
void *ptr; // 真正指向底层数据结构的指针
} robj;接下来咱们便能够取得这张图片，咱们对 redis 的存储构造就高深莫测了：
为了便于操作，Redis 采纳 redisObject 构造来形象了不同的数据类型，这样所有的数据类型就能够用雷同的模式在函数之间传递，而不是应用特定的类型构造。同时，为了辨认不同的数据类型，
redisObject 中定义了 type 和encoding 字段 对不同的数据类型加以辨别。简略地说，redisObject 就是 String,hash,list,set,zset 的父类，能够在函数间传递的时候暗藏具体的根本类型信息，所以作者形象了 redisObject。
2. 程序员应用 redis 时的底层思维
咱们刚开始学习 redis 的时候，只会调用调用顶层的 api，所以咱们看到的 redis 是这个样子的：
然而咱们学习了 redis 的的底层数据结构后，咱们将会看到这样子的 redis：
3.String 底层数据结构
Redis 的 String 类型，其实底层是由 三种数据结构组成的 ：
1）int： 整数且小于二十位整数以下的数字数据才会应用这个类型
2）embstr（embedded string，示意嵌入式的 String）： 代表 embstr 格局的 SDS（Simple Dynamic String 简略动静字符串），保留长度小于 44 字节的字符串。
3）raw：保留长度大于 44 的字符串
咱们先对下面这个案例做一个测试：
咱们发现保留的数据内容，会随着保留内容的变动而发生变化。
这就是 redis 中，String 类型没有间接复用 C 语言的字符串，而是 新建了属于本人的构造————SDS（简略动静字符串）。在 Redis 数据库里，蕴含字符串的键值对都是由 SDS 实现的，Redis 中所有的值对象蕴含的字符串对象底层也是由 SDS 实现！
咱们点开 sds.h，发现 sds 由多种类型形成：
struct __attribute__ ((__packed__)) sdshdr5 { // 被废除
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */ // 已用长度
uint8_t alloc; /* excluding the header and null terminator */ // 字符串最大字节长度
unsigned char flags; /* 3 lsb of type, 5 unused bits */ // 用来展现的 sds 类型
char buf[]; // 真正无效的字符串数据，长度由 alloc 管制};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];};
它用
sdshdr5、(2^5=32byte)
sdshdr8、(2 ^ 8=256byte)
sdshdr16、(2 ^ 16=65536byte=64KB)
sdshdr32、(2 ^ 32byte=4GB)
sdshdr64，2 的 64 次方 byte=17179869184G
来存储不同长度的字符串，len 示意长度，这样获取字符串长度就能够在 O(1)的状况下，拿到字符串，而不是像 C 语言一样去遍历。
alloc 能够计算字符串未被调配的空间，有了这个值就能够引入预调配空间的算法了，而不必去思考内存调配的问题。
buf 示意字符串数组，真存数据的。
为什么 Redis 要从新设计一个字符串 SDS，而不间接应用 char[]数组呢？
咱们能够从 redis 和 sds 的比照中能够发现：
| C 语言 | SDS | |
|---|---|---|
| 字符串长度解决 | 要从数组的头部开始遍历，直到遇到 ’\0’，工夫复杂度 O（n） | 间接读取长度，工夫复杂度 O（1） |
| 内存重新分配 | 内存超出调配的空间后，会导致下标越界或者溢出 | 预调配：SDS 调配后，如果长度小于 1M，那么会额定调配一个与 len 雷同长度的未应用的空间。惰性开释：SDS 短时并不会发出多余的空间，而是将多余的空间记录下来，如果有变更操作，间接应用多余的空间，缩小调配频率。 |
| 二进制平安 | 数据内容可能蕴含 ’\0’，C 语言遇上 ’\0’ 会提前结束，不会读取前面的内容 | 有了 len 作为长度，就不会有遍历这种问题了 |
论断：
只有整数才会应用 int，如果是浮点数，就是用字符串保留。
embstr 与 raw 类型底层的数据结构其实都是 SDS (简略动静字符串，Redis 外部定义 sdshdr5，sdshdr8 等等)。
存储构造：
1）int
当数据类型为整数的时候，RedisObject 中的 prt 指针间接赋值为整数数据，不会额定指向整数了，节俭内存开销。redis 在一万以内只会存一份，就像 JAVA 的 Integer -128~127 只存一份。
2) embstr
当保留的字符串数据小于等于 44 字节的时候，embstr 类型将会调用内存调配函数，只调配一块间断的空间，空间中一次蕴含 redisObject 和 sdshdr 两个构造，让元数据，指针和 sds 是一块间断的区域，防止内存碎片。
3) raw
字符串大于 44 字节时，SDS 的数据质变多变大了，SDS 和 RedisObject 布局会离开，会给 SDS 调配多的空间并用指针指向 SDS 构造，raw 类型将会调用两次内存调配函数，调配两块内存空间，一块用于蕴含 redisObject 构造，而另一块用于蕴含 sdshdr 构造。
调配流程图：
4.Hash 数据结构介绍
在查看 Hash 的数据结构之前，咱们先来看这样的一个配置：
咱们可能看不太懂，我来给解释一下：
hash-max-ziplist-entries：应用压缩列表保留哈希汇合中的最大元素个数。
hash-max-ziplist-value：应用压缩列表保留时哈希汇合中单个元素的最大长度。
可能咱们这么说还是不太懂，上案例：
Hash 数据类型也和 String 有相似之处，达到了肯定的阈值之后就会对数据结构进行降级。
数据结构：
1）hashtable 就是和 java 当中应用的 hashtable 一样，是一个 数组 + 链表的构造。
2）ziplist 压缩链表
咱们先来看一下 压缩链表的源码：
ziplist 是一种比拟紧凑的编码格局，设计思路是用工夫换取空间 ，因而 ziplist 实用于字段个数少，且字段值也较小的场景 。压缩列表内存利用率高的起因与 其连续性内存个性 是分不开的。
当一个 hash 对象，只蕴含大量的键，且每个键值对的值都是小数据，那么 ziplist 就适宜做为底层实现。
ziplist 的构造：
它是一个 通过非凡编码的双向链表 ，它尽管是双向链表，但它 不存储 指向上一个链表节点和指向下一个链表节点的指针，而是 存储上一个节点的长度和以后节点的长度，通过就义局部读写性能，来换取高空间利用率。
zlbytes 4 字节，记录整个压缩列表占用的内存字节数。
zltail 4 字节，记录压缩列表表尾节点的地位。
zllen 2 字节，记录压缩列表节点个数。
zlentry 列表节点，长度不定，由内容决定。
zlend 1 字节，0xFF 标记压缩的完结。
节点的构造源码：
typedef struct zlentry {
unsigned int prevrawlensize; // 上一个节点的长度
unsigned int prevrawlen; // 存储上一个链表节点长度所须要的的字节数
unsigned int lensize; // 以后节点所须要的的字节数
unsigned int len; // 以后节点占用的长度
unsigned int headersize; // 以后节点的头大小
unsigned char encoding; // 编码方式
unsigned char *p; // 指向以后节点起始地位
因为保留了这个构造，能够让 ziplist 从后往前遍历。
为什么有链表了，redis 还要整出一个压缩链表？
1）一般的双向链表会有两个前后指针 ，在存储数据很小的状况下， 咱们存储的理论数据大小可能还没有指针占用的内存大。而 ziplist 是一个非凡的双向链表，并没有保护前后指针这两个字段，而是存储上一个 entry 的长度和以后 entry 的长度，通过长度推算下一个元素在什么中央。就义读取的性能，获取高效的空间利用率，因为（简短 KV 键值对）存储指针比存储 entry 长度更费内存，这是典型的工夫换空间。
2）链表是不间断的，遍历比较慢，而 ziplist 却能够解决这个问题，ziplist 将一些必要的偏移量信息都记录在了每一个节点里，使之能跳到上一个节点或者尾节点节点。
3）头节点里有头结点同时还有一个参数 len，和 SDS 类型相似，这就是用来记录链表长度的。因而获取链表长度时不再遍历整个链表 ，间接拿到 len 值就能够了， 获取长度的工夫复杂度是 O（1）。
遍历过程：
通过指向表尾节点的地位指针 zltail, 减去节点的 previous_entry_length，失去前一个节点的起始地址的指针。如此循环，从表尾节点遍历到表头节点。
5.List 数据结构介绍
咱们先来看一下 list 的默认配置：
ziplist 压缩配置：list-compress-depth 0
示意一个 quicklis t 两端不被压缩的节点个数 ，这里的 quicklist（下文会解释）是 指 quickList 双向链表的节点，而不是指 ziplist 外面的数据项个数。
参数取值含意：
0：是个非凡值，示意都不压缩，这是 redis 的默认值。
1: 示意 quicklist 两端各有 1 个节点不压缩，两头的节点压缩。
2: 示意 quicklist 两端各有 2 个节点不压缩，两头的节点压缩。
3: 示意 quicklist 两端各有 3 个节点不压缩，两头的节点压缩。
依此类推…
(2) ziplist 中 entry 配置：list-max-ziplist-size -2
当取 正值 的时候，示意 依照数据项个数 来限定每个 quicklist 节点上的 ziplist 长度。比方当这个配置为 5 的时候，ziplist 里最多有 5 个数据项。
当取 负值 的时候，示意依照 占用字节数 来限定 quicklist 节点上的 ziplist 长度。这时，它只能取 -1~- 5 这几个值。
-5: 每个 quicklist 节点上的 ziplist 大小不能超过 64 Kb。（注：1kb => 1024 bytes）
-4: 每个 quicklist 节点上的 ziplist 大小不能超过 32 Kb。
-3: 每个 quicklist 节点上的 ziplist 大小不能超过 16 Kb。
-2: 每个 quicklist 节点上的 ziplist 大小不能超过 8 Kb。（- 2 是 Redis 给出的默认值）
-1: 每个 quicklist 节点上的 ziplist 大小不能超过 4 Kb。
quicklist 构造介绍：
list 用 quicklist 来存储，quicklist 存储了一个双向链表，每一个节点都是一个 ziplist。
](/img/bVcX7sS)
源码：
typedef struct quicklist {
quicklistNode *head; // 指向双向列表的表头
quicklistNode *tail; // 指向双向链表的表尾
unsigned long count; // 所有 ziplist 中共存储了多少个元素 /* total count of all entries in all listpacks */
unsigned long len; // 双向链表的长度，node 的数量 /* number of quicklistNodes */
signed int fill : QL_FILL_BITS; /* fill factor for individual nodes */
unsigned int compress : QL_COMP_BITS; // 压缩深度 /* depth of end nodes not to compress;0=off */
unsigned int bookmark_count: QL_BM_BITS;
quicklistBookmark bookmarks[];} quicklist;typedef struct quicklistNode {
struct quicklistNode *prev; // 前指针
struct quicklistNode *next; // 后指针
unsigned char *entry; 指向理论的 ziplist
size_t sz; /* entry size in bytes */
unsigned int count : 16; /* count of items in listpack */
unsigned int encoding : 2; /* RAW==1 or LZF==2 */
unsigned int container : 2; /* PLAIN==1 or PACKED==2 */
unsigned int recompress : 1; /* was this node previous compressed? */
unsigned int attempted_compress : 1; /* node can't compress; too small */
unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;6.Set 数据结构介绍
咱们来看一下 set 的配置：
set-max-intset-entries
set 数据类型汇合中，如果 没有超出了这个数量，且数据元素都是整数的话，类型为intset, 否则为hashtable。
intset 类型：
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];} intset;看到源码后，咱们能够得出，论断，intset 的数据结构实质是一个数组。而且 ** 存储数据的时候是有序的，因为在查找数据的时候是通过二分查找来实现的。
**
咱们略微剖析一下 set 的单个元素的增加流程。
如果 set 曾经是 hashtable 的编码，那么走 hashtable 的增加流程。
如果原来是 intset：
1）能转化为 int 对象 ，就用 intset 保留。
2） 如果长度超过设置 ，就用 hashtable 保留
3） 其它状况对立用 hashtable 保留。
7.ZSet 数据结构介绍
咱们看一下 ZSet 的配置：
当有序汇合中蕴含的元素数量超过服务器属性 zset_max_ziplist_entries 的值（默认值为 128），
或者有序汇合中新增加元素的 member 的长度大于服务器属性 zset_max_ziplist_value 的值（默认值为 64）时，redis 会应用跳跃表（下文会解释）作为有序汇合的底层实现。
否则会应用 ziplist作为有序汇合的底层实现
看一下源码：
当元素个数大于设置的个数或者元素的列表原本就是 skiplist 编码的时候，用 skiplist 存储，否则就用 ziplist 存储。
skiplist（跳表）是什么：
跳表是一种以空间换取工夫的构造。
因为 链表是无奈进行二分查找的 ，因而 借鉴了数据库索引 的思维，提取出链表中要害节点（索引），当初要害节点上进行查找，再进入链表进行查找。
提取了很多要害节点，就造成了跳表。
因为跳表是以一种跳跃式的数据存在，当咱们 查问‘14’这个数据的时候，能够跳过很多无用的数据，缩小遍历的次数。
跳表是一个典型的空间换工夫的解决方案，而且只有在 数据量较大的状况下能力体现进去劣势。还是要读多写少的状况才适宜应用 ，所以它的适用范围还是比拟无限的， 新增或者删除的时候要把所有数据都更新一遍。
8. 总结