Redis数据结构

数据类型

• String
• List
• Hash
• Sorted Set
• Set

数据结构

sds-简单动态字符串

• Redis通过自定义简单动态字符串，作为可变字符串的存储结构。对比C字符串的优势有
  1）常数复杂度获取字符串长度
  2）可以杜绝缓冲区溢出。SDS通过维护char[]长度，自动扩容实现
  3）减少修改字符串长度时所需的内存分配次数。SDS通过空间预分配和惰性回收实现
  4）二进制安全。C字符串只支持文本的存储，SDS支持二进制的数据存储
  5）兼容部分C字符串函数，直接复用了部分<sting.h>库中的函数

list-双向链表

1）每个链表节点由一个listNode结构来表示，每个节点都有一个指向前置和后置节点的指针
2）每个链表使用一个list结构来表示，这个结构中含有 表头节点指针、表尾节点指针、以及链表长度等信息
3）链表的表头的前置节点和表尾的后置节点指向都是NULL，所以是无环链表
4）通过为链表设置不同的类型特定函数，Redis可用于保存各种不同类型的值

hash-哈希表（字典）

1）字典广泛 应用于Redis的各种功能，包括数据库 和哈希键
2）Redis的字典底层使用哈希表实现，每个字典有两个哈希表，一个平时使用，另一个在进行rehash时使用
3）Redis使用MurmurHash2算法来计算哈希值
4）Redis使用链地址法来解决键冲突，相同hash值的键值对会连接成一个单向链表
5）哈希表进行扩展或收缩时，需要将现有哈希表的所有键值对rehash到新哈希表中，这个rehash过程不是一次性完成的，而是渐进式完成的

zskiplist-跳跃表

1）有序集合的底层实现之一
2）由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表的表头节点、表尾节点、长度等信息，zskiplistNode用于表示跳跃表节点
3）每个跳跃表节点的层高都是1~32之间的随机数
4）同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的
5）跳跃表的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序

intset-整形数组

1）是集合建的底层实现之一
2）底层实现为数组，以有序、无重复的方式保存集合元素，在需要时，会根据新添加的元素类型，改变这个数组的类型。比如默认是int8_t，如果放入的元素大小为int32_t，则程序会将数组的类型更改为int32_t
3）自动升级适配新类型元素，带来了操作上的灵活，并且尽可能地节约了内存
4）只支持升级操作，不支持降级 操作

ziplist-压缩列表

1）为了节约内存而开发的顺序型数据结构
2）是列表键和哈希键的底层实现之一
3）包含多个节点，每个节点可以保存一个字节数组或整数值
4）添加新节点或删除节点，可能会引发连锁的更新操作，但几率很小

数量类型和数据结构的关系

image.png