Redis数据结构与对象

1.简单动态字符串

每个sds.h/sdshdr结构表示一个SDS值，Redis是C语言写的。

image.png

与C字符串的区别：

• 常数复杂度获取字符串长度

• 杜绝缓冲区溢出

C字符串不记录长度，如果两个C字符串前后紧挨在一起，这时候扩展前字符串时，后字符串就会被覆盖。

• 减少修改字符串时内存重分配的次数

结构体的free，就是处理分配的空间大小，如果你要扩展的话，可以探索是否有足够空间，够的话直接修改free，不够再重分配，缩短一定不用重分配了，直接缩短就行了。

• 二进制安全

• 兼容部分C字符串函数

2.链表

链表广泛运用与Redis的各个功能，例如：列表键、发布与订阅、慢查询、监视器等。

image (1).png

3.字典

(1) 结构体

字典所使用的的哈希表结构：

image (2).png

我们存进去的hash键值对是哈希表的节点

image (1).png

字典的结构体：

d64ecd6c-f2f3-46ec-96b0-a16542c9b0e1.png

整个关系是：字典>哈希表>键值对

(2)存入过程

• 先计算键值对的哈希值，根据哈希值模哈希表的节点数，得出键值对存入哪个节点中。解决哈希冲突的方法是拉链法

• 当键值对越来越多的时候，为了维持负载因子在一定量，会进行rehash操作。rehash过程采用的是渐进式rehash

4.跳跃表

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

• 跳跃表支持平均Ologn，最坏On复杂度的查找复杂度，跳表实现比平衡二叉树简单。

• 跳表只在有序集合键使用到了

(1)跳表的实现

f82d6ecc-593f-4588-909a-783fe7474dc2.png

跳表用了两个结构体定义，相对复杂的是节点的结构体定义。

跳跃表节点

3c0bcfbb-442c-4f39-bed9-829f8802760b.png

• 每个节点都有一个数组，我们称作层，每一层都可以直接指向其他节点，只要层越多，访问节点速度越快。

• 每层都有一个前进指针，还有个跨度，前进指针用来指向下一个节点，跨度记录前进指针跨了几个节点。

5.整数集合

数据结构如图：

2f76af1a-e7cd-4ed7-8aa3-679b7aaa2476.png

• 整数集合是个集合，所以不会有重复值，只存放整数int8、int32、int64；

• 整数集合底层实现是个数组contents，而且排好序的

• contents的类型不是int8，真正的类型是由encoding的值决定的。

升级与降级

升级过程：

1）根据新元素的类型，扩展数组底层的空间大小，并为新元素分配空间；

2）将底层数组的所有元素换成对应的类型，并保证有序性的情况下放在正确的位置上；

3）将新元素放入底层数组中；

升级的好处：

• 提升灵活性

• 节约内存

降级：整数集合不支持降级操作，一旦升级就不会降级。

6.压缩列表

• 压缩列表是列表键与哈希键的底层实现之一；

• 压缩列表的结构包括：zlbytes、zltail、zllen、entrys；其中entrys是个列表，zlbyte表示整个压缩列表的大小，zltail是从压缩列表首地址到最后一个entry的地址偏移量；

• entry由previous_entry_length、encoding、content组成，其中：

  • previous_entry_length保存上一个entry的长度，大小有1字节或者5字节，可用这个值来计算上一个节点的首地址

• encoding记录了content的类型以及长度

• 连锁更新：我们往一个压缩列表的首节点插入一个大于254字节的节点，这时，后面的那个节点的previous_entry_length就要从1字节编程5字节，这时就需要重分配内存，而重分配后，该节点后一个结点的previous_entry_length也要从1字节变成5字节，会导致连锁更新。