其搜索的步骤为,先通过头结点定位到跳跃表结点,然后通过层去定位到下一个跳跃表结点的位置,直到找到给定分值的结点。
整数集合前提:当一个集合只包含整数值元素,并且这个集合的元素数量不多时。
typedef struct intset{ //编码方式 uint32_t enconding; // 集合包含的元素数量 uint32_t length; //保存元素的数组 int8_t contents[]; }
因为可能存在存入的整数不符合已存在集合中的编码格式,因此需要使用升级策略来解决。
扩展空间:根据新元素的类型,扩展整数集合底层数组的空间大小,并为新元素分配空间
转换编码:将底层数组现有的所有元素都转换成新的编码格式,重新分配空间
添加:将新元素加入到底层数组中
一旦对数组进行了升级,编码就会一直保存升级后的状态。
压缩列表压缩列表是Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个结点,每个结点可以保存一个字节数或者一个整数值。