前言
声明：参考来源互联网，有任何争议可以留言。站在前人的肩上，我们才能看的更远。
本教程纯手打，致力于最实用教程，不需要什么奖励，只希望多多转发支持。
上一篇都是对一些 redis 基本数据类型 api 的讲解，本篇是数据类型底层实现，主要内容有：
- 为什么使用Redis
- Redis数据结构解析
- SDS简单动态字符串
- 哈希表
- 跳跃表
- 整数集合
- 压缩列表
- Redis中数据结构的对象
- …
1.再谈Redis
Redis 是什么？官话来说就是：
Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker.
Redis 是一个开源的、基于内存的数据结构存储器，可以用作数据库、缓存和消息中间件。
如果想尝试 Redis 命令又懒得安装，可以使用这个 http://try.redis.io/ 网站。
2.为什么要用Redis
上一篇咱们有一定了解
Redis 是**基于内存**，常用作缓存的一种技术，并且 Redis 存储的方式是以 key-value 形式。
那我们为什么不用 Java Map？
Java Map是**本地缓存**的，最主要的特点是轻量以及快速，生命周期随着jvm的销毁而结束，并且在多实例的情况下，每个实例都需要各自保存一份缓存，缓存不具有一致性。
JVM内存太大容易挂掉，还有各种**过期机制、存储结构**需要自己手动来写
Redis 会定期把缓存保存到硬盘，重启恢复数据，丰富的数据结构，缓存机制等实用功能。
3.为什么要使用缓存？
高并发，高可用这是现在互联网经常提到的一个词。在程序出现大量请求是就会出现**性能问题，一般性能问题第一道就是数据库扛不住了**，数据库的读写会有磁盘操作，而磁盘的速度相对内存来说慢很多。
所有我们在中间加一道缓存：
4.Redis数据结构
4.1.SDS简单动态字符串
4.1.1.SDS简单动态字符串
Redis 是由C语言编写的。
我们现在知道 Redis 所有键都是字符串，值有字符串（string）、散列（hash）、列表（list）、集合（set）和有序集合（sorted set）这五种类型的键的底层实现数据结构。
Redis 没有直接使用 C 语言传统的字符串表示（以空字符结尾的字符数组，以下简称 C 字符串）， 而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型， 并将 SDS 用作 Redis 的默认字符串表示。
Redis 使用 sds.h/sdshdr 结构表示一个 SDS 值：
struct sdshdr { // 记录 buf 数组中已使用字节的数量 // 等于 SDS 所保存字符串的长度 int len; // 记录 buf 数组中未使用字节的数量 int free; // 字节数组，用于保存字符串 char buf[]; };
上图是 SDS 示例，以空字符结尾 '\0'。遵循空字符结尾这一惯例的好处是， SDS 可以直接重用一部分 C 字符串函数库里面的函数。
举个例子， 如果我们有一个指向图 2-1 所示 SDS 的指针 s ， 那么我们可以直接使用 stdio.h/printf 函数， 通过执行以下语句：
printf("%s", s->buf);
来打印出 SDS 保存的字符串值 “Redis” ， 而无须为 SDS 编写专门的打印函数。
4.1.2.SDS简单动态字符串好处
- sdshdr数据结构中用len属性记录了字符串的长度。那么获取字符串的长度时，时间复杂度只需要
O(1)。常数复杂度获取字符串长度。 - SDS不会发生溢出的问题，如果修改SDS时，空间不足。先会扩展空间，再进行修改！(内部实现了动态扩展机制)。杜绝缓冲区溢出。
- SDS可以**减少内存分配的次数(空间预分配机制)。在扩展空间时，除了分配修改时所必要的空间，还会分配额外的空闲空间(free 属性)。减少修改字符串长度时所需的内存重分配次数**。
- SDS是**二进制安全**的，SDS 以二进制的方式来处理SDS存放在buf数组里的数据。
- 可以使用一部分
库中的函数。兼容部分 C 字符串函数。
4.2.Redis 链表和链表节点
Java 学习者对链表应该都很熟悉，链表是 Java 中一种典型且常用的数据构。
每个**链表节点**使用一个 adlist.h/listNode 结构来表示：
typedef struct listNode { // 前置节点 struct listNode *prev; // 后置节点 struct listNode *next; // 节点的值 void *value; } listNode;
使用listNode是可以组成链表了，Redis中**使用list结构来持有链表**：
typedef struct list { // 表头节点 listNode *head; // 表尾节点 listNode *tail; // 链表所包含的节点数量 unsigned long len; // 节点值复制函数 void *(*dup)(void *ptr); // 节点值释放函数 void (*free)(void *ptr); // 节点值对比函数 int (*match)(void *ptr, void *key); } list;
由一个 list 结构和三个 listNode 结构组成的链表：
4.2.2.Redis 链表重点
- 链表被广泛用于实现 Redis 的各种功能， 比如列表键， 发布与订阅， 慢查询， 监视器， 等等。
每个链表节点由一个 listNode 结构来表示， 每个节点都有一个指向前置节点和后置节点的指针， 所以 Redis 的链表实现是双端链表。
每个链表使用一个 list 结构来表示，这个结构带有表头节点指针、表尾节点指针、以及链表长度等信息。
因为链表表头节点的前置节点和表尾节点的后置节点都指向 NULL ， 所以 Redis 的链表实现是无环链表。
通过为链表设置不同的类型特定函数， Redis 的链表可以用于保存各种不同类型的值。
4.3.Redis 字典
4.3.1.哈希表
字典是 Redis 中的一个概念，Redis 的字典使用哈希表作为底层实现。 一个哈希表里面可以有多个哈希表节点， 而每个哈希表节点就保存了字典中的一个键值对。
空哈希表
Redis 字典所使用的哈希表由 dict.h/dictht 结构定义：
typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值 // 总是等于 size - 1 unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used; } dictht;
哈希表节点
哈希表节点使用 dictEntry 结构表示， 每个 dictEntry 结构都保存着一个键值对：
typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; //uint64_t整数 int64_t s64; //int64_t整数 } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next; } dictEntry;
有没有注意到，上图有个冲突，俩个键在同一个节点，这就是 Redis 解决键冲突 ，Redis 的哈希表使用链地址法（separate chaining）来解决键冲突：
每个哈希表节点都有一个 next 指针， 多个哈希表节点可以用 next 指针构成一个单向链表， 被分配到同一个索引上的多个节点可以用这个单向链表连接起来， 这就解决了键冲突的问题。
rodert单排学习redis进阶【青铜】2：https://developer.aliyun.com/article/new?spm=a2c6h.13046898.J_eBhO-wcawiLJRkGqHmozR.89.1ad56ffaywWtYb#/
