redis有序集合(intset)剖析

说明

本篇文章介绍redis中的有序集合(intset)数据结构。该结构使用连续的内存存储，所以每次插入和删除都会触发内存的分配。适合数量较小，插入和删除不平凡的时候使用，不太影响效率的同时节省内存，同时可以利用它的有序性进行高效的查找

实现

inset

typedef struct intset {
    uint32_t encoding;          // 当前集合的编码格式，例如INT16, INT32, INT64，可以理解为每个元素的大小
    uint32_t length;            // set长度
    int8_t contents[];
} intset;

• 同样为了节约内存，intset使用了INT16，INT32，INT64三种编码来存储集合中的元素。编码存放再encoding中
• length存放集合元素的个数
• contents指向实际存放元素数组的地址，通过encoding和length，就可以知道contents实际上是一个int16[length]、int32[length]还是int64[length]数组，这样就能很方便操作集合里面的元素
• intset是一个有序集合，实际上只需要维护好插入节点之后也保持有序即可，插入步骤可以分为：
  • 从contents中通过二分查找插入元素，如果找到，则不插入该元素，如果找不到，则返回该元素应该插入的pos
  • 从pos开始一直到尾部的元素往后移动一位
  • 将该节点赋值到该位置

函数分析

函数	描述	时间复杂度
intsetNew	创建一个空的intset，长度为0，encode为INT16	O(1)
intsetAdd	插入一个元素，如果value比原来编码大，就会扩大原来的编码	O(N)，N为元素个数
intsetRemove	移除元素	O(N)，N为元素个数
intsetFind	查找元素，找不到返回0，找到返回1	O(log(N))，N为元素个数
intsetRandom	从set中随机取一个元素，我看的版本(3.2.12)直接%，如果长度为0，应该会导致宕机	O(1)
intsetGet	从set指定位置取元素，pos无效返回0，有效返回1，值存放在value参数中	O(1)
intsetLen	返回当前set的长度	O(1)
intsetBlobLen	返回当前set的内存占用空间大小，单位Byte	O(1)

每个函数的声明及作用，具体细节可以查看我注释的redis源码

intset *intsetNew(void);        // 创建一个空的intset，长度为0，encode为INT16
intset *intsetAdd(intset *is, int64_t value, uint8_t *success);     // 插入一个元素，如果value比原来编码大，就会扩大原来的编码
intset *intsetRemove(intset *is, int64_t value, int *success);      // 移除一个元素
uint8_t intsetFind(intset *is, int64_t value);                      // 查找一个元素，找不到返回0，找到返回1
int64_t intsetRandom(intset *is);                                   // 从set中随机取一个元素，如果length为0，会导致宕机
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);        // 从指定位置中取一个元素，如果pos在范围内，返回1，否则返回0
uint32_t intsetLen(intset *is);                                     // 返回当前set的长度
size_t intsetBlobLen(intset *is);                                   // 返回当前set的内存占用空间大小，单位Byte