Redis 数据结构

空间与效率平衡的典范

外部数据结构

0. SDS

Simple Dynamic String

• 一个带长度信息的字节数组 【二进制安全】

• 长度小于44使用 embstr 存储，否则 raw

• 小于 1M 扩容空间采用加倍策略，否则扩容只会多分配 1M 大小的冗余空间

二进制安全

• C 语言的字符串默认是以 ‘\0’ 结尾的，也就是说你保存的字符串内存在 ‘\0’，C 语言自会识别前面的数据，后面的就会被忽略掉，所以说是不安全的

• Redis 内部虽然也是以 ‘\0’ 标示一个字符串的结束，但是该字符串的指针内还保存了 len 和 free 两个属性，len 表示该字符串的实际内容所占长度

1. hash

• 两个 hashtable，渐进式 rehash

• hashtable，第一维是数组，第二维是链表

• hash 函数是 siphash

• 元素较少时使用 ziplist

2. list

过去时

• 数据少时 ziplist

• 数据多时使用 linkedlist

现在时 qucklist

• 将 linkedlist 按段切分

• 每一段使用 ziplist 来紧凑存储

• 多个 ziplist 之间使用双向指针串接起来

• 使用 LZF 算法会对 ziplist 压缩 【压缩深度】

3. set

就是 hash，只是所有的 value 都是 NULL

4. zset

• 需要一个 hash 结构来存储 value 和 score 的对应关系

• 需要提供按照 score 来排序【 skiplist 】

• 元素较少时【 ziplist 】

内部数据结构

0. hashtable

• 对 key 进行 hash 计算

• 放入一维数组对应的位置上

• 有冲突的，以链表的形式向下延展

• 链表过长时，扩充一维数组容量

1. skiplist

• 用链表来实现 score 的排序

• 随机选出一些元素，保持顺序，作为上层，依次类推

• 倒着生成的二叉树，提高查询速度

2. ziplist

ztail_offset

• 快速定位到最后一个元素

• 倒着遍历

prevlen

• 前一个 entry 的字节长度

3. listpack

比 ziplist 少了一个 zltail_offset 字段

4. intset

当 set 集合容纳的元素都是整数并且元素个数较小时