Redis设计与实现第六章笔记
date
Jul 21, 2021
slug
Redis设计与实现第六章笔记
status
Published
tags
读书笔记
summary
整数集合
type
Post
6.1 整数集合的实现
contents数组是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项，各个项在数组中按从小到大排列，并且不含重复项
虽然intset结构将contents属性声明为int8_t类型的数组，但实际上contents数组并不保存任何int8_t类型的值，contents数组的真正类型取决于e
6.2 升级
当一个新的比整数集合中所有元素都要长的元素添加到集合中时，集合需要先进行升级，然后才能将新元素添加到整数集合中。
升级步骤：
- 根据新元素类型，扩展集合底层数组空间大小，并为新元素分配空间
- 将底层数组现有的元素都转换成新元素一样的类型，并将元素放在正确的位置，保持底层数组的有序性不变
- 将新元素添加到底层数组里
向整数集合添加新元素的时间复杂度时O(N)，因为可能需要对所有元素进行类型转换。
以为引发升级的新元素长度总是比原有的所有元素要长，所有这个元素要么比所有元素大（放在最末尾），要么比所有元素小（放在最开头）。
6.3 升级的好处
6.3.1 提升灵活性
可以根据需要将不同类型的元素添加到集合，而不必担心类型错误
6.3.2 节约内存
既可以同时保存三种不同类型的值，又可以确保升级操作只会在有需要的时候进行，可以尽量节省内存。
6.4 降级
整数集合不支持降级