1.SDS(简单动态字符串)
1.1底层数据结构
@Data
public class SDS {
//已经使用的长度
private int len;
//未使用长度
private int free;
//字符数组，长度=len+free+1，字符串末尾以 '\0'结束
private char[] buf;
}
1.2重点回顾
- 获取字符串长度的复杂度为
O(1)- API是安全的，拼接字符串时
避免缓冲区溢出- 修改时，可降低内存分配次数,N次修改，
最多引起N次内存分配- 可保存文本或二进制数据
- 可使用一部分
string.h库中的函数（兼容部分C字符串）
2链表
2.1底层结构
@Data
public class RedisLinkedList {
private Node head;
private Node tail;
private long len;
@Data
public static class Node {
private Node prev;
private Node next;
private Object value;
}
}
2.2重点回顾
- 链表被广泛应用在Redis 中的列表键，发布与订阅，慢查询，监视器等
- 双端链表结构，并保存头尾节点，保存表长度
- 头节点的prev以及尾节点的next 指向null, 所以Redis的链表实现是无环链表
3.字典
3.1底层结构
@Data
public class RedisDict {
//哈希表
private BaseDict[] baseDicts = new BaseDict[2];
//当rehash不在进行时，值为 -1
private int rehashIndex;
@Data
public static class BaseDict {
//哈希表数组
private DictEntry[] dictEntries;
//哈希表大小
private long size;
//哈希表大小掩码，用于索引计算，总是等于 size - 1
private long sizeMask;
//已有节点数量
private long used;
}
@Data
public static class DictEntry {
//键
private Object key;
//值
private Object value;
//下一个节点
private DictEntry next;
}
}
3.2用法
- RedisDict包含一个长度为2的数组，数组中每一项都是一个哈希表，一般情况下，只使用
baseDicts[0], baseDicts[1]只会在对baseDicts[0] 进行rehash时使用。- 除baseDicts[1]外，rehashIndex记录了目前rehash的进度，如果没有rehash,则值为-1
- 哈希冲突的解决办法：链地址法，将冲突的键值以链表的方式进行放置（加入链表的头部）
- rehash : rehash分为一次性rehash,即对全量的数据进行调整（适合数据量比较少时），渐进式rehash,即在每次操作时将部分数据进行迁移，以rehashIndex记录rehash的进度。
- 渐进式hash执行期间的哈希表操作：在此过程中会用到baseDicts[0],baseDicts[1]两个表，字典的删除，查找，更新等操作会在这两个表上进行。在reahsh期间，新增的键会直接加入到baseDicts[1] 中，保证baseDicts[0]的数据只减不增
3.3重点回顾
- 字典被广泛用于redis的各类功能，包括数据库和哈希键
- redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，一个rehash时使用。
- 当字典被用作数据库的底层实现，或者哈希键的底层是现实时，采用 MurmurHash2算法来计算键的hash值
- 哈希表采用链地址法来解决键冲突，被分配到同一个索引上的多个键形成一个单向链表
- 在对哈希表进行扩展或者收缩时，采用渐进式rehash的方式进行
4.跳跃表
- 跳跃表是有序集合的底层实现之一
- redis的跳跃表实现由zskiplist 和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点，表尾节点，长度），而zskiplistNode则用于标示跳跃表节点
- 每个跳跃表的节点的层高都是1至32上之间的随机数
- 在同一个跳跃表中，多个节点可包含相同的分值，单每个节点的成员对象必须是唯一的
- 跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序
5.整数集合
@Data
public class RedisIntSet {
//编码方式(uint32_t)
private int encoding;
//包含的元素个数(uint32_t)
private int length;
//保存元素的数组(int8_t)
private int[] contents;
}
5.1整数集合的特性
- contents中的元素按照大小进行排序，并且不包含重复项
- contents 中元素的类型取决于encoding的类型：当encoding为
INTSET_ENC_INT_16，数组中的每一项都是 一个int16_t类型的整数值（最小-32768，最大32767），当encoding为INTSET_ENC_INT_32时，数组里的每一项都是一个int32_t类型的整数值（最小-2147483648，最大2147483647），当encoding为INTSET_ENC_INT_64时，数组中的每一项是一个int64_t的整数值- 类型升级，当新增的元素类型大于当前元素编码的最大值，则contents数组会自动升级为当前新增元素的编码类型，升级的好处：提升灵活性，节约内存
- 类型降级：暂时不支持类型降级
6.压缩列表
- 压缩列表是列表键和哈希键的底层实现之一，当一个列表键含有少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么redis就会使用压缩列表雷做列表键的底层实现
- 压缩表是redis为了节约内存而开发的，是由一些列特殊编码的
连续内存组成的顺序型数据结构
[图片上传失败...(image-d7260-1540899488341)]- 压缩列表的每一项可以保存一个字节数组或一个整数
[图片上传失败...(image-78f7d7-1540899488341)]
连锁更新：当中间节点变长，变短，删除等触发连锁更新。
6.1重点回顾
- 压缩列表是为了节约内存而开发出来的顺序型数据结构
- 压缩列表被用来做为列表键和哈希键的底层实现之一
- 压缩列表可包含多个节点，每个节点包含一个字节数组或整数值
- 添加或者删除节点可能会触发连锁更新，但这种情况出现的几率不高
7.对象
7.1对象简介
- Redis 并没有直接使用以上这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含
字符串对象，列表对象，哈希对象，集合对象和有序集合对象这5种类型的对象，美中对象都使用到了至少一种我们前面所介绍的数据结构。- 使用对象的好处是，我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。
- Redis的对象系统实现了基于引用计数技术的内存回收机制，当程序不再使用某个对象的时候，这个对象会被自动释放
7.2对象数据结构
@Data
public class RedisObject {
//类型
private RedisType type;
//编码
private RedisEncoding encoding;
//指向底层实现的数据结构引用
private Object ptr;
//引用计数，用于内存回收
private int refCount;
//最后一次的访问时间，用来计算对象的空转时常
private long lru;
public enum RedisType {
REDIS_STRING("字符串对象", "string"),
REDIS_LIST("列表对象", "list"),
REDIS_HASH("哈希对象", "hash"),
REDIS_SET("集合对象", "set"),
REDIS_ZSET("有序集合对象", "zset");
public String objectType;
public String objectTypeOutput;
RedisType(String objectType, String objectTypeOutput) {
this.objectType = objectType;
this.objectTypeOutput = objectTypeOutput;
}
}
public enum RedisEncoding {
REDIS_ENCODING_INT("long类型的整数"),
REDIS_ENCODING_ENMSTR("embstr编码的简单动态字符串"),
REDIS_ENCODING_RAW("简单动态字符串"),
REDIS_ENCODING_HT("字典"),
REDIS_ENCODING_LINKEDLIST("双端链表"),
REDIS_ENCODING_ZIPLIST("压缩列表"),
REDIS_ENCODING_INTSET("整数集合"),
REDIS_ENCODING_SKIPLIST("跳跃表和字典");
public String encodingName;
RedisEncoding(String encodingName) {
this.encodingName = encodingName;
}
}
}
7.3不同类型和编码的对象
[图片上传失败...(image-1bc80a-1540899488341)]
通过encoding属性来设定对象所使用的编码，而不是为特定类型的对象关联一种固定的编码，极大地提升了Redis的灵活性和效率，因为Redis可以根据不同的使用场景来为一个对象设置不同的编码，从而优化对象在某一场景下的效率。
比如，当列表对象包含的元素比较少时，采用压缩列表（节约内存），当元素多时使用双端链表
