Redis (4) -- Talking about integer set

1, Preface

Set of integers （intset） Is one of the underlying implementations of set keys , When a set contains only integer value elements , And when the number of elements in this collection is small ,Redis We will use the integer set as the underlying implementation of the set key

Redis Other data structures related to are as follows ：
Simple dynamic string
Linked list
Dictionaries

2, Set of integers

If a set key , When all the stored elements are integer values , Then the underlying implementation of this integer key will be an integer set

SADD numbers 1 3 5 7 9

#  See what data structure is used at the bottom of the collection key 
OBJECT ENCODING numbers

2.1, structure

The related structure of this integer set is as follows ：

typedef struct intset{
    

	// Encoding mode 
	uint32_t encoding;

	// Number of elements contained in the collection 
	uint32_t length;

	// Array to hold elements 
	int8_t contents[];

} intset;

2.1.1,contents

contents An array is the underlying implementation of an integer set ： Every element of the set of integers is contents Each element item of the array , Each element item is arranged in the array according to the size of the value from small to large , And there are no duplicates in the array

2.1.2,length

This property records contents Number of elements in the array

2.1.3,encoding

Although mentioned above contents It's a int8_t Array of , But actually contents What type of value to save depends on encoding Value
encoding There are several options ：

• int8_t： use 8 A digit number represents an integer value （ The minimum is -32768, The maximum is 32767）
• int32_t： use 32 A digit number represents an integer value （ The minimum is -2 147 483 648, The maximum is 2 147 483 647）
• int64_t： use 64 A digit number represents an integer value （ The minimum is -9 223 372 036 854 775 808, The maximum is 9 223 372 036 854 775 807）

2.1.4, Example

• encoding The value bit of INSET_ENC_INT16 Represents the underlying implementation of an integer set as int16_t An array of types , What is kept is int16_t Integer value of type
• length The attribute is 5, Indicates that the integer set stores five elements
• contents Arrays store elements in descending order
• Because every set element is int16_t Integer value of type , therefore contents The size of the array is equal to 80 position

2.2, upgrade

Suppose you have a set of integers A, Inside contents yes int16_t An array of types , So when we gather A There is more than... Stored in int16_t Integer of value range （ Suppose that this integer can be used as int32_t Storage ） when , Will trigger the upgrade , Upgrade the integer set
The upgrade steps are as follows ：

1. According to the type of new elements , Expand the space size of the array at the bottom of the integer set , And allocate space for new elements
2. Convert all elements of the underlying array to be of the same type as the new element , And put it in the right place , And in this process, it is necessary to ensure the storage from small to large
3. Add new elements to the underlying array
4. And then encoding To change the value of INSET_ENC_INT32, And will length From 3 Change it to 4

The benefits of upgrading

The upgrade strategy of integer sets has two advantages ：

• Improve the flexibility of integer set
  • Integer collections can be adapted to new elements by upgrading the underlying array , So that users do not have to worry about type errors
• To save memory
  • Upgrading allows a collection to hold three different types of values at the same time （ In this case, the array type will be INSET_ENC_INT64）, It can also ensure that the upgrade will only be carried out when necessary

Downgrade

The integer set does not support demotion , Once the array is upgraded , The code will always be upgraded