author：徐振东

createTime：2022-05-16

updateTime：2022-06-10

---

2022-06-10: 培训结束

# SDS 动态字符串

结构定义：

struct sdshdr {
    int len;  // 记录buf的已使用的空间
    int free; // buf中空闲空间长度
    char buf[]; //存储的实际内容  
}

1. 字符串长度处理

   在C语言中，要获取字符串的长度，需要从头开始遍历，时间复杂度为O(n); Redis中，对数据结构中定义了len字段记录当前字符串长度，可以直接获取，时间复杂度为O(1)

2. 减少内存重新分配的次数

   在C语言中，修改字符串，需要重新分配内存，修改越频繁，内存分配就越频繁，而分配内存是比较消耗性能的，在Redis中，SDS提供了两种优化策略：空间预分配和惰性空间释放

3. 空间预分配

   SDS在修改和空间扩充时，除了分配必要的空间，还会分配额外未时间的空间存储于字段 free中，这样，如果后面字符的发生变更后就不需要重新分配内存了，修改完字符后修改len和free字段即可

4. 惰性空间释放

   当SDS缩短时，也不回收多余的内存空间，而是用free记录下多余的剩余空间

# 哈希

Redis 作为一个key-value的内存数据库，它使用一张全局的哈希来保存所有的键值对。这张哈希表，有多个哈希桶组成，一个哈希桶由多个entry元素组成，每个entry有 *key、*value 和 *next三个指针字段。*key 指向真实的键，*value指向实际的值，*next指向hash冲突的下一个entry元素。

通过Hash结构，我们可以在O(1)的时间复杂度内快速找到想要的值

# 跳跃表

跳跃表是Redis特有的数据结构，它其实就是在链表的基础上，增加多级索引，以提高查找效率。

• 每一层都有一条有序的链表，最底层的链表包含了所有的元素。
• 跳跃表支持平均 O（logN）,最坏 O（N）复杂度的节点查找，还可以通过顺序性操作批量处理节点。

# 压缩列表

压缩列表ziplist是列表和哈希的底层实现之一。它是由一系列特殊编码的内存块构成的列表， 一个ziplist可以包含多个entry， 每个entry可以保存一个长度受限的字符数组或者整数，如下：

• zlbytes ：记录整个压缩列表占用的内存字节数
• zltail: 尾节点至起始节点的偏移量
• zllen : 记录整个压缩列表包含的节点数量
• entryX: 压缩列表包含的各个节点
• zlend : 特殊值0xFF(十进制255)，用于标记压缩列表末端

由于内存是连续分配的，所以遍历速度很快