Redis | @所有人 奇淫数据类型

Redis是一款事件驱动型的数据库服务器，基于key-value实现存储，相比于RDB和AOF持久化方式，文件事件和时间事件的灵活调度，以及键过期时间等知识，真正让我喜欢上它的是内部数据类型，字符串对象、列表对象、哈希对象、集合对象以及有序集合对象，均可选择合适的内部数据类型存储，将其称为奇淫数据类型真不为过，一看究竟吧！

一、简单动态字符串

SDS：用于字符串对象

相比于C字符串，SDS增加free和len变量，具有什么意义呢？且听我娓娓道来：

1）获取字符串长度的复杂度由O(N)降为O(1)

C字符串获取其长度，需从头遍历至尾部；而SDS字符串，直接获取len值即可；

2）杜绝缓冲区溢出和减少内存分配次数

C字符串的拼接、修改和截断操作，首先需要进行内存分配操作，产生大量的系统调用；

SDS的空间预分配和惰性释放策略，有效解决多次内存分配问题；

空间预分配原则：修改后的SDS的len值小于1M视为a，则分配与len值等大的未使用空间，即free为a，此时SDS的buf大小为(2a+1)字节；修改后的SDS的len值大于1M视为A，则分配1M的未使用空间，即free为1M，此时SDS的buf大小为(A+1M+1)字节；(1字节用于空字符串存储)

惰性释放原则：free值大于0时，并不立即回收，等待下一次使用；存在API用于释放free空间，避免造成内存浪费；

3）二进制安全

C字符串仅用于存储文本文件，SDS字符串也可以用于存储二进制文件，二进制文件与文本文件区别 ，简单来说，文本文件是基于固定长度的编码方式，二进制文件是自定义的编码方式

4）兼容部分C字符串函数

C字符串与SDS均保持字符串末尾均以空字符结束，可以兼容部分C字符串函数

二、链表

链表：用于列表键、慢查询和监视器等

三、整数集合

整数集合：实现集合键方式之一

升级操作三步曲：

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

2）将底层所有元素进行升级，转换为新类型后，以有序的方式放置到合适位置；

3）将新元素添加到底层数组中；

四、字典

字典：数据库和哈希键

1）哈希算法

根据键值对的键计算出哈希值，由哈希值和表大小掩码进行与操作确定索引位置；

2）键冲突解决

若不同的键生成相同的哈希值，产生相同的索引位置，使用链地址法解决；出于速度考虑，将新的键值对添加在表头位置；

3）rehash（将负载因子稳定在合适范围内）

将rehashidx值由-1置为0，开始进行rehash操作；如果是扩展，则ht[1]的大小为第一个大于等于ht[0].used * 2的2的n次方的数，如果是收缩，则ht[1]的大小为第一个大于等于ht[0].used的2的n次方的数；基于新的哈希值和表大小掩码计算索引位置；ht[0]中所有键值对迁移结束后，释放ht[0]，将ht[1]更改为ht[0]，创建新的ht[1]

4）渐进式rehash（将rehash操作均摊在对键值对的增删改查上）

添加操作在ht[1]中进行，保证ht[0]中键值对数量只减不增；删除、查找和修改操作先在ht[0]中进行，没有查找到，再在ht[1]中进行；具体的操作细节，在阅读源码之后方可确定

五、跳跃表

跳跃表：有序集合键和集群节点中内部数据结构

六、压缩列表

压缩列表：存储小整数和短字符串

本文是对于《Redis设计与实现》中关于数据类型的简单总结，具体可以参考Redis设计与实现，而关于Redis中常见的操作，可以参照Redis命令查询。转眼间，本学期已经进入期末考试复习阶段，这一学期广泛学习了很多东西。伴随着期末复习的热潮，开始本学期所学内容的梳理和温习。向上吧！少年。