Redis 底层数据结构

SDS（动态字符串）

• SDS是simple dynamic string的缩写，Redis中所有场景中出现的字符串，基本都是由SDS来实现的。
  • 所有非数字的key，例如set msg "hello world" 中的key msg
  • 字符串数据类型的值，例如`` set msg "hello world”中的msg的值”hello wolrd”
  • 非字符串数据类型中的"字符串值”，例如RPUSH fruits "apple" "banana" "cherry"中的”apple” "banana” "cherry”

• 数据结构
  • free：还剩多少空间。
  • len：字符串长度。
  • buf：存放的字符数组。
• 空间预分配：为减少修改字符串带来的内存重分配次数，sds采用了一次管够的策略。
  • 若修改之后sds长度小于1MB，则多分配现有len长度的空间。
  • 若修改之后sds长度大于等于1MB，则扩充除了满足修改之后的长度外，额外多1MB空间。
• 惰性空间释放：为避免缩短字符串时候的内存重分配操作，sds在数据减少时，并不立刻释放空间。

int

• Redis中存放的各种数字的数据类型，包括故意加引号的数字。

双向链表

• 每个节点listNode可以通过prev和next指针分布指向前一个节点和后一个节点组成双端链表，同时每个链表还会有一个list结构为链表提供表头指针head，表尾指针tail，以及链表长度计数器len，还有三个用于实现多态链表的类型特定函数。
  • dup：用于复制链表节点所保存的值。
  • free：用于释放链表节点所保存的值。
  • match：用于对比链表节点所保存的值和另一个输入值是否相等。

Ziplist（压缩列表）

• Redis的列表键和哈希键的底层实现之一，此数据结构是为了节约内存而开发的，和各种语言的数组类似，它是由连续的内存块组成的，这样一来，由于内存是连续的，就减少了很多内存碎片和指针的内存占用，进而节约了内存。
  • zlbytes：记录整个压缩列表占用的内存字节数，在压缩列表内存重分配，或者计算zlend的位置时使用。
  • zltail：记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过该偏移量，可以不用遍历整个压缩列表就可以确定表尾节点的地址。
  • zllen：记录压缩列表包含的节点数量，但该属性值小于UINT16_MAX(65535）时，该值就是压缩列表的节点数量，否则需要遍历整个压缩列表才能计算出真实的节点数量。
  • entryX：压缩列表的节点。
  • zlend：特殊值0xFF（十进制255)，用于标记压缩列表的末端。

• 每个压缩列表节点可以保存一个字节数字或者一个整数值，结构如下。
  • previous_entry_length：记录压缩列表前一个节点的长度。
  • encoding：节点的encoding保存的是节点的content的内容类型。
  • content:content区域用于保存节点的内容，节点内容类型和长度由encoding决定。

• 元素的遍历
  1. 先找到列表尾部元素。
  2. 然后再根据ziplist节点元素中的previous_entry_length属性，来逐个遍历。
• 连锁更新
  • entry元素的结构，有一个previous_entry_length字段，它的长度要么都是1个字节，要么都是5个字节。
    • 前一节点的长度小于254字节，则previous_entry_length长度为1字节。
    • 前一节点的长度大于254字节，则previous_entry_length长度为5字节。
  • 假设现在存在一组压缩列表，长度都在250字节至253字节之间，突然新增一新节点new长度大于等于254字节，会从后往前将原有的所有entry的长度都变长，程序需要不断的对压缩列表进行空间重分配工作，直到结束。
  • 除了增加操作，删除操作也有可能带来"连锁更新”

intset

• 整数集合（intset）是Redis用于保存整数值的集合抽象数据结构，可以保存类型为int16_t,int32_t,int64_t的整数值，并且保证集合中不会出现重复元素。

跳表

• 跳跃表其实可以把它理解为多层的链表，它有如下的性质：
  • 多层的结构组成，每层是一个有序的链表
  • 最底层（level 1）的链表包含所有的元素。
  • 跳跃表的查找次数近似于层数，时间复杂度为O(logn)，插入，删除也为 O(logn)
  • 跳跃表是一种随机化的数据结构，跳跃表维持结构平衡的成本是比较低的，完全是依靠随机，相比二叉查找树，在多次插入删除后，需要Rebalance来重新调整结构平衡。
• 上浮元素：每隔随机元素，把它放到上一层的链表当中，组成多层链表结构。

• 查找元素：从上层开始查找，大数向右找到头，小数向左找到头，例如我要查找17，查询的顺序是：13 -> 46 -> 22 -> 17，如果是查找35，则是 13 -> 46 -> 22 -> 46 -> 35，如果是54，则是 13 -> 46 -> 54
• 添加元素：是通过抛硬币的方式来决定该元素会出现到多少层，也就是说它会有 1/2的概率出现第二层，1/4 的概率出现在第三层，以此类推。
• 删除元素：跳跃表的删除很简单，只要先找到要删除的节点，然后顺藤摸瓜删除每一层相同的节点就好了。

Redis五种数据结构的实现

Redis对象

• Redis中并没有直接使用以上所说的各种数据结构来实现键值数据库，而是基于一种对象，对象底层再间接的引用上文所说的具体的数据结构。

字符串

• int：数字的时候。
• raw：长字符串（长度大于39个字节）
• embstr：短字符串（长度小于39个字节）
• 注意:embstr和raw都是由SDS动态字符串构成的，唯一区别是：raw 是分配内存的时候，RedisObject 和 SDS 各分配一块内存，而embstr是 RedisObject 和 SDS 在同一块内存中。

list

• ziplist：列表对象所有字符串元素长度都小于64个字节且元素数量小于512
• 双向链表：不满足ziplist条件的其他情况。

hash

• ziplist：元素数量小于512且所有元素长度小于64字节。
• 哈希表：不满足ziplist条件的其他情况。

set

• inset：所有元素都是整数且元素数量小于512
• 哈希表：不满足inset条件的的其他情况。

zset

• ziplist：元素数量小于128且所有元素长度小于64
• 跳表：不满足ziplist条件的其他情况。