Redis主要数据结构

Redis主要数据结构

字符串

1. 为避免长短不一的字符串造成内存重新分配对性能造成影响，SDS中数组长度不一定字符串长度+1，数组中可以包含空字节
2. 空间预分配

• 可以减少连续执行字符串增长操作所需的内存重分配次数
• SDS长度小于1M，13字节变成13+13+1字节
• SDS长度大于1M，30M变成30M+30M+1

3. 惰性空间释放，缩短SDS保存的字符串时，程序不立即使用内存中分配，而是使用free属性将这些字节的数量记录起来，等待被使用
4. C字符串除字符串末尾外，字符串中不能包含空字符
5. SDS是用来保存一系列二进制数据
6. 用strcasecmp函数来对比SDS保存的字符串和另一个C字符串

链表

1. len链表长度计数器
2. dup函数用于复制链表节点所保存的值
3. free函数释放链表节点锁保存的值
4. match用于比对链表节点保存的值与另一个输入值是否相等

字典 key-value

1. redis的字典是使用哈希表作为底层实现的，一个哈希表里面可以有多个哈希表节点，每个哈希表节点就保存了字典中的一个键值对
2. table属性是一个数组，数组中的每个元素都指向dict.h/dictEntry结构的指针
3. size记录哈希表的大小，即table数组的大小
4. used属性记录哈希表目前已有节点的数量
5. sizemask属性的值是size-1
6. 哈希算法：要将一个新的key-value添加到字典中时，需要先根据键值对计算出哈希值和索引值，再根据索引值将包含键值对的哈希表节点放到哈希表数组的指定索引上去
7. 键冲突

• 多于一个数量的键被分配到哈希表数组的同一个索引上面
• 使用链地址法来解决键冲突，将多个哈希表节点用next指针组成一个单项链表

8. 扩展和收缩哈希表通过rehash（重新散列）操作来完成

• 为字典表ht[1]分配空间
• 将原本的ht[0]的所有键值对都迁移到ht[1]
• 释放ht[0]，将ht[1]设置为ht[0]

9. 哈希表的扩展与收缩

• 哈希表的负载因子计算公式：load_factor = ht[0].used / ht[0].size
• 执行扩展操作1：服务器没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1
• 执行扩展操作2：服务器正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5

10. 渐进式rehash

• 为ht[1]分配空间，字典同时持有ht[0]和ht[1]
• 在字典中维持索引计数器变量rehashidx，并将它的值设为0
• 每次对字典执行添加、删除、查找或者更新操作时，顺带将ht[0]在rehashidx索引上的所有键值对rehash打牌ht[1]上
• 当所有键值对都被rehash到ht[1]上后将，将rehashidx属性的值设为-1，表示rehash所有的操作完成

11. 因为在rehash过程中会同时存在两个哈希表，因此在查找key时，若在ht[0]中没有找到，会继续在ht[1]中查找

跳跃表

1. 跳跃表示一种有序数据结构，在每个节点中维持多个指向其他节点的指针，已达到快速访问每个节点的目的
2. 跳跃表的每层都带有两个属性，前进指针和跨度。前进指针用于访问表尾方向的其他节点，跨度记录前进指针所指的节点和房钱节点之间的距离
3. 后退指针指向当前节点的前一个节点，主要用于遍历

整数集合

1. contents数组是整数集合的底层实现，郑书记和的每个元素都是contents数组的一个数组项，各个项在数组中按值的大小从小到大有序排列，在数组中不包含任何重复项
2. length记录整数集合包含的元素数量
3. encoding属性决定contents的类型
4. 升级：

• 根据新元素的类型，扩展郑书记和底层数组的空间大小，为新元素分配空间
• 将底层数组所有的元素都转换成新元素相同的类型，并将类型转换后的元素防止到争取的位，同时保持有序性不变
• 将新元素添加到底层数组里面

5. 将新元素添加到整数集合的时间复杂度是o(n)
6. 升级的好处：

• 提升灵活性
• 节约内存

7. 整数集合不支持降级

压缩列表

1. 压缩列表是列表键和哈希建的底层实现之一
2. 当一个列表键只有少量列表项，并且每个列表项要么是小整数值，要么是长度比较短的字符串，redis会使用压缩列表来做列表键的底层实现
3. 节点的previous-entry-length属性记录了前一个节点的长度，所以程序可以通过指针和当前节点的起点地址来计算出前一个节点的起始位置
4. content属性保存节点的值
5. redis在特殊情况下产生的连续多次的空间扩展操作称为连锁更新，添加新的节点和删除节点都有可能引发连锁更新，连锁更新最坏的复杂度是o(n^2)

对象

1. redis使用对象来表示数据库中的key和value，每次在redis数据库中创建一个新的key-value至少会创建两个对象
2. redis的每个对象都由一个redisObject结构表示
3. 对象type属性记录了对象的类型
4. 对象的ptr指针指向对象的底层实现数据结构，这些数据结构都是由对象的encoding属性决定的
5. 字符串对象是唯一一种会被其他四种对象嵌套的对象
6. 保存同一键值对的两个节点总是挨在一起，保存键的节点在前，保存值的节点在后
7. 先添加到表头的键值对会被放在压缩列表的表头方向
8. redis在对象系统中使用引用计数的方式实现内存回收，引用计数lru
9. 对象共享节约内存，但是共享对象保存的值越复杂验证共享对象和目标对象是否相同所需要的复杂度会越高
10. 空转时长：当前时间减去键的值对象的lru时间计算出来的