总述

Redis 数据库里面的每个键值对（key-value pair）都是由对象（object）组成的：

  • 其中， 数据库键总是一个字符串对象（string object）；

  • 而数据库键的值则可以是字符串对象、 列表对象（list object）、 哈希对象（hash object）、 集合对象（set object）、 有序集合对象（sorted set object）这五种对象中的其中一种。

    字符串类型介绍

    1: redis底层并没有使用c语言字符串， 而是自己定义了一个叫做sds的动态字符串
    2: sds结构如下

    1. struct sdshdr {
    2.   // 记录 buf 数组中已使用字节的数量
    3.   // 等于 SDS 所保存字符串的长度
    4.   int len;
    5.   // 记录 buf 数组中未使用字节的数量
    6.   int free;
    7.   // 字节数组，用于保存字符串
    8.   char buf[];
    9. };

    3: c语言字符串的缺点

  • 获取长度复杂度高

  • api不安全， 可能会产生缓冲区溢出： 需要程序员提前计算空间是否满足， 不满足就要分配足够的空间
  • 每次拼接字符串都要重新进行一次内存重分配操作， 如果忘记会导致缓冲区溢出
  • 只能保存文件数据， 字符串中不能保存空字符， 否则程序就会认为是字符串的结尾， 而sds是通过len来判断字符串结尾的， 因此没有这个限制

4: sds独特的优势
image.png

5: 使用场景
数据库键总是一个字符串对象
数据库值可以是个字符串对象

压缩列表

1: 为了节省内存而开发， 是一块连续的字节数组
2: 数据结构
image.png
previout_entry_length: 为了可以做到反向遍历
encoding: 为了支持多种类型，(字节数组和正数值)， 功能是对content内容的解释：content长度和数据类型
content: 具体存储内容
zlbytes: 总字节数
zltail: 尾节点
zllen: 节点总数

2: 核心操作
插入节点： 编码， 重新分配空间， 数据拷贝， 时间复杂度O(n)

3: 连锁更新

  • 如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性需要用 1 字节长的空间来保存这个长度值。
  • 如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性需要用 5 字节长的空间来保存这个长度值。
  • 每次插入或者删除元素的时候可能会产生连锁更新问题
  • 举例说明： a1(253)-a2(253)-a3(253), 往a2前面插入500字节的节点时， a2的空间会比以前多4字节， 内存需要重新分配，依次扩展a3也是一样的
  • 时间复杂度： O(n^2)
  • 出现的条件极为苛刻， 因此概率极低「有多个连续的、长度介于 250 字节至 253 字节之间的节点， 连锁更新才有可能被引发」

4: 应用场景
列表对象
有序集合
哈希对象

5: 为什么当前结构存储的数据条目达到一定数值使用压缩列表就不好？
压缩列表的新增、删除的操作平均时间复杂度为O(N)，随着N的增大，时间必然会增加

跳表

  • 跳跃表是有序集合的底层实现之一， 除此之外它在 Redis 中没有其他应用。
  • Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成， 其中 zskiplist 用于保存跳跃表信息（比如表头节点、表尾节点、长度）， 而 zskiplistNode 则用于表示跳跃表节点。
  • 每个跳跃表节点的层高都是 1 至 32 之间的随机数。
  • 基于运气的一种数据结构

redis的hash对象实现机制

  • 使用压缩列表或者hashtable实现

image.png

  • 解决冲突采用开链法
  • 扩容时机： 负载因子（桶的个数和节点总个数有关）
  • rehash采用，桶节点增加2倍，之后采用渐进式的算法逐渐迁移， 好处不会阻塞客户端使用
  • 和golang-map的区别是， map中一个节点可以放8个keyvalue,数据结构更紧凑，节省内存

image.png

  • 使用压缩列表保存时， 健值对是连续存储的

编码转换规则：
当哈希对象可以同时满足以下两个条件时， 哈希对象使用 ziplist 编码：

  • 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节；
  • 哈希对象保存的键值对数量小于 512 个；
  • 总结一句话： 如果要使用压缩列表，节点的数量和长度都要满足一定要求

**