Redis底层数据结构学习

发表于 更新于 分类于 阅读次数：

总体概述

Redis是一种键值对形式的NoSQL数据库，它使用哈希表来保存所有的键值，哈希表可以快速的以O(1)的时间复杂度帮我们找到我们需要的键值对。
在Redis中，键是String类型的，而对应的值则可以是任何的Redis中的数据类型，比如String、list、set、zset、hash等。哈希表中并不是直接存放值本身，而是通过void * key和void * value指针，分别指向实际的键对象和值对象，所以无论值是什么类型的，都可以通过指针来找到。
下面是一张Redis保存键值所涉及的数据结构：

  • redisDb 结构，表示 Redis 数据库的结构，结构体⾥存放了指向了 dict 结构的指针；
  • dict 结构，结构体⾥存放了 2 个哈希表，正常情况下都是⽤哈希表1，哈希表2只有在 rehash 的时候才⽤；
  • ditctht 结构，表示哈希表的结构，结构⾥存放了哈希表数组，数组中的每个元素都是指向⼀个哈希表 节点结构（dictEntry）的指针；
  • dictEntry 结构，表示哈希表节点的结构，结构⾥存放了 void * key 和 void * value 指针， * key 指向 的是 String 对象，⽽ * value 则可以指向 String 对象，也可以指向集合类型的对象，⽐如 List 对 象、Hash 对象、Set 对象和 Zset 对象。
    void * key和void * value指针指向的是Redis对象，Redis中的每个对象都是由redisObject结构来表示的，具体结构如下图：

对象结构⾥包含的成员变量包括：

  • type，标识该对象是什么类型的对象（String 对象、 List 对象、Hash 对象、Set 对象和 Zset 对 象）；
  • encoding，标识该对象使⽤了哪种底层的数据结构；
  • ptr，指向底层数据结构的指针。

数据结构实现

SDS(Simple Dynamic String)

结构中的每个成员变量分别介绍下：

  • len，记录了字符串⻓度。这样获取字符串⻓度的时候，只需要返回这个成员变量值就⾏，时间复杂度 只需要 O(1)。
  • alloc，分配给字符数组的空间⻓度。这样在修改字符串的时候，可以通过 ==alloc - len== 计算出剩余的 空间⼤⼩，可以⽤来判断空间是否满⾜修改需求，如果不满⾜的话，就会⾃动将 SDS 的空间扩展⾄ 执⾏修改所需的⼤⼩，然后才执⾏实际的修改操作，所以使⽤ SDS 既不需要⼿动修改 SDS 的空间⼤ ⼩，也不会出现前⾯所说的缓冲区溢出的问题。
  • flags，⽤来表示不同类型的 SDS。⼀共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、 sdshdr32 和 sdshdr64，分别支持不同长度的变量位数。
  • buf[]，字符数组，⽤来保存实际数据。不仅可以保存字符串，也可以保存⼆进制数据。