Redis：5大基本数据类型底层实现（初探）

参考文章：Redis系列（二）: 连集合底层实现原理都不知道，你敢说Redis用的很溜？ - InfoQ 写作平台

redis的5种数据结构及其底层实现原理_zhongzhh8的博客-CSDN博客_redis数据结构的底层实现

String

SDS：全称 Simple Dynamic String，即简单动态字符串

SDS

  • SDS：
    • 组成部分
      • free：表示 buf 中的空闲的空间大小
      • len：表示 buf 中的内容长度
      • buf：一个 char 类型的数组，用于存储实际字符串的内容。
    • 优点
      • 获取字符串长度的复杂度为 O(1)
      • 防止 buf 存储内容溢出的问题
      • 空间预分配 &空间惰性释放
      • 二级制安全性

List

redis3.2之前由 ZipList 和 LinkedList 实现，3.2之后由 QuickList实现

ZipList

  • ZipList：由一块连续的存储空间组成
    • 使用条件
      • List 中存储的每个元素的长度小于 64byte
      • 元素个数小于 512
    • 组成部分
      • zlbytes：表示当前 list 的存储元素的总长度。
      • zllen：表示当前 list 存储的元素的个数。
      • zltail：表示当前 list 的头结点的地址，通过 zltail 就是可以实现 list 的遍历。
      • zlend：表示当前 list 的结束标识。
      • entry：表示存储实际数据的节点，每个 entry 代表一个元素。
      • previours_entry_length: 表示当前节点元素的长度，通过其长度可以计算出下一个元素的位置。
      • encoding：表示元素的编码格式。
      • content：表示实际存储的元素内容。

LinkedList

  • LinkedList：由不连续的内存块形成的双向链表组成
    • 组成部分
      • head：表示 List 的头结点；通过其可以找到 List 的头节点。
      • tail：表示 List 的尾节点；通过其可以找到 List 的尾节点。
      • len：表示 List 存储的元素个数。
      • dup：表示用于复制元素的函数。
      • free：表示用于释放元素的函数。
      • match：表示用于对比元素的函数。

QuickList

  • QuickList：结合ZipList和LinkedList
    • 组成部分
      • 整体上采用LinkedList
      • 具体每个结点采用ZipList

Set

Set集合由Intset和字典组成

Insert

  • Intset
    • 使用条件
      • 元素均为整数
      • 元素个数小于 512

字典

  • 字典

Zset

Zset由ZipList 和 SkipList组成，每个元素包含数据本身和一个对应的分数(score)

ZipList

  • ZipList

SkipList

  • SkipList
  • 组成部分
    • dict
      • 字典
    • zset
      • 跳表

Hash

Hash由ZipList 和HashTable 组成

ZipList

  • ZipList

HashTable

  • HashTable