整数集合(intset)
在redis中，整数集合主要用于存储整数值，其底层实现是数组。但是因为当在增加元素时intset需要扩展内存和移动数据，当元素较多时效率会变低，因此redis只用intset来存储少量的元素。redis中intset结构体定义如下typedefstructintset{uint32_tencoding;//编码格式uint32_tlength;//整数集合中的元素个数int8_tcontents[];//用于存储元素d的数组}intset;该结构体为可变长数组，定义了三个属性：encoding字段表示当前集合的编码格式，即每个元素所占内存大小(16位、32位或者64位)；length字段记录了当前集合所存储的元素总个数；contents字段为数组，其内存大小由当前集合中的元素个数以及元素编码格式来决定。其存储结构如下图整数集合中数据的存储是有序的，由小到大排列的，因此redis对ineset元素查找的实现是使用的是二分查找算法
//该函数主要用于在插入元素时，找到对应的插入位置//或者在删除元素时找到对应的元素位置staticuint8_tintsetSearch(intset*is,int64_tvalue,uint32_t*pos){intmin=0,max=intrev32ifbe(is-length)-1,mid=-1;int64_tcur=-1;//集合中没有元素时直接返回if(intrev32ifbe(is-length)==0){if(pos)*pos=0;return0;}else{//因为数组中的元素是有序的，如果插入的元素大于最后一个元素//则应该插入到数组最后if(value_intsetGet(is,max)){if(pos)*pos=intrev32ifbe(is-length);return0;}elseif(value_intsetGet(is,0)){//同理，当插入元素小于第一个元素//则应该插入到数组最前if(pos)*pos=0;return0;}}//二分查找，搜寻准确的位置//时间复杂度为O(log(N))while(max=min){mid=((unsignedint)min+(unsignedint)max)1;cur=_intsetGet(is,mid);if(valuecur){min=mid+1;}elseif(valuecur){max=mid-1;}else{break;}}//检查已有元素与插入元素值是否相等if(value==cur){if(pos)*pos=mid;return1;}else{if(pos)*pos=min;return0;}}
此外，整数集合还涉及到编码升级过程，intset的元素初始编码默认值为16位，当我们插入的值大于该16位的最大值时，需要对编码进行升级到对应的编码格式(32位或者64位，取决于值的大小)。
有人可能会有疑问，既然有升级，那是否有降级操作呢，在redis的实现中，可能是考虑了效率的因素，并未有编码降级的实现。
压缩列表
压缩列表是一种线性数据结构，由一系列经过编码的内存块组成，其结构设计如下在源码中，列表头由zlbytes、zltail和zllen组成，大小定义如下#defineZIPLIST_HEADER_SIZE(sizeof(uint32_t)*2+sizeof(uint16_t))zlbytes是32位无符号整数，用来标识整个压缩列表所占内存大小(单位字节)；zltail也是32为无符号整数，用来记录最后一个节点(entry)的偏移字节数，这样避免在执行pop操作时需要对整个列表进行遍历；zllen是16位无符号整数，记录节点总数量；zlend为一个特殊结束符，大小为1字节，编码为0XFF。节点(entry)压缩列表的每个节点都是一个被编码的内存块，每个节点都包含前缀，前缀由两个字段两部分组成：prevlen，记录前一个节点的大小，以便于压缩列表的反向遍历；当pevlen小于时，该字段占用1个字节，当prevlen大于等于时，该字段占用5个字节，第一个字节标记为0xFE，后4个字节为字符串长度。encoding，表示当前节点的数据类型(整数或字符串)，当标识字符串时，encoding也存储了字符串的长度。值得注意的是，当整数的数值较小时(1～13)，encoding字段也包含了该整数的值。即会省略掉entry-data。在redis源码中，encoding字段的编码定义有：
00pppppp
字符串，长度小于等于63，pppppp被编码为字符串长度；
01pppppp
qqqqqqqq
字符串，长度小于等于；
qqqqqqqq
rrrrrrrr
ssssssss
tttttttt
字符串，长度大于
16位整数，即数据类型为int16_t；
32位整数，即数据类型为int32_t；
64位整数，即数据类型为int64_t；
24位整数；
8位整数；
xxxx
较小数，1～13；
zlend。因为ziplist压缩列表的实现不具有通用性，只是redis是按这样的编码来实现的，每个人都能有自己的编码方式和实现方式，因此我们只在这个文章中介绍其编码设计来扩展我们的设计思路，而对于ziplist的实现细节就不在这里过多介绍。但是，在实现的过程中我们需要考虑级联更新(CascadeUpdate)的问题，因为每个节点都包含了之前节点的长度，因此修改一个节点或者新增一个节点都有可能会对后续节点造成影响。以上就是redis中两种编码数据结构的实现！对于内存的编码设计，你学会了吗～希望大家能够多多