Shulou(Shulou.com)06/01 Report--

Detailed explanation of intset of redis data structure

In redis, intset is mainly used to save integer values, because the underlying layer uses arrays to save data, so it is necessary to expand and migrate the collection when adding data to the collection, so redis uses this data structure to save the integer collection only when the amount of data is small. The specific underlying data structure is as follows:

Typedef struct intset {/ / Encoding uint32_t encoding; / / the number of elements contained in the collection uint32_t length; / / an array of saved elements int8_t contents [];} intset

The integer collection has three main attributes: encoding is used to save the encoding of the current collection, there are 16-bit, 32-bit and 64-bit; length saves the amount of data saved in the current integer collection; and the contents attribute stores specific data, and the number of bits occupied by each data is specified by the encoding attribute.

What needs to be explained here is that the data in the intset of redis is stored in the order from small to large, so the data can be queried by dichotomy. The specific search code is as follows:

Static uint8_t intsetSearch (intset * is, int64_t value, uint32_t * pos) {int min = 0, max = intrev32ifbe (is- > length)-1, mid =-1; int64_t cur =-1; / * The value can never be found when the set is empty * / / handles the case where is is empty if (intrev32ifbe (is- > length) = = 0) {if (pos) * pos = 0; return 0 } else {/ * Check for the case where we know we cannot find the value, * but do know the insert position. * / because the underlying array is ordered, if value is larger than the last value in the array / / then value certainly does not exist in the collection, / / and value should be added to the last if of the underlying array (value > _ intsetGet (is,intrev32ifbe (is- > length)-1) {if (pos) * pos = intrev32ifbe (is- > length); return 0 / / because the underlying array is ordered, if value is smaller than the first value in the array / / then value certainly does not exist in the collection, / / and it should be added to the front end of the underlying array} else if (value

< _intsetGet(is,0)) { if (pos) *pos = 0; return 0; } } // 在有序数组中进行二分查找 // T = O(log N) while(max >

= min) {mid = (min+max) / 2; cur = _ intsetGet (is,mid); if (value > cur) {min = mid+1;} else if (value)

< cur) { max = mid-1; } else { break; } } // 检查是否已经找到了 value if (value == cur) { if (pos) *pos = mid; return 1; } else { if (pos) *pos = min; return 0; }} 此外，整数集合中具体还有两个需要说明的操作是升级和降级。升级指的是当向低编码的整数集合中添加位数较高的数值时，就会扩容并将整数集合中的所有元素都转换为高位数的编码格式，然后把新添加的元素插入到指定位置；降级指的是当将整数集合中唯一一个高位的元素删除时会将其余元素转换为低位数的编码格式，但是为了提升速率，redis中并不会为剩余元素重新分配内存并进行编码转换，而只是会将该高位元素给删除，并重新分配内存给剩余的元素，然后迁移数据。如图是inset保存数据的示例：

If you have any questions, please leave a message or go to the community to exchange and discuss, thank you for reading, hope to help you, thank you for your support!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.