Redis壶中天-内部数据结构

常用数据类型的底层实现

简单动态字符串、链表、字典、跳跃表、整数集合、压缩列表、快速列表

本文所使用的Redis版本为3.2.8

安装与启动

macOS下使用homebrew安装

1
brew install redis

启动server

1
redis-server

启动client

1
redis-cli # 默认地址为127.0.0.1:6379

简单动态字符串

简单动态字符串(SDS,Simple Dynamic String)为redis中默认字符串的表示。

1
2
3
4
127.0.0.1:6379> SET msg "hello redis"
OK
127.0.0.1:6379> Object encoding msg
"embstr"

构成

sdshdr

属性 类型 描述
len int buf数组中已使用的字节数量,字符串的长度
free int buf数组中未使用字节数量
buf[ ] char 字节数组,保存字符串

特点

相对于C中string类型的优点:

  • 获取字符串长度的复杂度为O(1)
  • API是安全的,不会造成缓冲区溢出
  • 可保存文本或二进制数据
  • 可使用一部分库中的函数

用处

  • 保存数据库的字符串值
  • AOF缓冲区
  • 客户端输入状态缓冲区

链表

一种常用的数据结构,顺序式的节点访问方式与灵活的链表长度调整。

构成

listNode

属性 类型 描述
*prev struct listNode 前置节点
*next struct listNode 后置节点
*value void 节点值

list

属性 类型 描述
*head listNode 表头结点
*tail listNode 表尾节点
len unsigned long 链表所包含节点数量
dup function 节点值复制函数
free function 节点值释放函数
match function 节点值对比函数

特点

  • 双向 - 每个节点都有prev和next指针
  • 无环 - 表头的prev与表尾的next都指向NULL
  • 带表头指针和表尾指针 - 通过head和tail指针获取表头和表尾
  • 带链表长度计数器 - 使用len属性对节点计数
  • 多态 - 可使用dup、free与match属性为节点值设置类型特定函数

用处

  • 列表键
  • 发布与订阅、慢查询、监视器
  • 保存多个客户端的状态信息
  • 构建客户端输出缓冲区

字典

一种用于保存键值对的抽象数据结构。

构成

dictht - 哈希表

属性 类型 描述
**table dictEntry 哈希表数组
size unsigned long 哈希表大小
sizemask unsigned long 哈希表大小掩码 总是=size-1
used unsigned long 已有节点数量

dictentr - 哈希表节点

属性 类型 描述
*key void
v union{void *val;uint64_t u64; int64_t s64}
*next struct dictEntry 指向下个节点,形成链表

dict

属性 类型 描述
*type dictType 类型特定函数
*privatedata void 私有数据
ht[2] dictht 哈希表
trehashidx int rehash索引

特点

  • 每个字典都有两个哈希表,一个平时使用,一个在rehash时使用
  • 哈希表使用链地址法解决键冲突
  • 当对哈希表进行扩展或者收缩操作时,需要将现有哈希表的所有键值对渐进式地rehash到新哈希表里

用处

  • 数据库及CRUD操作
  • 哈希键

跳跃表

一种有序数据结构,通过在每个节点中维持多个指向其它节点的指针,达到快速访问节点的目的。

构成

zskiplistNode

属性 类型 描述
*backward struct zskiplistNode 后退指针
score double 分值
*obj robj 成员对象
zskiplistLevel struct 层(包含前进指针与跨度)

zskiplist

属性 类型 描述
*header struct zskiplistNode 表头节点
*tail struct zskiplistNode 表尾节点
length unsigned long 节点数量
level int 最大节点层数

特点

  • 每个节点的层高为1到32的随机数
  • 同一个表中,多个节点可以包含相同的分值,但每个节点的成员对象必须唯一
  • 跳跃表中按节点分值大小排序,若分值相同则按成员对象大小排序

整数集合

一种包含少量整数值元素的集合。

构成

intset

属性 类型 描述
encoding uint32_t 编码方式
length uint32_t 元素数量
contents[] int8_t 保存元素的数组

特点

  • 底层实现为数组,有序、无重复的范式保存集合元素
  • 有需要时会根据添加元素的类型改变数组类型

压缩列表

一种由一系列特殊编码的连续内存块组成的顺序型数据结构。

构成

ziplist

属性 类型 描述
zlbytes uint32_t 占用的字节数
zltail uint32_t 表尾节点距起始地址的字节数
zllen uint16_t 节点数量
entryX 列表节点 各个节点,长度由内容决定
zlend uint8_t 末端

特点

  • 包含多个节点,每个节点保存一个字节数组或者整数值
  • 添加或删除节点有可能会引起连锁更新

快速列表

redis3.2引入的数据类型,快速列表是一种双向链表,每个节点都是一个压缩列表。

1
2
3
4
127.0.0.1:6379> RPUSH foo 1 2 3 "yrq" "yeah"
(integer) 5
127.0.0.1:6379> OBJECT ENCODING foo
"quicklist"

构成

quicklistNode

属性 类型 描述
*prev struct quicklistNode 指向前一个节点的指针
*next struct quicklistNode 指向后一个节点的指针
*zl unsigned char 数据指针,若压缩指向ziplist,否则指向quicklistLZF
sz 列表节点 各个节点,长度由内容决定
count uint8_t 末端

quicklistLZF - 用LZF算法压缩的ziplist

属性 类型 描述
sz unsigned int 压缩后的ziplist大小
compressed[ ] char 存放压缩后的ziplist字节数组

quicklist

属性 类型 描述
*head quicklistNode 表头指针
*tail quicklistNode 表尾指针
count uint16_t 数据项数量
len 列表节点 节点数量,击ziplist数量

特点

  • 结合了双向链表和ziplist的优点,提高了Redis的效率,修改操作的复杂度低。

参考

文章目录
  1. 1. 安装与启动
  2. 2. 简单动态字符串
    1. 2.1. 构成
    2. 2.2. 特点
    3. 2.3. 用处
  3. 3. 链表
    1. 3.1. 构成
    2. 3.2. 特点
    3. 3.3. 用处
  4. 4. 字典
    1. 4.1. 构成
    2. 4.2. 特点
    3. 4.3. 用处
  5. 5. 跳跃表
    1. 5.1. 构成
    2. 5.2. 特点
  6. 6. 整数集合
    1. 6.1. 构成
    2. 6.2. 特点
  7. 7. 压缩列表
    1. 7.1. 构成
    2. 7.2. 特点
  8. 8. 快速列表
    1. 8.1. 构成
    2. 8.2. 特点
  9. 9. 参考
|